Madhur Tulsiani

STOC Conference 2025 Conference Paper

Explicit Codes Approaching Generalized Singleton Bound using Expanders

• Fernando Granha Jeronimo
• Tushant Mittal
• Shashank Srivastava
• Madhur Tulsiani

We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of O (1/є). In contrast to existing explicit constructions of codes achieving list decoding capacity, our arguments do not rely on algebraic structure but utilize simple combinatorial properties of expander graphs. Our construction is based on a celebrated distance amplification procedure due to Alon, Edmonds, and Luby [FOCS’95], which transforms any high-rate code into one with near-optimal rate-distance tradeoff. We generalize it to show that the same procedure can be used to transform any high-rate code into one that achieves list decoding capacity. Our proof can be interpreted as a ”local-to-global” phenomenon for (a slight strengthening of) the generalized Singleton bound. Using this construction, for every R , є ∈ (0,1) and k ∈ ℕ + , we obtain an explicit family of rate R codes C ⊆ Σ n that achieve the є-relaxed generalized Singleton bound. The alphabet size of these codes is a constant depending only on є and k , and they can be list decoded up to radius k −1/ k · (1− R −є), in time n O k ,є (1) with a list of size k −1. As a corollary of our result, we also obtain the first explicit construction of LDPC codes achieving list decoding capacity, and in fact arbitrarily close to the generalized Singleton bound.

FOCS Conference 2025 Conference Paper

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time

• Shashank Srivastava
• Madhur Tulsiani

We give a new framework based on graph regularity lemmas, for list decoding and list recovery of codes based on spectral expanders. Using existing algorithms for computing regularity decompositions of sparse graphs in (randomized) near-linear time, and appropriate choices for the constant-sized inner/base codes, we prove the following: –Expander-based codes constructed using the distance amplification technique of Alon, Edmonds and Luby [FOCS 1995] can be list decoded to capacity in near-linear time. By known results, the output list is optimal up to constant factors. –The same codes of Alon, Edmonds and Luby, can also be list recovered to capacity in near-linear time, with constant-sized output lists. –The Tanner code construction of Sipser and Spielman [IEEE Trans. Inf. Theory 1996] can be list decoded to its distance in near-linear time, with constant-sized output lists. Our results imply novel combinatorial as well as algorithmic bounds for each of the above explicit constructions. All of these bounds are obtained via combinatorial rigidity phenomena, proved using (weak) graph regularity. The regularity framework allows us to lift the list decoding and list recovery properties for the local base codes, to the global codes obtained via the above constructions.

FOCS Conference 2024 Conference Paper

Efficient Certificates of Anti-Concentration Beyond Gaussians

• Ainesh Bakshi
• Pravesh K. Kothari
• Goutham Rajendran
• Madhur Tulsiani
• Aravindan Vijayaraghavan

A set of high dimensional points X $= \{x_{1}, x_{2}, \ldots, x_{n}\}\subseteq \mathbb{R}^{d}$ in isotropic position is said to be $\delta$ -anti concentrated if for every direction $v$, the fraction of points in $X$ satisfying $\left|\left\langle x_i, v\right\rangle\right| \leqslant \delta$ is at most $O(\delta)$. Motivated by applications to list-decodable learning and clustering, three recent works [7], [44], [71] considered the problem of constructing efficient certificates of anti-concentration in the average case, when the set of points X corresponds to samples from a Gaussian distribution. Their certificates played a crucial role in several subsequent works in algorithmic robust statistics on list-decodable learning and settling the robust learnability of arbitrary Gaussian mixtures. Unlike related efficient certificates of concentration properties that are known for wide class of distri-butions [52], the aforementioned approach has been limited only to rotationally invariant distributions (and their affine transformations) with the only prominent example being Gaussian distributions. This work presents a new (and arguably the most natural) formulation for anti- concentration. Using this formulation, we give quasi-polynomial time verifiable sum-of-squares certificates of anti-concentration that hold for a wide class of non-Gaussian distributions including anti-concentrated bounded product distributions and uniform distributions over $L_{p}$ balls (and their affine transformations). Consequently, our method upgrades and extends results in algorithmic robust statistics e. g. , list-decodable learning and clustering, to such distributions. As in the case of previous works, our certificates are also obtained via relaxations in the sum-of-squares hierarchy. However, the nature of our argument differs significantly from prior works that formulate anti-concentration as the non-negativity of an explicit polynomial. Our argument constructs a canonical integer program for anti-concentration and analysis a SoS relaxation of it, independent of the intended application. The explicit polynomials appearing in prior works can be seen as specific dual certificates to this program. From a technical standpoint, unlike existing works that explicitly construct sum-of-squares certificates, our argument relies on duality and analyzes a pseudo-expectation on large subsets of the input points that take a small value in some direction. Our analysis uses the method of polynomial reweightings to reduce the problem to analyzing only analytically dense or sparse directions.

