Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MADHU SUDAN:
All reports by Author Madhu Sudan:

TR17-138 | 17th September 2017
Srikanth Srinivasan, Madhu Sudan

Local decoding and testing of polynomials over grids

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 >>>


TR17-081 | 2nd May 2017
Badih Ghazi, Madhu Sudan

The Power of Shared Randomness in Uncertain Communication

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 >>>


TR16-194 | 4th December 2016
Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan

The Optimality of Correlated Sampling

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 >>>


TR16-104 | 14th July 2016
Badih Ghazi, Pritish Kamath, Madhu Sudan

Decidability of Non-Interactive Simulation of Joint Distributions

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 >>>


TR15-087 | 30th May 2015
Badih Ghazi, Pritish Kamath, Madhu Sudan

Communication Complexity of Permutation-Invariant Functions

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 >>>


TR15-064 | 19th April 2015
Ilan Komargodski, Pravesh Kothari, Madhu Sudan

Communication with Contextual Uncertainty

Revisions: 1

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 >>>


TR15-043 | 2nd April 2015
Alan Guo, Elad Haramaty, Madhu Sudan

Robust testing of lifted codes with applications to low-degree testing

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 >>>


TR14-153 | 14th November 2014
Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

Communication with Imperfectly Shared Randomness

Revisions: 2

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 >>>


TR14-067 | 4th May 2014
Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

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 >>>


TR13-055 | 5th April 2013
David Gamarnik, Madhu Sudan

Limits of local algorithms over sparse random graphs

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 >>>


TR13-030 | 20th February 2013
Elad Haramaty, Noga Ron-Zewi, Madhu Sudan

Absolutely Sound Testing of Lifted Codes

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 >>>


TR12-166 | 25th November 2012
Elad Haramaty, Madhu Sudan

Deterministic Compression with Uncertain Priors

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 >>>


TR12-149 | 8th November 2012
Alan Guo, Swastik Kopparty, Madhu Sudan

New affine-invariant codes from lifting

Comments: 1

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 >>>


TR12-106 | 27th August 2012
Alan Guo, Madhu Sudan

New affine-invariant codes from lifting

Comments: 1

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 >>>


TR12-049 | 27th April 2012
Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan

Sparse affine-invariant linear codes are locally testable

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 >>>


TR12-048 | 25th April 2012
Alan Guo, Madhu Sudan

Some closure features of locally testable affine-invariant properties

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 >>>


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

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 >>>


TR11-079 | 9th May 2011
Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

On Sums of Locally Testable Affine Invariant Properties

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 >>>


TR11-059 | 15th April 2011
Elad Haramaty, Amir Shpilka, Madhu Sudan

Optimal testing of multivariate polynomials over small prime fields

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 >>>


TR11-005 | 20th January 2011
Madhu Sudan

Testing Linear Properties: Some general themes

Revisions: 1

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 >>>


TR10-116 | 21st July 2010
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Testing linear-invariant non-linear properties: A short report

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 >>>


TR10-108 | 9th July 2010
Eli Ben-Sasson, Madhu Sudan

Limits on the rate of locally testable affine-invariant codes

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 >>>


TR10-051 | 26th March 2010
Madhu Sudan

Invariance in Property Testing

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 >>>


TR09-126 | 26th November 2009
Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Locally Testable Codes Require Redundant Testers

Revisions: 3

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 >>>


TR09-086 | 2nd October 2009
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

Optimal testing of Reed-Muller codes

Revisions: 1

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 >>>


TR09-075 | 17th September 2009
Oded Goldreich, Brendan Juba, Madhu Sudan

A Theory of Goal-Oriented Communication

Revisions: 1 , Comments: 1

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 >>>


TR09-043 | 18th May 2009
Elena Grigorescu, Tali Kaufman, Madhu Sudan

Succinct Representation of Codes with Applications to Testing

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 >>>


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

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 >>>


TR08-095 | 31st October 2008
Brendan Juba, Madhu Sudan

Universal Semantic Communication II: A Theory of Goal-Oriented Communication

Revisions: 1

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 >>>


TR08-088 | 13th September 2008
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Testing Linear-Invariant Non-Linear Properties

Revisions: 1

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 >>>


