All reports by Author Madhu Sudan:

__
TR18-150
| 27th August 2018
__

Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan#### Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation

__
TR18-027
| 8th February 2018
__

Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan#### General Strong Polarization

__
TR17-138
| 17th September 2017
__

Srikanth Srinivasan, Madhu Sudan#### Local decoding and testing of polynomials over grids

Revisions: 1

__
TR17-081
| 2nd May 2017
__

Badih Ghazi, Madhu Sudan#### The Power of Shared Randomness in Uncertain Communication

__
TR16-194
| 4th December 2016
__

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan#### The Optimality of Correlated Sampling

Revisions: 1

__
TR16-104
| 14th July 2016
__

Badih Ghazi, Pritish Kamath, Madhu Sudan#### Decidability of Non-Interactive Simulation of Joint Distributions

__
TR15-087
| 30th May 2015
__

Badih Ghazi, Pritish Kamath, Madhu Sudan#### Communication Complexity of Permutation-Invariant Functions

__
TR15-064
| 19th April 2015
__

Ilan Komargodski, Pravesh Kothari, Madhu Sudan#### Communication with Contextual Uncertainty

Revisions: 1

__
TR15-043
| 2nd April 2015
__

Alan Guo, Elad Haramaty, Madhu Sudan#### Robust testing of lifted codes with applications to low-degree testing

__
TR14-153
| 14th November 2014
__

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan#### Communication with Imperfectly Shared Randomness

Revisions: 2

__
TR14-067
| 4th May 2014
__

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang#### Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

__
TR13-055
| 5th April 2013
__

David Gamarnik, Madhu Sudan#### Limits of local algorithms over sparse random graphs

__
TR13-030
| 20th February 2013
__

Elad Haramaty, Noga Ron-Zewi, Madhu Sudan#### Absolutely Sound Testing of Lifted Codes

__
TR12-166
| 25th November 2012
__

Elad Haramaty, Madhu Sudan#### Deterministic Compression with Uncertain Priors

__
TR12-149
| 8th November 2012
__

Alan Guo, Swastik Kopparty, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR12-106
| 27th August 2012
__

Alan Guo, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR12-049
| 27th April 2012
__

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan#### Sparse affine-invariant linear codes are locally testable

__
TR12-048
| 25th April 2012
__

Alan Guo, Madhu Sudan#### Some closure features of locally testable affine-invariant properties

__
TR12-046
| 24th April 2012
__

Madhu Sudan, Noga Ron-Zewi#### A new upper bound on the query complexity for testing generalized Reed-Muller codes

Revisions: 1

__
TR11-079
| 9th May 2011
__

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan#### On Sums of Locally Testable Affine Invariant Properties

__
TR11-059
| 15th April 2011
__

Elad Haramaty, Amir Shpilka, Madhu Sudan#### Optimal testing of multivariate polynomials over small prime fields

__
TR11-005
| 20th January 2011
__

Madhu Sudan#### Testing Linear Properties: Some general themes

Revisions: 1

__
TR10-116
| 21st July 2010
__

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie#### Testing linear-invariant non-linear properties: A short report

__
TR10-108
| 9th July 2010
__

Eli Ben-Sasson, Madhu Sudan#### Limits on the rate of locally testable affine-invariant codes

__
TR10-051
| 26th March 2010
__

Madhu Sudan#### Invariance in Property Testing

__
TR09-126
| 26th November 2009
__

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman#### Locally Testable Codes Require Redundant Testers

Revisions: 3

__
TR09-086
| 2nd October 2009
__

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman#### Optimal testing of Reed-Muller codes

Revisions: 1

__
TR09-075
| 17th September 2009
__

Oded Goldreich, Brendan Juba, Madhu Sudan#### A Theory of Goal-Oriented Communication

Revisions: 1
,
Comments: 1

__
TR09-043
| 18th May 2009
__

Elena Grigorescu, Tali Kaufman, Madhu Sudan#### Succinct Representation of Codes with Applications to Testing