SODA Conference 2023 Conference Paper

Concentration of polynomial random matrices via Efron-Stein inequalities

• Goutham Rajendran
• Madhur Tulsiani

Analyzing concentration of large random matrices is a common task in a wide variety of fields. Given independent random variables, several tools are available to bound the norms of random matrices whose entries are linear in the variables, such as the matrix-Bernstein inequality. However, for many recent applications, we need to bound the norms of random matrices whose entries are polynomials in the variables. Such matrices arise naturally in the analysis of spectral algorithms (e. g. , Hopkins et al. [STOC 2016], Moitra and Wein [STOC 2019]), and in lower bounds for semidefinite programs based on the Sum-of-Squares (SoS) hierarchy (e. g. Barak et al. [FOCS 2016], Jones et al. [FOCS 2021]). In this work, we present a general framework to obtain such bounds, based on the beautiful matrix Efron-Stein inequalities developed by Paulin, Mackey and Tropp [Annals of Probability 2016]. The Efron- Stein inequality bounds the norm of a random matrix by the norm of another potentially simpler (but still random) matrix. We view the latter matrix as arising by “differentiating” the starting matrix. By recursively differentiating, our framework reduces the main task to bounding the norms of far simpler matrices. These simpler matrices are in fact deterministic matrices in the case of Rademacher random variables and hence, bounding their norm is a far easier task. In general for non-Rademacher random variables, the task reduces to the much easier task of scalar concentration. Moreover, in the setting of polynomial matrices, our main result also generalizes the work of Paulin, Mackey and Tropp. As applications of our basic framework, we recover known bounds in the literature, especially for simple “tensor networks” and “dense graph matrices”. As applications of our general framework, we derive bounds for “sparse graph matrices”. The sparse graph matrix bounds were obtained only recently by Jones et al. [FOCS 2021] using a nontrivial application of the trace power method, and was a core component in their work. We expect this framework will also be helpful for other applications involving concentration phenomena for nonlinear random matrices.

FOCS Conference 2023 Conference Paper

List Decoding of Tanner and Expander Amplified Codes from Distance Certificates

• Fernando Granha Jeronimo
• Shashank Srivastava
• Madhur Tulsiani

We develop new list decoding algorithms for Tanner codes and distance-amplified codes based on bipartite spectral expanders. We show that proofs exhibiting lower bounds on the minimum distance of these codes can be used as certificates discoverable by relaxations in the Sum-of-Squares (SoS) semi-definite programming hierarchy. Combining these certificates with certain entropic proxies to ensure that the solutions to the relaxations cover the entire list, then leads to algorithms for list decoding several families of codes up to the Johnson bound. We prove the following results: - We show that the LDPC Tanner codes of Zémor [IEEE Trans. Inf. Theory 2001] with alphabet size q, block-length n and distance $\delta$, based on an expander graph with degree d, can be list-decoded up to distance $\mathcal{J}_{q}(\delta)-\varepsilon$ in time $n^{O_{d, q}\left(1 / \varepsilon^{4}\right)}$, where $\mathcal{J}_{q}(\delta)$ denotes the Johnson bound. - We show that the codes obtained via the expander-based distance amplification procedure of Alon, Edmonds and Luby [FOCS 1995] can be list-decoded close to the Johnson bound using the SoS hierarchy, by reducing the list decoding problem to unique decoding of the base code. In particular, starting from any base code unique-decodable up to distance $\delta$, one can obtain near-MDS codes with rate R and distance $1-R-\varepsilon$, list-decodable up to the Johnson bound in time $n^{O_{\varepsilon, \delta}(1)}$. - We show that the locally testable codes of Dinur et al. [STOC 2022] with alphabet size q, block-length n and distance $\delta$ based on a square Cayley complex with generator sets of size d, can be list-decoded up to distance $\mathcal{J}_{q}(\delta)-\varepsilon$ in time $n^{O_{d, q}\left(1 / \varepsilon^{4}\right)}$, where $\mathcal{J}_{q}(\delta)$ denotes the Johnson bound.