TR08-033 | 21st March 2008
Elena Grigorescu, Tali Kaufman, Madhu Sudan

2-Transitivity is Insufficient for Local Testability

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 >>>


TR08-020 | 7th March 2008
Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

Decodability of Group Homomorphisms beyond the Johnson Bound

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 >>>


TR07-111 | 1st November 2007
Tali Kaufman, Madhu Sudan

Algebraic Property Testing: The Role of Invariance

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 >>>


TR07-084 | 4th September 2007
Brendan Juba, Madhu Sudan

Universal Semantic Communication I

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 >>>


TR07-060 | 11th July 2007
Tali Kaufman, Madhu Sudan

Sparse Random Linear Codes are Locally Decodable and Testable

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 >>>


TR06-118 | 2nd September 2006
Irit Dinur, Madhu Sudan, Avi Wigderson

Robust Local Testability of Tensor Products of LDPC Codes

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 >>>


TR04-093 | 9th November 2004
Oded Goldreich, Madhu Sudan, Luca Trevisan

From logarithmic advice to single-bit advice

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 >>>


TR04-060 | 22nd July 2004
Eli Ben-Sasson, Madhu Sudan

Simple PCPs with Poly-log Rate and Query Complexity

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 >>>


TR04-046 | 4th June 2004
Eli Ben-Sasson, Madhu Sudan

Robust Locally Testable Codes and Products of Codes

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 >>>


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

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 >>>


TR03-019 | 3rd April 2003
Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

Bounds on 2-Query Codeword Testing.

Revisions: 1


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 >>>


TR02-050 | 5th August 2002
Oded Goldreich, Madhu Sudan

Locally Testable Codes and PCPs of Almost-Linear Length

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 >>>


TR00-062 | 25th August 2000
Venkatesan Guruswami, Johan Hastad, Madhu Sudan

Hardness of approximate hypergraph coloring

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 >>>


TR00-061 | 14th August 2000
Prahladh Harsha, Madhu Sudan

Small PCPs with low query complexity

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 >>>


TR99-029 | 31st August 1999
Ilya Dumer, Daniele Micciancio, Madhu Sudan

Hardness of approximating the minimum distance of a linear code

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 >>>


TR99-025 | 2nd July 1999
Yonatan Aumann, Johan Hastad, Michael O. Rabin, Madhu Sudan

Linear Consistency Testing

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 >>>


TR98-074 | 16th December 1998
Madhu Sudan, Luca Trevisan, Salil Vadhan

Pseudorandom generators without the XOR Lemma

Revisions: 2


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 >>>


TR98-062 | 28th October 1998
Oded Goldreich, Dana Ron, Madhu Sudan

Chinese Remaindering with Errors

Revisions: 4 , Comments: 1

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 >>>


TR98-060 | 8th October 1998
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

Learning polynomials with queries -- The highly noisy case.

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 >>>


TR98-043 | 27th July 1998
Venkatesan Guruswami, Madhu Sudan

Improved decoding of Reed-Solomon and algebraic-geometric codes.

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 >>>


TR98-040 | 24th July 1998
Madhu Sudan, Luca Trevisan

Probabilistically checkable proofs with low amortized query complexity

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 >>>


TR98-017 | 29th March 1998
Oded Goldreich, Madhu Sudan

Computational Indistinguishability: A Sample Hierarchy.


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 >>>


TR98-008 | 15th January 1998
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

Proof verification and the hardness of approximation problems.


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 >>>


TR97-003 | 29th January 1997
Sanjeev Arora, Madhu Sudan

Improved low-degree testing and its applications


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 >>>


TR96-064 | 11th December 1996
Sanjeev Khanna, Madhu Sudan, Luca Trevisan

Constraint satisfaction: The approximability of minimization problems.


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 >>>


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


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 >>>


TR96-028 | 9th April 1996
Sanjeev Khanna, Madhu Sudan

The Optimization Complexity of Constraint Satisfaction Problems

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 >>>


TR95-024 | 23rd May 1995
Mihir Bellare, Oded Goldreich, Madhu Sudan

Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

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 >>>


TR95-023 | 16th May 1995
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

On Syntactic versus Computational views of Approximability

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 >>>




ISSN 1433-8092 | Imprint