__
TR09-004
| 15th January 2009
__

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan#### Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

__
TR08-095
| 31st October 2008
__

Brendan Juba, Madhu Sudan#### Universal Semantic Communication II: A Theory of Goal-Oriented Communication

Revisions: 1

__
TR08-088
| 13th September 2008
__

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie#### Testing Linear-Invariant Non-Linear Properties

Revisions: 1

__
TR08-033
| 21st March 2008
__

Elena Grigorescu, Tali Kaufman, Madhu Sudan#### 2-Transitivity is Insufficient for Local Testability

__
TR08-020
| 7th March 2008
__

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan#### Decodability of Group Homomorphisms beyond the Johnson Bound

__
TR07-111
| 1st November 2007
__

Tali Kaufman, Madhu Sudan#### Algebraic Property Testing: The Role of Invariance

__
TR07-084
| 4th September 2007
__

Brendan Juba, Madhu Sudan#### Universal Semantic Communication I

__
TR07-060
| 11th July 2007
__

Tali Kaufman, Madhu Sudan#### Sparse Random Linear Codes are Locally Decodable and Testable

__
TR06-118
| 2nd September 2006
__

Irit Dinur, Madhu Sudan, Avi Wigderson#### Robust Local Testability of Tensor Products of LDPC Codes

__
TR04-093
| 9th November 2004
__

Oded Goldreich, Madhu Sudan, Luca Trevisan#### From logarithmic advice to single-bit advice

__
TR04-060
| 22nd July 2004
__

Eli Ben-Sasson, Madhu Sudan#### Simple PCPs with Poly-log Rate and Query Complexity

__
TR04-046
| 4th June 2004
__

Eli Ben-Sasson, Madhu Sudan#### Robust Locally Testable Codes and Products of Codes

__
TR04-021
| 23rd March 2004
__

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan#### Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

__
TR03-019
| 3rd April 2003
__

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan#### Bounds on 2-Query Codeword Testing.

Revisions: 1

__
TR02-050
| 5th August 2002
__

Oded Goldreich, Madhu Sudan#### Locally Testable Codes and PCPs of Almost-Linear Length

__
TR00-062
| 25th August 2000
__

Venkatesan Guruswami, Johan Håstad, Madhu Sudan#### Hardness of approximate hypergraph coloring

__
TR00-061
| 14th August 2000
__

Prahladh Harsha, Madhu Sudan#### Small PCPs with low query complexity

__
TR99-029
| 31st August 1999
__

Ilya Dumer, Daniele Micciancio, Madhu Sudan#### Hardness of approximating the minimum distance of a linear code

__
TR99-025
| 2nd July 1999
__

Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan#### Linear Consistency Testing

__
TR98-074
| 16th December 1998
__

Madhu Sudan, Luca Trevisan, Salil Vadhan#### Pseudorandom generators without the XOR Lemma

Revisions: 2

__
TR98-062
| 28th October 1998
__

Oded Goldreich, Dana Ron, Madhu Sudan#### Chinese Remaindering with Errors

Revisions: 4
,
Comments: 1

__
TR98-060
| 8th October 1998
__

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan#### Learning polynomials with queries -- The highly noisy case.

__
TR98-043
| 27th July 1998
__

Venkatesan Guruswami, Madhu Sudan#### Improved decoding of Reed-Solomon and algebraic-geometric codes.

__
TR98-040
| 24th July 1998
__

Madhu Sudan, Luca Trevisan#### Probabilistically checkable proofs with low amortized query complexity

__
TR98-017
| 29th March 1998
__

Oded Goldreich, Madhu Sudan#### Computational Indistinguishability: A Sample Hierarchy.

__
TR98-008
| 15th January 1998
__

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy#### Proof verification and the hardness of approximation problems.

__
TR97-003
| 29th January 1997
__

Sanjeev Arora, Madhu Sudan#### Improved low-degree testing and its applications