STOC Conference 2021 Conference Paper

Near-linear time decoding of Ta-Shma's codes via splittable regularity

• Fernando Granha Jeronimo
• Shashank Srivastava
• Madhur Tulsiani

The Gilbert–Varshamov bound non-constructively establishes the existence of binary codes of distance 1/2−є/2 and rate Ω(є 2 ). In a breakthrough result, Ta-Shma [STOC 2017] constructed the first explicit family of nearly optimal binary codes with distance 1/2−є/2 and rate Ω(є 2+α ), where α → 0 as є → 0. Moreover, the codes in Ta-Shma’s construction are є-balanced, where the distance between distinct codewords is not only bounded from below by 1/2−є/2, but also from above by 1/2+є/2. Polynomial time decoding algorithms for (a slight modification of) Ta-Shma’s codes appeared in [FOCS 2020], and were based on the Sum-of-Squares (SoS) semidefinite programming hierarchy. The running times for these algorithms were of the form N O α (1) for unique decoding, and N O є,α (1) for the setting of “gentle list decoding”, with large exponents of N even when α is a fixed constant. We derive new algorithms for both these tasks, running in time Õ є ( N ). Our algorithms also apply to the general setting of decoding direct-sum codes. Our algorithms follow from new structural and algorithmic results for collections of k -tuples (ordered hypergraphs) possessing a “structured expansion” property, which we call splittability . This property was previously identified and used in the analysis of SoS-based decoding and constraint satisfaction algorithms, and is also known to be satisfied by Ta-Shma’s code construction. We obtain a new weak regularity decomposition for (possibly sparse) splittable collections W ⊆ [ n ] k , similar to the regularity decomposition for dense structures by Frieze and Kannan [FOCS 1996]. These decompositions are also computable in near-linear time Õ(| W |), and form a key component of our algorithmic results.

FOCS Conference 2021 Conference Paper

Sum-of-Squares Lower Bounds for Sparse Independent Set

• Chris Jones
• Aaron Potechin
• Goutham Rajendran
• Madhur Tulsiani
• Jeff Xu

The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic paradigm which captures state-of-the-art algorithmic guarantees for a wide array of problems. In the average case setting, SoS lower bounds provide strong evidence of algorithmic hardness or information-computation gaps. Prior to this work, SoS lower bounds have been obtained for problems in the “dense” input regime, where the input is a collection of independent Rademacher or Gaussian random variables, while the sparse regime has remained out of reach. We make the first progress in this direction by obtaining strong SoS lower bounds for the problem of Independent Set on sparse random graphs. We prove that with high probability over an Erdós-Rénvi random graph $G\sim G_{n_{J}\frac{d}{u}}$ with average degree $d > \log^{2}n$, degree-Dsos SoS fails to refute the existence of an independent set of size $k=\displaystyle \Omega(\frac{n}{\sqrt{d}(\log n)(\mathrm{D}_{\mathrm{S}\mathrm{o}\mathrm{S}})^{c_{0}}})$ in $G$ (where $c_{0}$ is an absolute constant), whereas the true size of the largest independent set in $G$ is $O(\displaystyle \frac{n\log d}{d})$. Our proof involves several significant extensions of the techniques used for proving SoS lower bounds in the dense setting. Previous lower bounds are based on the pseudo-calibration heuristic of Barak et al. [FOCS 2016] which produces a candidate SoS solution using a planted distribution indistinguishable from the input distribution via low-degree tests. In the sparse case the natural planted distribution does admit low-degree distinguishers, and we show how to adapt the pseudo-calibration heuristic to overcome this. Another notorious technical challenge for the sparse regime is the quest for matrix norm bounds. In this paper, we obtain new norm bounds for graph matrices in the sparse setting. While in the dense setting the norms of graph matrices are characterized by the size of the minimum vertex separator of the corresponding graph, this turns not to be the case for sparse graph matrices. Another contribution of our work is developing a new combinatorial understanding of structures needed to understand the norms of sparse graph matrices.

