All reports by Author Madhur Tulsiani:

__
TR20-136
| 11th September 2020
__

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani#### Explicit and structured sum of squares lower bounds from high dimensional expanders

__
TR18-097
| 15th May 2018
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Approximating Operator Norms via Generalized Krivine Rounding

__
TR18-037
| 21st February 2018
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Inapproximability of Matrix $p \rightarrow q$ Norms

__
TR16-185
| 18th November 2016
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

Revisions: 1

__
TR16-117
| 31st July 2016
__

Mrinalkanti Ghosh, Madhur Tulsiani#### From Weak to Strong LP Gaps for all CSPs

Revisions: 1

__
TR13-146
| 20th October 2013
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### A Characterization of Approximation Resistance

Revisions: 1

__
TR13-075
| 23rd May 2013
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### A Characterization of Strong Approximation Resistance

__
TR12-151
| 6th November 2012
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### The Complexity of Somewhat Approximation Resistant Predicates

Revisions: 1

__
TR12-135
| 26th October 2012
__

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf#### Sampling-based proofs of almost-periodicity results and algorithmic applications

Revisions: 2

__
TR12-109
| 31st August 2012
__

Subhash Khot, Muli Safra, Madhur Tulsiani#### Towards An Optimal Query Efficient PCP?

__
TR12-105
| 17th August 2012
__

Madhur Tulsiani, Pratik Worah#### $LS_+$ Lower Bounds from Pairwise Independence

__
TR11-084
| 23rd May 2011
__

Madhur Tulsiani, Julia Wolf#### Quadratic Goldreich-Levin Theorems

__
TR10-172
| 11th November 2010
__

Prasad Raghavendra, David Steurer, Madhur Tulsiani#### Reductions Between Expansion Problems

__
TR09-141
| 19th December 2009
__

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani#### Improved Pseudorandom Generators for Depth 2 Circuits

__
TR09-124
| 24th November 2009
__

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi#### On the Optimality of a Class of LP-based Algorithms

Revisions: 1

__
TR09-113
| 9th November 2009
__

Anindya De, Luca Trevisan, Madhur Tulsiani#### Non-uniform attacks against one-way functions and PRGs

__
TR09-061
| 2nd July 2009
__

Konstantinos Georgiou, Avner Magen, Madhur Tulsiani#### Optimal Sherali-Adams Gaps from Pairwise Independence

__
TR08-104
| 23rd November 2008
__

Madhur Tulsiani#### CSP Gaps and Reductions in the Lasserre Hierarchy

__
TR08-103
| 22nd November 2008
__

Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

__
TR08-045
| 23rd April 2008
__

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Dense Subsets of Pseudorandom Sets

__
TR06-132
| 17th October 2006
__

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani#### Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut

Revisions: 1

__
TR06-098
| 17th August 2006
__

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani#### A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

We construct an explicit family of 3XOR instances which is hard for Omega(sqrt(log n)) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time.

Our construction is based on the high-dimensional expanders devised by Lubotzky, ...
more >>>

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

We consider the $(\ell_p,\ell_r)$-Grothendieck problem, which seeks to maximize the bilinear form $y^T A x$ for an input matrix $A \in {\mathbb R}^{m \times n}$ over vectors $x,y$ with $\|x\|_p=\|y\|_r=1$. The problem is equivalent to computing the $p \to r^\ast$ operator norm of $A$, where $\ell_{r^*}$ is the dual norm ... more >>>

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

We study the problem of computing the $p\rightarrow q$ norm of a matrix $A \in R^{m \times n}$, defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p} \] This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$, $q=1$), and has been ... more >>>

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 \mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in many diverse contexts ranging from tensor and operator norms to graph expansion to quantum information ... more >>>

Mrinalkanti Ghosh, Madhur Tulsiani

We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by $\Omega\left(\frac{\log n}{\log \log n}\right)$ levels of the Sherali-Adams hierarchy on instances ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

A predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|f^{-1}(1)|}{2^k}$ is called {\it approximation resistant} if given a near-satisfiable instance of CSP$(f)$, it is computationally hard to find an assignment that satisfies at least $\rho(f)+\Omega(1)$ fraction of the constraints.

We present a complete characterization of approximation resistant predicates under the ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

For a predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|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 $[\rho(f)-\Omega(1), \rho(f)+\Omega(1)]$.

We present a characterization of ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

A boolean predicate $f:\{0,1\}^k\to\{0,1\}$ is said to be {\em somewhat approximation resistant} if for some constant $\tau > \frac{|f^{-1}(1)|}{2^k}$, given a $\tau$-satisfiable instance of the MAX-$k$-CSP$(f)$ problem, it is NP-hard to find an assignment that {\it strictly beats} the naive algorithm that outputs a uniformly random assignment. Let $\tau(f)$ denote ... more >>>

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf

We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [Geom. Funct. Anal. 2010], whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and $L^p$-norm free) point of view, which allows for ... more >>>

Subhash Khot, Muli Safra, Madhur Tulsiani

We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16.

At a technical level, our ...
more >>>

Madhur Tulsiani, Pratik Worah

We consider the complexity of LS$_+$ refutations of unsatisfiable instances of Constraint Satisfaction Problems (CSPs) when the underlying predicate supports a pairwise independent distribution on its satisfying assignments. This is the most general condition on the predicates under which the corresponding MAX-CSP problem is known to be approximation resistant.

We ... more >>>

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 can be viewed as an algorithmic analogue of such a decomposition as it ... more >>>

Prasad Raghavendra, David Steurer, Madhur Tulsiani

The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in graphs. This hardness assumption is closely connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the Small-Set Expansion Hypothesis implies the Unique ... more >>>

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

We prove the existence of a $poly(n,m)$-time computable

pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables

and $m$ terms, and has seed length $O(\log^2 nm \cdot \log\log nm)$.

Previously, the best pseudorandom generator for depth-2 circuits had seed

length $O(\log^3 nm)$, and was due to Bazzi (FOCS 2007).

It ... more >>>

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi

In this paper we will be concerned with a large class of packing

and covering problems which includes Vertex Cover and Independent Set.

Typically, for NP-hard problems among them, one can write an LP relaxation and

then round the solution. For instance, for Vertex Cover, one can obtain a

more >>>

Anindya De, Luca Trevisan, Madhur Tulsiani

We study the power of non-uniform attacks against one-way

functions and pseudorandom generators.

Fiat and Naor show that for every function

$f: [N]\to [N]$

there is an algorithm that inverts $f$ everywhere using

(ignoring lower order factors)

time, space and advice at most $N^{3/4}$.

We show that ... more >>>

Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by $P$ contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on $n$ variables cannot be approximated ... more >>>

Madhur Tulsiani

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck 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 ...
more >>>

Luca Trevisan, Madhur Tulsiani, Salil Vadhan

We show that every high-entropy distribution is indistinguishable from an

efficiently samplable distribution of the same entropy. Specifically, we prove

that if $D$ is a distribution over $\{ 0,1\}^n$ of min-entropy at least $n-k$,

then for every $S$ and $\epsilon$ there is a circuit $C$ of size at most

$S\cdot ...
more >>>

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan

A theorem of Green, Tao, and Ziegler can be stated (roughly)

as follows: if R 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

more >>>

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

We study linear programming relaxations of Vertex Cover and Max Cut

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

the integrality gap remains at least $2-\epsilon$ after

$\Omega_\epsilon(\log n)$ ...
more >>>

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

We study semidefinite programming relaxations of Vertex Cover arising from

repeated applications of the LS+ ``lift-and-project'' method of Lovasz and

Schrijver starting from the standard linear programming relaxation.

Goemans and Kleinberg prove that after one round of LS+ the integrality

gap remains arbitrarily close to 2. Charikar proves an integrality ...
more >>>