__
TR96-064
| 11th December 1996
__

Sanjeev Khanna, Madhu Sudan, Luca Trevisan#### Constraint satisfaction: The approximability of minimization problems.

__
TR96-062
| 3rd December 1996
__

Sanjeev Khanna, Madhu Sudan, David P. Williamson#### A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

__
TR96-028
| 9th April 1996
__

Sanjeev Khanna, Madhu Sudan#### The Optimization Complexity of Constraint Satisfaction Problems

__
TR95-024
| 23rd May 1995
__

Mihir Bellare, Oded Goldreich, Madhu Sudan#### Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

__
TR95-023
| 16th May 1995
__

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani#### On Syntactic versus Computational views of Approximability

Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan

We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ with the pairs $(X_1,Y_1)$, $(X_2, Y_2)$, $\dots$ being drawn independently from some known probability distribution $\mu$. They ... more >>>

Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan

Ar\i kan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix $M$, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the $\textit{polarization}$ of an associated $[0,1]$-bounded martingale, ... more >>>

Srikanth Srinivasan, Madhu Sudan

The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate

polynomials of total degree at most $d$ over

grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \times A_n$, form

error-correcting codes (of distance at least $2^{-d}$ provided $\min_i\{|A_i|\}\geq 2$).

In this work we explore their local

decodability and local testability. ...
more >>>

Badih Ghazi, Madhu Sudan

In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function ... more >>>

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan

In the "correlated sampling" problem, two players, say Alice and Bob, are given two distributions, say $P$ and $Q$ respectively, over the same universe and access to shared randomness. The two players are required to output two elements, without any interaction, sampled according to their respective distributions, while trying to ... more >>>

Badih Ghazi, Pritish Kamath, Madhu Sudan

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions $P(x,y)$ and $Q(u,v)$: The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where ... more >>>

Badih Ghazi, Pritish Kamath, Madhu Sudan

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of ''permutation-invariant'' functions. A partial function $f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$ is permutation-invariant if for every bijection $\pi:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, it is the case that $f(\mathbf{x}, \mathbf{y}) ... more >>>

Ilan Komargodski, Pravesh Kothari, Madhu Sudan

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information $x$ and Bob gets $y$, where $(x,y)$ is drawn from a known distribution, and Bob ... more >>>

Alan Guo, Elad Haramaty, Madhu Sudan

A local tester for a code probabilistically looks at a given word at a small set of coordinates and based on this local view accepts codewords with probability one while rejecting words far from the code with constant probabilility. A local tester for a code is said to be ``robust'' ... more >>>

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

The communication complexity of many fundamental problems reduces greatly

when the communicating parties share randomness that is independent of the

inputs to the communication task. Natural communication processes (say between

humans) however often involve large amounts of shared correlations among the

communicating players, but rarely allow for perfect sharing of ...
more >>>

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>

David Gamarnik, Madhu Sudan

Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research ... more >>>

Elad Haramaty, Noga Ron-Zewi, Madhu Sudan

In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of "affine-invariant'' codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes ... more >>>

Elad Haramaty, Madhu Sudan

We consider the task of compression of information when the source of the information and the destination do not agree on the prior, i.e., the distribution from which the information is being generated. This setting was considered previously by Kalai et al. (ICS 2011) who suggested that this was a ... more >>>

Alan Guo, Swastik Kopparty, Madhu Sudan

In this work we explore error-correcting codes derived from

the ``lifting'' of ``affine-invariant'' codes.

Affine-invariant codes are simply linear codes whose coordinates

are a vector space over a field and which are invariant under

affine-transformations of the coordinate space. Lifting takes codes

defined over a vector space of small dimension ...
more >>>

Alan Guo, Madhu Sudan

the ``lifting'' of ``affine-invariant'' codes.

Affine-invariant codes are simply linear codes whose coordinates

are a vector space over a field and which are invariant under

affine-transformations of the coordinate space. Lifting takes codes