SODA Conference 2020 Conference Paper

List Decoding of Direct Sum Codes

• Vedat Levi Alev
• Fernando Granha Jeronimo
• Dylan Quintana
• Shashank Srivastava
• Madhur Tulsiani

FOCS Conference 2020 Conference Paper

Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound

• Fernando Granha Jeronimo
• Dylan Quintana
• Shashank Srivastava
• Madhur Tulsiani

The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes of distance $1/2-\varepsilon$ and rate $\Omega(\varepsilon^{2})$ (where an upper bound of $O(\varepsilon^{2}\log(1/\varepsilon))$ is known). Ta-Shma [STOC 2017] gave an explicit construction of $\varepsilon$ -balanced binary codes, where any two distinct codewords are at a distance between $1/2-\varepsilon/2$ and $1/2+\varepsilon/2$, achieving a near optimal rate of $\Omega(\varepsilon^{2+\beta})$, where $\beta\rightarrow 0$ as $\varepsilon\rightarrow 0$. We develop unique and list decoding algorithms for (a slight modification of) the family of codes constructed by Ta-Shma, in the adversarial error model. We prove the following results for $\varepsilon$ -balanced codes with block length $N$ and rate $\Omega(\varepsilon^{2+\beta})$ in this family: –For all $\varepsilon, \beta > 0$, there are explicit codes which can be uniquely decoded up to an error of half the minimum distance in time $N^{O_{\varepsilon, \beta}(1)}$. –For any fixed constant $\beta$ independent of $\varepsilon$, there is an explicit construction of codes which can be uniquely decoded up to an error of half the minimum distance in time $(\log(1/\varepsilon))^{O(1)}\cdot N^{O_{\beta}(1)}$. –For any $\varepsilon > 0$, there are explicit $\varepsilon$ -balanced codes with rate $\Omega(\varepsilon^{2+\beta})$ which can be list decoded up to error $1/2-\varepsilon^{\prime}$ in time $N^{\mathrm{O}_{\varepsilon, \varepsilon^{\prime}, \beta}(1)}$, where $\varepsilon^{\prime}, \beta\rightarrow 0$ as $\varepsilon\rightarrow 0$. The starting point of our algorithms is the framework for list decoding direct-sum codes develop in Alev et al. [SODA 2020], which uses the Sum-of-Squares SDP hierarchy. The rates obtained there were quasipolynomial in $\varepsilon$. Here, we show how to overcome the far from optimal rates of this framework obtaining unique decoding algorithms for explicit binary codes of near optimal rate. These codes are based on simple modifications of Ta-Shma's construction.

SODA Conference 2019 Conference Paper

Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness

• Vijay Bhattiprolu
• Mrinalkanti Ghosh
• Venkatesan Guruswami
• Euiwoong Lee
• Madhur Tulsiani

We study the problem of computing the p → q operator norm of a matrix A in ℝ m × n, defined as ‖ A ‖ p → q: = sup x ∊ℝ n \{0} ‖ Ax ‖ q /‖ x ‖ p. This problem generalizes the spectral norm of a matrix ( p = q = 2) and the Grothendieck problem ( p = ∞, q = 1), and has been widely studied in various regimes. When p ≥ q, the problem exhibits a dichotomy: constant factor approximation algorithms are known if 2 is in [ q, p ], and the problem is hard to approximate within almost polynomial factors when 2 is not in [ q, p ]. For the case when 2 is in [ q, p ] we prove almost matching approximation and NP-hardness results. The regime when p < q, known as hypercontractive norms, is particularly significant for various applications but much less well understood. The case with p = 2 and q > 2 was studied by [Barak et. al. , STOC’12] who gave sub-exponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the Exponential Time Hypothesis. However, no NP-hardness of approximation is known for these problems for any p < q. We prove the first NP-hardness result for approximating hypercontractive norms. We show that for any 1 < p < q < ∞ with 2 not in [ p, q ], ‖ A ‖ p → q is hard to approximate within 2 O ( log 1−∊ n ) assuming NP is not contained in BPTIME(2 log O(1) n ) ).

FOCS Conference 2019 Conference Paper

Approximating Constraint Satisfaction Problems on High-Dimensional Expanders

• Vedat Levi Alev
• Fernando Granha Jeronimo
• Madhur Tulsiani

