Optimal Testing of Reed-Muller Codes (2009)
Bhattacharyya, Arnab, Kopparty, Swastik, Schoenebeck, Grant, Sudan, Madhu, Zuckerman, David
We consider the problem of testing if a given function $f : \F_2^n \to \F_2$ is close to any degree $d$ polynomial in $n$ variables, also known as the Reed-Muller testing problem. Alon et al....
Succinct Representation of Codes with Applications to Testing (2009)
Grigorescu, Elena, Kaufman, Tali, Sudan, Madhu
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...
Amplifying Collision Resistance: A Complexity-Theoretic Treatment (2009)
Ran Canetti, Ron Rivest, Madhu Sudan, Luca Trevisan, Salil Vadhan, Hoeteck Wee
Abstract. We initiate a complexity-theoretic treatment of hardness amplification for collision-resistant hash functions, namely the transformation of weakly collision-resistant hash functions into...
Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers (2009)
Dvir, Zeev, Kopparty, Swastik, Saraf, Shubhangi, Sudan, Madhu
We extend the "method of multiplicities" to get the following results, of interest in combinatorics and randomness extraction. We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector...
Probabilistically Checkable Proofs (2009)
Probabilistically checkable proofs (PCPs) are arguably fascinating objects. They offer a certain robustness to the logical process of verification that may not have been suspected before. While the...
Testing Linear-Invariant Non-Linear Properties (2009)
Bhattacharyya, Arnab, Chen, Victor, Sudan, Madhu, Xie, Ning
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...
Testing Linear-Invariant Non-Linear Properties (2009)
Bhattacharyya, Arnab, Chen, Victor, Sudan, Madhu, Xie, Ning
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...
Testing Linear-Invariant Non-Linear Properties (2009)
Bhattacharyya, Arnab, Chen, Victor, Sudan, Madhu, Xie, Ning
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...
Probabilistically Checkable Proofs (2009)
Probabilistically checkable proofs (PCPs) are arguably fascinating objects. They offer a certain robustness to the logical process of verification that may not have been suspected before. While the...
Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers (2009)
Zeev Dvir, Shubhangi Saraf, Madhu Sudan
We extend the “method of multiplicities ” to get the following results, of interest in combinatorics and randomness extraction. 1. We show that every Kakeya set in F n q, the n-dimensional vector...
Amplifying Collision Resistance: A Complexity-Theoretic Treatment (2008)
Ran Canetti, Ron Rivest, Madhu Sudan, Luca Trevisan, Salil Vadhan, Hoeteck Wee
Abstract. We initiate a complexity-theoretic treatment of hardness amplification for collision-resistant hash functions, namely the transformation of weakly collision-resistant hash functions into...
Amplifying Collision Resistance: A Complexity-Theoretic Treatment (2008)
Ran Canetti, Madhu Sudan, Luca Trevisan, Salil Vadhan, Hoeteck Wee
Abstract. We initiate a complexity-theoretic treatment of hardness amplification for collision-resistant hash functions, namely the transformation of weakly collision-resistant hash functions into...
Testing Linear-Invariant Non-Linear Properties (2008)
Bhattacharyya, Arnab, Chen, Victor, Sudan, Madhu, Xie, Ning
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...
Improved lower bound on the size of Kakeya sets over finite fields (2008)
Saraf, Shubhangi, Sudan, Madhu
In a recent breakthrough, Dvir showed that every Kakeya set in $\F^n$ must be of cardinality at least $c_n |\F|^n$ where $c_n \approx 1/n!$. We improve this lower bound to $\beta^n |\F|^n$ for a...
Irit Dinur, Madhu Sudan, Avi Wigderson
Abstract. Given two binary linear codes R and C, their tensor product R⊗C consists of all matrices with rows in R and columns in C. We analyze the “robustness ” of the following test for this...
Abstract Guessing Secrets Efficiently via List Decoding (Extended Abstract) (2008)
Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan
We consider the guessing secrets problem defined by
Talk given at workshop on Algebraic Methods in Complexity Theory (2008)
On the role of algebra in the efficient verification of proofs
Amplifying Collision Resistance: A Complexity-Theoretic Treatment (2008)
Ran Canetti, Ron Rivest, Madhu Sudan, Luca Trevisan, Salil Vadhan, Hoeteck Wee
Abstract. We initiate a complexity-theoretic treatment of hardness amplification for collision-resistant hash functions, namely the transformation of weakly collision-resistant hash functions into...
Decodability of Group Homomorphisms beyond the Johnson Bound (2008)
Irit Dinur, Elena Grigorescu, 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...
Improved lower bound on the size of Kakeya sets over finite fields (2008)
In a recent breakthrough, Dvir showed that every Kakeya set in F n must be of cardinality at least cn|F | n where cn ≈ 1/n!. We improve this lower bound to β n |F | n for a constant β> 0. This...
Improved lower bound on the size of Kakeya sets over finite fields (2008)
In a recent breakthrough, Dvir showed that every Kakeya set in F n must be of cardinality at least cn|F | n where cn ≈ 1/n!. We improve this lower bound to β n |F | n for a constant β> 0. This...
Emerging networking technologies tend to be introduced complete with protocols for managing their own resources, for example, routing, resource reservation, and signaling. Each network offers a...
Multicasting Layered Multimedia Streams In An Atm Environment (2007)
HMC (Heterogeneous MultiCast) [10] is a communication paradigm which uses the technique of partitioning data streams into a hierarchy of layers (one base layer and several enhancement layers) and...
Amos Beimel, Yevgeniy Dodis, John Dunagan, Venkatesan Guruswami, Prahladh Harsha, Adam Klivans, ...
much more careful and clear than I was. Thanks in particular to Salil Vadhan who lectured on November 9, 1998, two hours after Roshni Malhaar was born. These notes are by no means polished....
In this lecture we will see how we can \correct " more errors. More correctly, we will redene the \correction " problem, and then how to correct more errors in this denition.
On Representations of Algebraic-Geometric Codes for List Decoding (2007)
Venkatesan Guruswami, Madhu Sudan
Abstract. We show that all algebraic-geometric codes possess a succinct representation that allows for the list decoding algorithms of [15, 7] to run in polynomial time. We do this by presenting a...
Alok Aggarwal, Amotz Bar-noy, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
This paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical ber is utilized by partitioning it into several...
Probabilistically Checkable Proofs (2007)
Madhu Sudan, Scribe Venkatesan Guruswami
1. Overview The goal of this four part lecture series is to present (the important ideas and most details of) the proof of the following striking assertion: There is a format of writing
These notes outline how a rational function interpolation problem may be reduced (in nearly linear time) to a \rational approximation problem". The writeup assumes that polynomial...
Error-Correction Diameter (2007)
Decoding Reed, Solomon Codes, Madhu Sudan
We describe a new algorithm for the decoding of Reed Solomon codes. This algorithm was originally described in [12]. While the algorithm presented in this article is the same, the presentation is...
Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets (2007)
Eli Ben-sasson, Madhu Sudan, Cambridge Ma, Salil Vadhan, Avi Wigderson
We present the first explicit construction of Probabilistically Checkable Proofs (PCPs) and Locally Testable Codes (LTCs) of fixed constant query complexity which have almostlinear (= n ) size. Such...
Algebraic Property Testing: The Role of Invariance (2007)
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...
Sparse random linear codes are locally decodable and testable (2007)
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...
On Dinur’s Proof of the PCP Theorem (2007)
Jaikumar Radhakrishnan, Madhu Sudan
Probabilistically checkable proofs are proofs that can be checked probabilistically by reading very few bits of the proof. In the early 1990s, it was shown that proofs could be transformed into...
Towards Universal Semantic Communication (2007)
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...
Towards Universal Semantic Communication (Version 0- Very Preliminary) (2007)
Is is 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...
Towards Universal Semantic Communication (2007)
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...
Towards Universal Semantic Communication (Version 0- Very Preliminary) (2007)
Is is 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...
On Dinur’s Proof of the PCP Theorem (2006)
Jaikumar Radhakrishnan, Madhu Sudan
Probabilistically checkable proofs are proofs that can checked probabilistically by reading very few bits of the proof. In the early 1990’s, it was shown that proofs could be transformed into...
Local decoding and testing for homomorphisms (2006)
Abstract. Locally decodable codes (LDCs) have played a central role in many recent results in theoretical computer science. The role of finite fields, and in particular, low-degree polynomials over...
Short PCPs with Polylog Query Complexity (2006)
We give constructions of probabilistically checkable proofs (PCPs) of length n · polylog n proving satisfiability of circuits of size n that can verified by querying polylog n bits of the proof. We...
Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan
We study the problem of designing seller optimal auctions. Prior to this work, the only previously known auctions that are approximately optimal in worst case employ randomization. Our main result is...
Optimal error correction against computationally bounded noise (2005)
Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson
Abstract. For computationally bounded adversarial models of error, we construct appealingly simple, efficient, cryptographic encoding and unique decoding schemes whose error-correction capability is...
Optimal error correction against computationally bounded noise (2005)
Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson
Abstract. For computationally bounded adversarial models of error, we construct appealingly simple, efficient, cryptographic encoding and unique decoding schemes whose error-correction capability is...
Distributed computing with imperfect randomness (2005)
Shafi Goldwasser, Madhu Sudan, Vinod Vaikuntanathan
Abstract. Randomness is a critical resource in many computational scenarios, enabling solutions where deterministic ones are elusive or even provably impossible. However, the randomized solutions to...
Guruswami, Venkatesan., Sudan, Madhu.
"Dissertation ... written under the supervision of Madhu Sudan and submitted to MIT in August 2001"--P. xi.
Robust locally testable codes and products of codes (2004)
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...
Short PCPs verifiable in polylogarithmic time (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
We show that every language in NP has a probabilistically checkable proof of proximity (i.e., proofs asserting that an instance is “close ” to a member of the language), where the verifier’s...
Robust PCPs of proximity, shorter PCPs and applications to coding (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan
Abstract. We continue the study of the trade-off between the length of probabilistically checkable proofs (PCPs) and their query complexity, establishing the following main results (which refer to...
Robust PCPs of proximity, shorter PCPs and applications to coding (2004)
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):...
Robust PCPs of proximity, shorter PCPs and applications to coding (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
Abstract 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...
Short PCPs verifiable in polylogarithmic time (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
We show that every language in NP has a probabilistically checkable proof of proximity (i.e., proofs asserting that an instance is “close ” to a member of the language), where the verifier’s...
Short PCPs verifiable in polylogarithmic time (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
We show that every language in NP has a probabilistically checkable proof of proximity (i.e., proofs asserting that an instance is “close ” to a member of the language), where the verifier’s...
Short PCPs verifiable in polylogarithmic time (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
We show that every language in NP has a probabilistically checkable proof of proximity (i.e., proofs asserting that an instance is “close ” to a member of the language), where the verifier’s...
Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets (2003)
Eli Ben-sasson, Madhu Sudan, Cambridge Ma, Salil Vadhan, Avi Wigderson
We present the first explicit construction of Probabilistically Checkable Proofs (PCPs) and Locally Testable Codes (LTCs) of fixed constant query complexity which have almostlinear (= n ) size. Such...
Harmonic Broadcasting is Bandwidth-Optimal Assuming Constant Bit Rate (2002)
Abstract. Harmonic broadcasting was introduced by Juhn and Tseng in 1997 as a way to reduce the bandwidth requirements required for video-on-demand broadcasting. In this correspondence, we note that...
Harmonic Broadcasting is Bandwidth-Optimal Assuming Constant Bit Rate (2002)
Abstract. Harmonic broadcasting was introduced by Juhn and Tseng in 1997 as a way to reduce the bandwidth requirements required for video-on-demand broadcasting. In this paper, we note that harmonic...
she might take is to compile a set A of her favorite movies and publish it in a concealed form.For instance, Alice might post to a Web newsgroup a ciphertext
Abstract. We describe a simple and novel cryptographic construction that we refer to as a fuzzy vault. A player Alice may place a secret value κ in a fuzzy vault and “lock ” it using a set A of...
Abstract. We describe a simple and novel cryptographic construction that we refer to as a fuzzy vault. A player Alice may place a secret value κ in a fuzzy vault and “lock ” it using a set A of...
On representations of algebraicgeometric codes (2001)
Venkatesan Guruswami, Madhu Sudan
We show that all algebraic-geometric codes possess a succinct representation that allows for the list decoding algorithms of [9, 6] to run in polynomial time. We do this by presenting a root-finding...
Extensions to the Johnson bound (2001)
Venkatesan Guruswami, Madhu Sudan
We present extensions of some recent geometric proofs of the well-known Johnson bound. Our extensions apply to arbitrary alphabets (while previous proofs were given only for the binary case). Our...
Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms', Lect (2001)
Abstract. Over the past ve years a number of algorithms decoding some well-studied error-correcting codes far beyond their \error-correcting radii " have been developed. These algorithms,...
Coding theory: Tutorial and survey (2001)
Coding theory has played a central role in the theoretical computer science. Computer scientists have long exploited notions, constructions, theorems and techniques of coding theory. More recently,...
The approximability of constraint satisfaction problems (2001)
Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson
Abstract. We study optimization problems that may be expressed as "Boolean constraint satisfaction problems. " An instance of a Boolean constraint satisfaction problem is given by m...
On representations of algebraicgeometric codes (2001)
Venkatesan Guruswami, Madhu Sudan
We show that all algebraic-geometric codes possess a succinct representation that allows for the list decoding algorithms of [9, 6] to run in polynomial time. We do this by presenting a root-finding...
Coding theory: Tutorial and survey (2001)
Abstract Coding theory has played a central role in the theoretical computer science. Computer scientists have long exploited notions, constructions, theorems and techniques of coding theory. More...
The Approximability of Constraint Satisfaction Problems (2000)
Khanna, Sanjeev, Sudan, Madhu, Trevisan, Luca, Williamson, David P
We study optimization problems that may be expressed as "Boolean constraint satisfaction problems". An instance of a Boolean constraint satisfaction problem is given by m constraints applied to n...
Small PCPs with low query complexity (2000)
Abstract. 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...
Combinatorial bounds for list decoding (2000)
Venkatesan Guruswami, Johan Hastad, Madhu Sudan, David Zuckerman
Abstract--- Informally, an error-correcting code has "nice " listdecodability properties if every Hamming ball of "large " radius has a "small "...
Combinatorial bounds for list decoding (2000)
Venkatesan Guruswami, Johan Hastad, Madhu Sudan, David Zuckerman
Abstract--- Informally, an error-correcting code has "nice " listdecodability properties if every Hamming ball of "large " radius has a "small "...
Small PCPs with low query complexity (2000)
Abstract. 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...
List decoding: Algorithms and applications (2000)
Over the years coding theory and complexity theory have benefited from a number of mutually enriching connections. This article focuses on a new connection that has emerged between the two topics in...
Small PCPs with low query complexity (2000)
Abstract. 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...
Combinatorial bounds for list decoding (2000)
Venkatesan Guruswami, Johan Hastad, Madhu Sudan, David Zuckerman
Abstract--- Informally, an error-correcting code has "nice " listdecodability properties if every Hamming ball of "large " radius has a "small "...
Hardness of Approximate Hypergraph Coloring (2000)
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...
"Soft-decision" Decoding of Chinese Remainder Codes (2000)
Venkatesan Guruswami, Amit Sahai, Madhu Sudan
Given n relatively prime integers p 1 < < pn and an integer k < n, the Chinese Remainder Code, CRT p1 ;:::;p n ;k , has as its message space M = f0; : : : ; Q k i=1 p i 1g, and encodes a...
"Soft-decision" Decoding of Chinese Remainder Codes (2000)
Venkatesan Guruswami, Amit Sahai, Madhu Sudan
Given n relatively prime integers p 1 ! \Delta \Delta \Delta ! pn and an integer k ! n, the Chinese Remainder Code, CRT p1 ;:::;p n ;k , has as its message space M = f0; : : : ; Q k i=1 p i \Gamma...
List Decoding Algorithms for Certain Concatenated Codes (2000)
Venkatesan Guruswami, Madhu Sudan
We give efficient (polynomial-time) list-decoding algorithms for certain families of error-correcting codes obtained by "concatenation ". Specifically, we give list-decoding algorithms for...
Hardness of Approximate Hypergraph Coloring (2000)
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...
Random Walks with "Back Buttons" (2000)
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
We introduce backoff processes, an idealized stochastic model of browsing on the world-wide web, which incorporates both hyperlink traversals and use of the "back button." With some...
List Decoding Algorithms for Certain Concatenated Codes (2000)
Venkatesan Guruswami, Madhu Sudan
We give efficient (polynomial-time) list-decoding algorithms for certain families of error-correcting codes obtained by "concatenation". Specifically, we give list-decoding algorithms for...
Gadgets, Approximation, and Linear Programming (2000)
Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
We present a linear-programming based method for finding "gadgets", i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in...
Hardness of approximating the minimum distance of a linear code (1999)
Ilya Dumer, Daniele Micciancio, Madhu Sudan
Abstract—We show that the minimum distance of a linear code is not approximable to within any constant factor in random polynomial time (RP), unless nondeterministic polynomial time (NP) equals RP....
Computational Indistinguishability: A Sample Hierarchy (1999)
We consider the existence of pairs of probability ensembles which may be efficiently distinguished from each other given k samples but cannot be efficiently distinguished given k 0 samples. It is...
Approximability of Optimization Problems 8 - Hardness of Approximation (1999)
F12.38> s.t. no fewer than k 0 and no more than gk 0 clauses can be simultaneously satisfied. Finally, g-approximate MAX-SAT problem is to find a satisfying assignment that satisfies at least...
Linear Consistency Testing (1999)
Yonatan Aumann, Johan Hastad, 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...
Gadgets, Approximation, and Linear Programming (1999)
Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
We present a linear programming-based method for finding "gadgets", i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in...
Hardness of Approximating the Minimum Distance of a Linear Code (1999)
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...
Pseudorandom generators without the XOR Lemma (1999)
Madhu Sudan, Luca Trevisan, Salil Vadhan
Impagliazzo and Wigderson [IW97] have recently shown that if there exists a decision problem solvable in time 2 O(n) and having circuit complexity 2 \Omega\Gamma n) (for all but finitely many n) then...
6.893 Approximability of Optimization Problems (1999)
Madhu Sudan, Lecturer Madhu, Sudan Scribe, Prahladh Harsha
airs (s i ; t i ) Objective: min P (i;j)2E d i;j Let the optimal solution of this LP problem be denoted by LP opt and let d i;j denote the value of the variables at the optimal. In order to obtain an...
Approximability of Optimization Problems 10 - Error Correcting Code (ECC) (1999)
1.52> Pr[V \Pi 0 (x; R) accepts] (1 \Gamma ffl)(1 \Gamma 3%) :97 \Gamma ffl For any x = 2 L, such a \Pi 0 does not exist. 10-1 1.2 Parameters of ECCs Let, C = A collection of strings (or vectors)...
Pseudorandom generators without the XOR Lemma (Extended Abstract) (1999)
Madhu Sudan, Luca Trevisan, Salil Vadhan
] Madhu Sudan y Luca Trevisan z Salil Vadhan x Abstract Impagliazzo and Wigderson [IW97] have recently shown that if there exists a decision problem solvable in time 2 O(n) and having circuit...
Computational Indistinguishability: A Sample Hierarchy (1999)
We consider the existence of pairs of probability ensembles which may be efficiently distinguished from each other given k samples but cannot be efficiently distinguished given k 0 ! k samples. It is...
Hardness of approximating the minimum distance of a linear code (1999)
Ilya Dumer, Daniele Micciancio, Madhu Sudan
We show that the minimum distance d of a linear code is not approximable to within any constant factor in random polynomial time (RP), unless NP (nondeterministic polynomial time) equals RP. We also...
Free bits, PCPs, and non-approximability -- towards tight results (1998)
Mihir Bellare, Oded Goldreich, Madhu Sudan
The first part of this paper presents new proof systems and improved non-approximability results. In particular we present a proof system for NP using logarithmic randomness and two amortized free...
Private Information Retrieval \Lambda (1998)
Benny Chory, Oded Goldreichz, Eyal Kushilevitzx, Madhu Sudan
Abstract Publicly accessible databases are an indispensable resource for retrieving up to date information. But they also pose a significant risk to the privacy of the user, since a curious database...
On Syntactic Versus Computational Views of Approximability (1998)
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani
.<F3.804e+05> We attempt to reconcile the two distinct views of approximation classes:<F3.45e+05> syntactic<F3.804e+05> and<F3.45e+05><F3.804e+05> computational....
Chinese Remaindering with Errors (1998)
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 ! Q k i=1 p i . Thus the...
A tight characterization of NP with 3 query PCPs (1998)
Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan
It is known that there exists a PCP characterization of NP where the verifier makes 3 queries and has a one-sided error that is bounded away from 1; and also that 2 queries do not suffice for such a...
Pseudorandom generators without the XOR Lemma (1998)
Madhu Sudan, Luca Trevisan, Salil Vadhan
Impagliazzo and Wigderson [IW97] have recently shown that if there exists a decision problem solvable in time 2 O(n) and having circuit complexity 2 \Omega\Gamma n) (for all but finitely many n) then...
Probabilistically Checkable Proofs with Low Amortized Query Complexity (1998)
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...
Chinese Remaindering with Errors (1998)
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 ! Q k i=1 p i . Thus the...
Probabilistically Checkable Proofs with Low Amortized Query Complexity (1998)
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...
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes (1998)
Venkatesan Guruswami, Madhu Sudan
Given an error-correcting code over strings of length n and an arbitrary input string also of length n, the list decoding problem is that of finding all codewords within a specified Hamming distance...
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes (1998)
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...
A tight characterization of NP with 3 query PCPs (1998)
Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan
It is known that there exists a PCP characterization of NP where the verifier makes 3 queries and has a one-sided error that is bounded away from 1; and also that 2 queries do not suffice for such a...
Probabilistic Verification of Proofs (1998)
. Recent research in the theory of computing has led to the following intriguing result. "There exists a probabilistic verifier for proofs of mathematical assertions that looks at a proof in...
Adversarial Queueing Theory (1998)
Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
this paper a request is a path specifying the route followed by a packet. We say that the adversary injects a set of packets when it generates a set of requested paths. We restrict ourselves to the...
Reconstructing Algebraic Functions from Mixed Data (1998)
Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan
.<F3.822e+05> We consider a variant of the traditional task of explicitly reconstructing algebraic functions from black box representations. In the traditional setting for such problems, one is...
Pseudorandom generators without the XOR Lemma (1998)
Madhu Sudan, Luca Trevisan, Salil Vadhan
Impagliazzo and Wigderson [IW97] have recently shown that if there exists a decision problem solvable in time 2 O(n) and having circuit complexity 2 \Omega\Gamma n) (for all but finitely many n) then...
Learning Polynomials With Queries: The Highly Noisy Case (1998)
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
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 on a tiny but...
Free bits, PCPs, and nonapproximability -- towards tight results (1998)
Mihir Bellare, Oded Goldreich, Madhu Sudan
This paper continues the investigation of the connection between probabilistically checkable proofs (PCPs) and the approximability of NP-optimization problems. The emphasis is on proving tight...
Private Information Retrieval \Lambda (1997)
Benny Chory, Oded Goldreichz, Eyal Kushilevitzx, Madhu Sudan
Abstract Publicly accessible databases are an indispensable resource for retrieving up to date information. But they also pose a significant risk to the privacy of the user, since a curious database...
Algorithmic issues in coding theory (1997)
The goal of this article is to provide a gentle introduction to the basic definitions, goals and constructions in coding theory. In particular we focus on the algorithmic tasks tackled by the theory....
Decoding of Reed-Solomon codes beyond the error-correction bound (1997)
We describe a new algorithm for the decoding of Reed Solomon codes. This algorithm was originally described in [12]. While the algorithm presented in this article is the same, the presentation is...
Decoding of Reed-Solomon codes beyond the error-correction bound (1997)
We describe a new algorithm for the decoding of Reed Solomon codes. This algorithm was originally described in [12]. While the algorithm presented in this article is the same, the presentation is...
A statistical perspective on data mining (1997)
Jonathan Hosking, Edwin Pednault, Madhu Sudan
Data mining can be regarded as a collection of methods for drawing inferences from data. The aims of data mining, and some of its methods, overlap with those of classical statistics. However, there...
Decoding of Reed-Solomon codes beyond the error-correction bound (1997)
We present a randomized algorithm which takes as input n distinct points f(x i; y i)g n i=1 from F F (where F is a eld) and integer parameters t and d and returns a list of all univariate polynomials...
Algorithmic issues in coding theory (1997)
Abstract. The goal of this article is to provide a gentle introduction to the basic denitions, goals and constructions in coding theory. In particular we focus on the algorithmic tasks tackled by the...
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 : f0; 1g k !...
A Statistical Perspective on Data Mining (1997)
J. Hosking, E. Pednault, M. Sudan, Madhu Sudan
Data mining can be regarded as a collection of methods for drawing inferences from data. The aims of data mining, and some of its methods, overlap with those of classical statistics. However, there...
HMC: A system for Heterogeneous Multicast over ATM (1997)
Nachum Shacham Madhu, Madhu Sudan, Michael Brown
A multimedia session normally consists of participants which differ widely in their preferences and available resources (like access bandwidth and processing capacity) . Heterogeneous MultiCast (HMC)...
Conducting a Multiparty Multimedia Session over ATM using Hierarchically Encoded Data (1997)
Nachum Shacham, Madhu Sudan, Michael Brown
Heterogeneous MultiCast (HMC) is a communication paradigm for distributing real-time streams among multiple session participants that have different constraints and reception preferences. In HMC,...
Decoding of Reed Solomon codes beyond the error-correction bound (1997)
We present a randomized algorithm which takes as input n distinct points f(x i ; y i )g n i=1 from F \Theta F (where F is a field) and integer parameters t and d and returns a list of all univariate...
Emerging networking technologies tend to be introduced complete with their own protocols for resource management; for example, routing, resource reservation, and signaling. Each network offers a...
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 : f0; 1g k !...
Improved Low-Degree Testing and Its Applications (1997)
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...
Gadgets, Approximation, and Linear Programming (1997)
Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
We present a linear-programming based method for finding "gadgets", i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in...
Algorithmic Issues in Coding Theory (1997)
The goal of this article is to provide a gentle introduction to the basic definitions, goals and constructions in coding theory. In particular we focus on the algorithmic tasks tackled by the theory....
Constraint Satisfaction: The Approximability of Minimization Problems (1997)
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...
Reconstructing Algebraic Functions from Mixed Data (1997)
Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan
We consider a variant of the traditional task of explicitly reconstructing algebraic functions from black box representations. In the traditional setting for such problems, one is given access to an...
Improved Low-Degree Testing and Its Applications (1997)
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...
Efficient routing in optical networks (1996)
Alok Aggarwal, Amotz Bar-noy, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
This paper studies the problems of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into...
Efficient Routing in Optical Networks (1996)
Alok Aggarwal, Amotz Bar-noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
This paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into...
Private Information Retrieval (1996)
Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan
Publicly accessible databases are an indispensable resource for retrieving up to date information. But they also pose a significant risk to the privacy of the user, since a curious database operator...
Guaranteeing Fair Service to Persistent Dependent Tasks (1996)
Amotz Bar-noy, Alain Mayer, Baruch Schieber, Madhu Sudan
We introduce a new scheduling problem that is motivated by applications in the area of access and flow-control in high-speed and wireless networks. An instance of the problem consists of a set of...
The Optimization Complexity of Structure Maximization Problems (1996)
Sanjeev Khanna, Madhu Sudan, David P. Williamson
In 1978, Schaefer [18] considered a subclass of languages in NP. This class, which generalizes the satisfiability problem, has as instances general constraints (of finite arity) placed on a...
Gadgets, approximation, and linear programming (1996)
Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
Abstract. We present a linear programming-based method for finding “gadgets, ” i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key...
Efficient checking of polynomials and proofs and the hardness of approximation problems / (1995)
Based on the author's Ph. D. thesis, University of California, Berkeley, 1993.
A reliable dissemination protocol for interactive collaborative applications (1995)
Rajendra Yavatkar, James Gri Oen, Madhu Sudan
The widespread availability of networked multimedia workstations and PCs has caused a signi cant interest in the use of collaborative multimedia applications. Examples of such applications include...
A reliable dissemination protocol for interactive collaborative applications (1995)
Rajendra Yavatkar, James Griffioen, Madhu Sudan
The widespread availability of networked multimedia workstations and PCs has caused a significant interest in the use of collaborative multimedia applications. Examples of such applications include...
Private Information Retrieval (1995)
Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan
: We describe schemes that enable a user to access k replicated copies of a database (k 2) and privately retrieve information stored in the database. This means that each individual database gets no...
Free Bits, PCPs and Non-Approximability - Towards Tight Results (3rd Version) (1995)
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...
A Reliable Dissemination Protocol for Interactive Collaborative Applications (1995)
Rajendra Yavatkar, James Griffioen, Madhu Sudan
The widespread availability of networked multimedia workstations and PCs has caused a significant interest in the use of collaborative multimedia applications. Examples of such applications include...
Some Improvements to Total Degree Tests (1995)
A low-degree test is a collection of simple, local rules for checking the proximity of an arbitrary function to a lowdegree polynomial. Each rule depends on the function's values at a small...
Learning Polynomials With Queries: The Highly Noisy Case (1995)
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
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 on a tiny but...
Adversarial Queueing Theory (1995)
Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queueing aimed at addressing some of the restrictions inherent in probabilistic...
A geometric approach to betweenness (1995)
Abstract. An input to the betweenness problem contains m constraints over n real variables (points). Each constraint consists of three points, where one of the points is specified to lie inside the...
Free Bits, PCPs and Non-Approximability - Towards Tight Results (3rd Version) (1995)
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...
Efficient routing and scheduling algorithms for optical networks (1994)
Alok Aggarwal, Amotz Bar-noy, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
This paper studies the problems of dedicating routes and scheduling transmissions in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by...
On Syntactic versus Computational Views of Approximability (1994)
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani, Min F
We attempt to reconcile the two distinct views of approximation classes: syntactic and computational. Syntactic classes such as MAX SNP permit structural results and have natural complete problems,...
Approximate Graph Coloring by Semidefinite Programming (1994)
David Karger, Rajeev Motwani, Madhu Sudan
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on n vertices with...
On the Role of Algebra in the Efficient Verification of Proofs (1994)
This article extracts the elements of algebra that play a central role in the design of efficient probabilistic verifiers or "probabilistically checkable proof systems (PCPs)". The main...
Computing Roots of Graphs is Hard (1994)
The square of an undirected graph G is the graph G 2 on the same vertex set such that there is an edge between two vertices in G 2 if and only if they are at distance at most 2 in G. The k'th...
Motion Planning on a Graph (1994)
Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki
We are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the vertices; this vertex is labeled s. Each of several other vertices contains a single movable...
On Syntactic versus Computational Views of Approximability (1994)
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 permit structural results and have natural complete problems,...
On Syntactic versus Computational Views of Approximability (1994)
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 permit structural results and have natural complete problems,...
Improved Non-Approximability Results (1994)
We indicate strong non-approximability factors for central problems: N 1=4 for Max Clique; N 1=10 for Chromatic Number; and 66=65 for Max 3SAT. Underlying the Max Clique result is a proof system in...
Approximate Graph Coloring by Semidefinite Programming (1994)
David Karger, Rajeev Motwani, Madhu Sudan
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with...
Approximate Graph Coloring by Semidefinite Programming (1994)
David Karger, Rajeev Motwani, Madhu Sudan
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with...
The Minimum Latency Problem (1994)
Avrim Blum, Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar Raghavan, Madhu Sudan
We are given a set of points p 1 ; : : : ; p n and a symmetric distance matrix (d ij ) giving the distance between p i and p j . We wish to construct a tour that minimizes P n i=1 `(i), where `(i) is...
Robust Characterizations of Polynomials and Their Applications to Program Testing (1993)
Rubinfeld, Ronitt, Sudan, Madhu
The study of self-testing and self-correcting programs leads to the search for robust characterizations of functions. Here we make this notion precise and show such a characterization for...
Proof verification and hardness of approximation problems (1992)
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 constant number of bits in the proof. If...
Proof Verification and Hardness of Approximation Problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
The class PCP(f(n); g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that uses O(f(n)) random bits, queries O(g(n)) bits of its oracle and...
Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems (1992)
Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems by Madhu Sudan Doctor of Philosophy in Computer Science University of California at Berkeley Professor Umesh V....
Proof verification and hardness of approximation problems (1992)
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 constant number of bits in the proof. If...
Self-Testing/Correcting for Polynomials and for Approximate Functions (1991)
Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson
The study of self-testing/correcting programs was introduced in [8] in order to allow one to use program P to compute function f without trusting that P works correctly. A self-tester for f estimates...
Connectivity Properties of Matroids (1989)
The bases-exchange graph of a matroid is the graph whose vertices are the bases of the matroid, and two bases are connected by an edge if and only if one can be obtained from the other by the...