defined over a vector space of small dimension ...
more >>>

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan

We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field ${\mathbb{F}}_q$ and an extension field ${\mathbb{F}}_{q^n}$, a property is a set of functions mapping ${\mathbb{F}}_{q^n}$ to ${\mathbb{F}}_q$. The property is said to be affine-invariant if it ... more >>>

Alan Guo, Madhu Sudan

We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and "lifts". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The "lift" is a less natural ... more >>>

Madhu Sudan, Noga Ron-Zewi

Over a finite field $\F_q$ the $(n,d,q)$-Reed-Muller code is the code given by evaluations of $n$-variate polynomials of total degree at most $d$ on all points (of $\F_q^n$). The task of testing if a function $f:\F_q^n \to \F_q$ is close to a codeword of an $(n,d,q)$-Reed-Muller code has been of ... more >>>

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Affine-invariant properties are an abstract class of properties that generalize some

central algebraic ones, such as linearity and low-degree-ness, that have been

studied extensively in the context of property testing. Affine invariant properties

consider functions mapping a big field $\mathbb{F}_{q^n}$ to the subfield $\mathbb{F}_q$ and include all

properties that form ...
more >>>

Elad Haramaty, Amir Shpilka, Madhu Sudan

We consider the problem of testing if a given function $f : \F_q^n \rightarrow \F_q$ is close to a $n$-variate degree $d$ polynomial over the finite field $\F_q$ of $q$ elements. The natural, low-query, test for this property would be to pick the smallest dimension $t = t_{q,d}\approx d/q$ such ... more >>>

Madhu Sudan

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, ... more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied ... more >>>

Eli Ben-Sasson, Madhu Sudan

A linear code is said to be affine-invariant if the coordinates of the code can be viewed as a vector space and the code is invariant under an affine transformation of the coordinates. A code is said to be locally testable if proximity of a received word

to the code ...
more >>>

Madhu Sudan

Property testing considers the task of testing rapidly (in particular, with very few samples into the data), if some massive data satisfies some given property, or is far from satisfying the property. For ``global properties'', i.e., properties that really depend somewhat on every piece of the data, one could ask ... more >>>

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes

whose duals have (superlinearly) {\em many} small weight ...
more >>>

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

We consider the problem of testing if a given function

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

more >>>

Oded Goldreich, Brendan Juba, Madhu Sudan

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this ... more >>>

Elena Grigorescu, Tali Kaufman, Madhu Sudan

Motivated by questions in property testing, we search for linear

error-correcting codes that have the ``single local orbit'' property:

i.e., they are specified by a single local

constraint and its translations under the symmetry group of the

code. We show that the dual of every ``sparse'' binary code

whose coordinates

more >>>

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.

\begin{enumerate}

\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ...
more >>>

Brendan Juba, Madhu Sudan

We continue the investigation of the task of meaningful communication among intelligent entities (players, agents) without any prior common language. Our generic thesis is that such communication is feasible provided the goals of the communicating players are verifiable and compatible. In a previous work we gave supporting evidence for this ... more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

We consider the task of testing properties of Boolean functions that

are invariant under linear transformations of the Boolean cube. Previous

work in property testing, including the linearity test and the test

for Reed-Muller codes, has mostly focused on such tasks for linear

properties. The one exception is a test ...
more >>>

Elena Grigorescu, Tali Kaufman, Madhu Sudan

A basic goal in Property Testing is to identify a

minimal set of features that make a property testable.

For the case when the property to be tested is membership

in a binary linear error-correcting code, Alon et al.~\cite{AKKLR}

had conjectured that the presence of a {\em single} low weight

more >>>

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>

Tali Kaufman, Madhu Sudan

We argue that the symmetries of a property being tested play a

central role in property testing. We support this assertion in the

context of algebraic functions, by examining properties of functions

mapping a vector space $\K^n$ over a field $\K$ to a subfield $\F$.

We consider $\F$-linear properties that ...
more >>>