We consider the problem of approximately solving constraint satisfaction problems with arity k > 2 (kCSPs) on instances satisfying certain expansion properties, when viewed as hypergraphs. Random instances of k-CSPs, which are also highly expanding, are well-known to be hard to approximate using known algorithmic techniques (and are widely believed to be hard to approximate in polynomial time). However, we show that this is not necessarily the case for instances where the hypergraph is a high-dimensional expander. We consider the spectral definition of highdimensional expansion used by Dinur and Kaufman [FOCS 2017] to construct certain primitives related to PCPs. They measure the expansion in terms of a parameter γ which is the analogue of the second singular value for expanding graphs. Extending the results by Barak, Raghavendra and Steurer [FOCS 2011] for 2-CSPs, we show that if an instance of MAX k-CSP over alphabet [q] is a high-dimensional expander with parameter γ, then it is possible to approximate the maximum fraction of satisfiable constraints up to an additive error ε using q O(k) · (k/ε) O(1) levels of the sum-of-squares SDP hierarchy, provided γ ≤ ε O(1) · (1/(kq)) O(k). Based on our analysis, we also suggest a notion of threshold-rank for hypergraphs, which can be used to extend the results for approximating 2-CSPs on low threshold-rank graphs. We show that if an instance of MAX k-CSP has threshold rank r for a threshold τ = (ε/k) O(1) · (1/q) O(k), then it is possible to approximately solve the instance up to additive error ε, using r · q O(k) · (k/ε) O(1) levels of the sum-of-squares hierarchy. As in the case of graphs, high-dimensional expanders (with sufficiently small γ) have threshold rank 1 according to our definition.

SODA Conference 2018 Conference Paper

Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius

• Pooya Hatami
• Madhur Tulsiani

FOCS Conference 2017 Conference Paper

Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere

• Vijay Bhattiprolu
• Mrinalkanti Ghosh
• Venkatesan Guruswami
• Euiwoong Lee
• Madhur Tulsiani

We consider the following basic problem: given an n-variate degree-d homogeneous polynomial f with real coefficients, compute a unit vector x in R̂n that maximizes abs(f(x)). Besides its fundamental nature, this problem arises in diverse contexts ranging from tensor and operator norms to graph expansion to quantum information theory. The homogeneous degree-2 case is efficiently solvable as it corresponds to computing the spectral norm of an associated matrix, but the higher degree case is NP-hard. We give approximation algorithms for this problem that offer a trade-off between the approximation ratio and running time: in n̂O(q) time, we get an approximation within factor (O(n)/q)̂(d/2-1) for arbitrary polynomials, (O(n)/q)̂(d/4-1/2) for polynomials with non-negative coefficients, and (m /q)̂(1/2) for sparse polynomials with m monomials. The approximation guarantees are with respect to the optimum of the level-q sum-of-squares (SoS) SDP relaxation of the problem (though our algorithms do not rely on actually solving the SDP). Known polynomial time algorithms for this problem rely on “decoupling lemmas. ” Such tools are not capable of offering a trade-off like our results as they blow up the number of variables by a factor equal to the degree. We develop new decoupling tools that are more efficient in the number of variables at the expense of less structure in the output polynomials. This enables us to harness the benefits of higher level SoS relaxations. Our decoupling methods also work with “folded polynomials, ” which are polynomials with polynomials as coefficients. This allows us to exploit easy substructures (such as quadratics) by considering them as coefficients in our algorithms. We complement our algorithmic results with some polynomially large integrality gaps for d-levels of the SoS relaxation. For general polynomials this follows from known results for random polynomials, which yield a gap of Omega(n)̂(d/4-1/2). For polynomials with non-negative coefficients, we prove an Omega(n̂(1/6) /polylogs) gap for the degree-4 case, based on a novel distribution of 4-uniform hypergraphs. We establish an n̂Omega(d) gap for general degree-d, albeit for a slightly weaker (but still very natural) relaxation. Toward this, we give a method to lift a level-4 solution matrix M to a higher level solution, under a mild technical condition on M. From a structural perspective, our work yields worst-case convergence results on the performance of the sum-of-squareshierarchy for polynomial optimization. Despite the popularity of SoS in this context, such results were previously only known for the case of q = Omega(n).

SODA Conference 2015 Conference Paper

