Arrow Research search

Author name cluster

Terence Tao

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers
1 author row

Possible papers

4

FOCS Conference 2007 Conference Paper

Structure and Randomness in Combinatorics

  • Terence Tao

Combinatorics, like computer science, often has to deal with large objects of unspecified (or unusable) structure. One powerful way to deal with such an arbitrary object is to decompose it into more usable components. In particular, it has proven profitable to decompose such objects into a structured component, a pseudo-random component, and a small component (i. e. an error term): in many cases it is the structured component which then dominates. We illustrate this philosophy in a number of model cases.

Details

STOC Conference 2007 Conference Paper

The condition number of a randomly perturbed matrix

  • Van H. Vu
  • Terence Tao

Let M be an arbitrary n by n matrix. We study the conditionnumber a random perturbation M+N n of M, where N n is arandom matrix. It is shown that, under very general conditions on M and M n , the condition number of M+N n is polynomial in n with very high probability. The main novelty here is that we allow N n to have discrete distribution.

Details

FOCS Conference 2005 Conference Paper

Error Correction via Linear Programming

  • Emmanuel J. Candès
  • Mark Rudelson
  • Terence Tao
  • Roman Vershynin

Suppose we wish to transmit a vector f ϵ R n reliably. A frequently discussed approach consists in encoding f with an m by n coding matrix A. Assume now that a fraction of the entries of Af are corrupted in a completely arbitrary fashion by an error e. We do not know which entries are affected nor do we know how they are affected. Is it possible to recover f exactly from the corrupted m-dimensional vector y = Af + e?

Details
v2026.09.13