Brendan Juba, Madhu Sudan

Is it possible for two intelligent beings to communicate meaningfully, without any common language or background? This question has interest on its own, but is especially relevant in the context of modern computational infrastructures where an increase in the diversity of computers is making the task of inter-computer interaction increasingly ... more >>>

Tali Kaufman, Madhu Sudan

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and ... more >>>

Irit Dinur, Madhu Sudan, Avi Wigderson

Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>>

Oded Goldreich, Madhu Sudan, Luca Trevisan

Building on Barak's work (Random'02),

Fortnow and Santhanam (FOCS'04) proved a time hierarchy

for probabilistic machines with one bit of advice.

Their argument is based on an implicit translation technique,

which allow to translate separation results for short (say logarithmic)

advice (as shown by Barak) into separations for ...
more >>>

Eli Ben-Sasson, Madhu Sudan

We give constructions of PCPs of length n*polylog(n) (with respect

to circuits of size n) that can be verified by making polylog(n)

queries to bits of the proof. These PCPs are not only shorter than

previous ones, but also simpler. Our (only) building blocks are

Reed-Solomon codes and the bivariate ...
more >>>

Eli Ben-Sasson, Madhu Sudan

We continue the investigation of locally testable codes, i.e.,

error-correcting codes for whom membership of a given word in the

code can be tested probabilistically by examining it in very few

locations. We give two general results on local testability:

First, motivated by the recently proposed notion of robust

probabilistically ...
more >>>

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

We continue the study of the trade-off between the length of PCPs

and their query complexity, establishing the following main results

(which refer to proofs of satisfiability of circuits of size $n$):

We present PCPs of length $\exp(\tildeO(\log\log n)^2)\cdot n$

that can be verified by making $o(\log\log n)$ Boolean queries.

more >>>

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

We present upper bounds on the size of codes that are locally

testable by querying only two input symbols. For linear codes, we

show that any $2$-locally testable code with minimal distance

$\delta n$ over a finite field $F$ cannot have more than

$|F|^{3/\delta}$ codewords. This result holds even ...
more >>>

Oded Goldreich, Madhu Sudan

Locally testable codes are error-correcting codes that admit

very efficient codeword tests. Specifically, using a constant

number of (random) queries, non-codewords are rejected with

probability proportional to their distance from the code.

Locally testable codes are believed to be the combinatorial

core of PCPs. However, the relation is ...
more >>>

Venkatesan Guruswami, Johan Håstad, Madhu Sudan

We introduce the notion of covering complexity of a probabilistic

verifier. The covering complexity of a verifier on a given input is

the minimum number of proofs needed to ``satisfy'' the verifier on

every random string, i.e., on every random string, at least one of the

given proofs must be ...
more >>>

Prahladh Harsha, Madhu Sudan

Most known constructions of probabilistically checkable proofs (PCPs)

either blow up the proof size by a large polynomial, or have a high

(though constant) query complexity. In this paper we give a

transformation with slightly-super-cubic blowup in proof size, with a

low query complexity. Specifically, the verifier probes the proof ...
more >>>

Ilya Dumer, Daniele Micciancio, Madhu Sudan

We show that the minimum distance of a linear code (or

equivalently, the weight of the lightest codeword) is

not approximable to within any constant factor in random polynomial

time (RP), unless NP equals RP.

Under the stronger assumption that NP is not contained in RQP

(random ...
more >>>

Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan

We extend the notion of linearity testing to the task of checking

linear-consistency of multiple functions. Informally, functions

are ``linear'' if their graphs form straight lines on the plane.

Two such functions are ``consistent'' if the lines have the same

slope. We propose a variant of a test of ...
more >>>

Madhu Sudan, Luca Trevisan, Salil Vadhan

Impagliazzo and Wigderson have recently shown that

if there exists a decision problem solvable in time $2^{O(n)}$

and having circuit complexity $2^{\Omega(n)}$

(for all but finitely many $n$) then $\p=\bpp$. This result

is a culmination of a series of works showing

connections between the existence of hard predicates

and ...
more >>>

Oded Goldreich, Dana Ron, Madhu Sudan

The Chinese Remainder Theorem states that a positive

integer m is uniquely specified by its remainder modulo

k relatively prime integers p_1,...,p_k, provided

m < \prod_{i=1}^k p_i. Thus the residues of m modulo

relatively prime integers p_1 < p_2 < ... < p_n

form a redundant representation of m if ...
more >>>

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

This is a revised version of work which has appeared

in preliminary form in the 36th FOCS, 1995.

Given a function $f$ mapping $n$-variate inputs from a finite field

$F$ into $F$,

we consider the task of reconstructing a list of all $n$-variate

degree $d$ polynomials which agree with $f$

more >>>

Venkatesan Guruswami, Madhu Sudan

We present an improved list decoding algorithm for decoding

Reed-Solomon codes. Given an arbitrary string of length n, the

list decoding problem is that of finding all codewords within a

specified Hamming distance from the input string.

It is well-known that this decoding problem for Reed-Solomon

codes reduces to the ...
more >>>

Madhu Sudan, Luca Trevisan

The error probability of Probabilistically Checkable Proof (PCP)

systems can be made exponentially small in the number of queries

by using sequential repetition. In this paper we are interested

in determining the precise rate at which the error goes down in

an optimal protocol, and we make substantial progress toward ...
more >>>

Oded Goldreich, Madhu Sudan

We consider the existence of pairs of probability ensembles which

may be efficiently distinguished given $k$ samples

but cannot be efficiently distinguished given $k'<k$ samples.

It is well known that in any such pair of ensembles it cannot be that

both are efficiently computable

(and that such phenomena ...
more >>>

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

We show that every language in NP has a probablistic verifier

that checks membership proofs for it using

logarithmic number of random bits and by examining a

<em> constant </em> number of bits in the proof.

If a string is in the language, then there exists a proof ...
more >>>

Sanjeev Arora, Madhu Sudan

NP = PCP(log n, 1) and related results crucially depend upon

the close connection between the probability with which a

function passes a ``low degree test'' and the distance of

this function to the nearest degree d polynomial. In this

paper we study a test ...
more >>>

Sanjeev Khanna, Madhu Sudan, Luca Trevisan

This paper continues the work initiated by Creignou [Cre95] and

Khanna, Sudan and Williamson [KSW96] who classify maximization

problems derived from boolean constraint satisfaction. Here we

study the approximability of {\em minimization} problems derived

thence. A problem in this framework is characterized by a

collection F ...
more >>>

Sanjeev Khanna, Madhu Sudan, David P. Williamson

In this paper we study the approximability of boolean constraint

satisfaction problems. A problem in this class consists of some

collection of ``constraints'' (i.e., functions

$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set

of constraints applied to specified subsets of $n$ boolean

variables. Schaefer earlier ...
more >>>

Sanjeev Khanna, Madhu Sudan

In 1978, Schaefer considered a subclass of languages in

NP and proved a ``dichotomy theorem'' for this class. The subclass

considered were problems expressible as ``constraint satisfaction

problems'', and the ``dichotomy theorem'' showed that every language in

this class is either in P, or is NP-hard. This result is in ...
more >>>

Mihir Bellare, Oded Goldreich, Madhu Sudan

This paper continues the investigation of the connection between proof

systems and approximation. The emphasis is on proving ``tight''

non-approximability results via consideration of measures like the

``free bit complexity'' and the ``amortized free bit complexity'' of

proof systems.

The first part of the paper presents a collection of new ... more >>>

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

We attempt to reconcile the two distinct views of approximation

classes: syntactic and computational.

Syntactic classes such as MAX SNP allow for clean complexity-theoretic

results and natural complete problems, while computational classes such

as APX allow us to work with problems whose approximability is

well-understood. Our results give a computational ...
more >>>