Algorithmic regularity for polynomials and applications

• Arnab Bhattacharyya 0001
• Pooya Hatami
• Madhur Tulsiani

In analogy with the regularity lemma of Szemerédi [Sze75], regularity lemmas for polynomials proved by Green and Tao [GT09] and by Kaufman and Lovett [KL08] show that one can modify a given collection of polynomials ℱ = { P 1, …, P m } into a new collection ℱ′ so that the polynomials in ℱ′ are “pseudorandom”. These lemmas have various applications, such as (special cases of) Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from ℱ to ℱ′ in these works is not algorithmic. We define new notions of regularity for polynomials which, while being qualitatively equivalent to the above, also allow for efficient algorithms. Using the algorithmic regularity lemmas, we obtain an algorithmic version of the inverse theorem for Gowers norm (for bounded degree polynomials) over fields of high characteristic, by Green and Tao [GT09]. As an application, we show that if a polynomial P of degree d is within (normalized) Hamming distance of some unknown polynomial of degree k over a prime field (for k < d < | |), then there is an efficient algorithm for finding a degree- k polynomial Q, which is within distance of P, for some η depending on ε, This can be thought of as decoding the Reed-Muller code of order k beyond the list decoding radius, in the sense of finding one close codeword, when the received word P itself is a polynomial (of degree larger than k but smaller than | |). We also show an algorithmic inverse theorem for polynomials over fields of small characteristic and somewhat simplify the original proof by Tao and Ziegler [TZ12]. We also obtain an algorithmic version of the worstcase to average-case reductions by Kaufman and Lovett [KL08]. They show that if a polynomial of degree d can be weakly approximated by a polynomial of lower degree, then it can be computed exactly using a collection of polynomials of degree at most d − 1. We give an effcient algorithm to find this collection. Finally, our algorithmic regularity lemma over low characteristics can be used to effciently decompose low-degree polynomials over n (for any prime order field ) into polynomials P 1, …, P m: n → that satisfy prescribed degree bounds and for which P ( x ) = Λ( P 1 ( x ), …. P m ( x )) for a given m and Λ.

STOC Conference 2014 Conference Paper

A characterization of strong approximation resistance

• Subhash Khot
• Madhur Tulsiani
• Pratik Worah

For a predicate f : {-1, 1} k ↦ {0, 1} with ρ ( f ) = | f -1 (1)|/2 k , we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP( f ), it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range [ ρ ( f ) - Ω(1), ρ ( f ) + Ω(1)].

SODA Conference 2011 Conference Paper

Algorithms and Hardness for Subspace Approximation

• Amit Deshpande 0001
• Madhur Tulsiani
• Nisheeth K. Vishnoi

SODA Conference 2011 Conference Paper

On LP-Based Approximability for Strict CSPs

• Amit Kumar 0001
• Rajsekar Manokaran
• Madhur Tulsiani
• Nisheeth K. Vishnoi

FOCS Conference 2011 Conference Paper

Quadratic Goldreich-Levin Theorems

• Madhur Tulsiani
• Julia Wolf

Decomposition theorems in classical Fourier analysis enable us to express a bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases. The Goldreich-Levin algorithm [7] can be viewed as an algorithmic analogue of such a decomposition as it gives a way to efficiently find the linear phases associated with large Fourier coefficients. In the study of "quadratic Fourier analysis", higher-degree analogues of such decompositions have been developed in which the pseudorandomness property is stronger but the structured part correspondingly weaker. For example, it has previously been shown that it is possible to express a bounded function as a sum of a few quadratic phases plus a part that is small in the U 3 norm, defined by Gowers for the purpose of counting arithmetic progressions of length 4. We give a polynomial time algorithm for computing such a decomposition. A key part of the algorithm is a local self-correction procedure for Reed-Muller codes of order 2 (over F 2 n ) for a function at distance 1/2 - ε from a codeword. Given a function f: F 2 n → {-1, 1} at fractional Hamming distance 1/2 - ε from a quadratic phase (which is a codeword of Reed-Muller code of order 2), we give an algorithm that runs in time polynomial in n and finds a codeword at distance at most 1/2 - η for η = η(ε). This is an algorithmic analogue of Samorodnitsky's result [17], which gave a tester for the above problem. To our knowledge, it represents the first instance of a correction procedure for any class of codes, beyond the list-decoding radius.

STOC Conference 2009 Conference Paper

CSP gaps and reductions in the lasserre hierarchy

• Madhur Tulsiani

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck [23] recently showed the first integrality gaps for these problems, showing that for MAX k-XOR, the ratio of the SDP optimum to the integer optimum may be as large as 2 even after Ω(n) rounds of the Lasserre hierarchy. We show that for the general MAX k-CSP problem, this ratio can be as large as 2 k /2k - ε when the alphabet is binary and q k /q(q-1)k - ε when the alphabet size a prime q, even after Ω(n) rounds of the Lasserre hierarchy. We also explore how to translate gaps for CSP into integrality gaps for other problems using reductions, and establish SDP gaps for Maximum Independent Set, Approximate Graph Coloring, Chromatic Number and Minimum Vertex Cover. For Independent Set and Chromatic Number, we show integrality gaps of n/2 O(√(log n log log n)) even after 2 Ω(√(log n log log n)) rounds. In case of Approximate Graph Coloring, for every constant l, we construct graphs with chromatic number Ω(2 l/2 /l 2 ), which admit a vector l-coloring for the SDP obtained by Ω(n) rounds. For Vertex Cover, we show an integrality gap of 1.36 for Ω(n δ ) rounds, for a small constant δ. The results for CSPs provide the first examples of Ω(n) round integrality gaps matching hardness results known only under the Unique Games Conjecture. This and some additional properties of the integrality gap instance, allow for gaps for in case of Independent Set and Chromatic Number which are stronger than the NP-hardness results known even under the Unique Games Conjecture.

FOCS Conference 2008 Conference Paper

Dense Subsets of Pseudorandom Sets

• Omer Reingold
• Luca Trevisan 0001
• Madhur Tulsiani
• Salil P. Vadhan

A theorem of Green, Tao, and Ziegler can be stated (roughly) as follows: ifR is a pseudorandom set, and D is a dense subset of R, then D may be modeled by a set M that is dense in the entire domain such that D and M are indistinguishable. (The precise statement refers to"measures" or distributions rather than sets.) The proof of this theorem is very general, and it applies to notions of pseudo-randomness and indistinguishability defined in terms of any family of distinguishers with some mild closure properties. The proof proceeds via iterative partitioning and an energy increment argument, in the spirit of the proof of the weak Szemeredi regularity lemma. The "reduction" involved in the proof has exponential complexity in the distinguishing probability. We present a new proof inspired by Nisan's proof of Impagliazzo's hardcore set theorem. The reduction in our proof has polynomial complexity in the distinguishing probability and provides a new characterization of the notion of "pseudoentropy" of a distribution. A proof similar to ours has also been independently discovered by Gowers [2]. We also follow the connection between the two theorems and obtain a new proof of Impagliazzo's hardcore set theorem via iterative partitioning and energy increment. While our reduction has exponential complexity in some parameters, it has the advantage that the hardcore set is efficiently recognizable.

STOC Conference 2008 Conference Paper

Unique games on expanding constraint graphs are easy: extended abstract

• Sanjeev Arora
• Subhash Khot
• Alexandra Kolla
• David Steurer
• Madhur Tulsiani
• Nisheeth K. Vishnoi

We present an efficient algorithm to find a good solution to the Unique Games problem when the constraint graph is an expander.

STOC Conference 2007 Conference Paper

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

• Grant Schoenebeck
• Luca Trevisan 0001
• Madhur Tulsiani

We study linear programming relaxations of Vertex Cover and Max Cutarising from repeated applications of the "lift-and-project" method of Lovasz and Schrijver starting from the standard linear programming relaxation. For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove thatthe integrality gap remains at least 2-ε after Ω ε (log n) rounds, where n is the number ofvertices, and Tourlakis proves that integrality gap remains at least 1.5-ε after Ω((log n) 2 ) rounds. Fernandez de laVega and Kenyon prove that the integrality gap of Max Cut is at most 12 + ε after any constant number of rounds. (Theirresult also applies to the more powerful Sherali-Adams method. We prove that the integrality gap of Vertex Cover remains at least 2-ε after Ω ε (n) rounds, and that theintegrality gap of Max Cut remains at most 1/2 +ε after Ω ε (n) rounds.