Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Madhur Tulsiani:

TR18-097 | 15th May 2018
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Approximating Operator Norms via Generalized Krivine Rounding

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

TR18-037 | 21st February 2018
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Inapproximability of Matrix $p \rightarrow q$ Norms

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

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

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

TR16-117 | 31st July 2016
Mrinalkanti Ghosh, Madhur Tulsiani

From Weak to Strong LP Gaps for all CSPs

Revisions: 1

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

TR13-146 | 20th October 2013
Subhash Khot, Madhur Tulsiani, Pratik Worah

A Characterization of Approximation Resistance

Revisions: 1

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

TR13-075 | 23rd May 2013
Subhash Khot, Madhur Tulsiani, Pratik Worah

A Characterization of Strong Approximation Resistance

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

TR12-151 | 6th November 2012
Subhash Khot, Madhur Tulsiani, Pratik Worah

The Complexity of Somewhat Approximation Resistant Predicates

Revisions: 1

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

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

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

TR12-109 | 31st August 2012
Subhash Khot, Muli Safra, Madhur Tulsiani

Towards An Optimal Query Efficient PCP?

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

TR12-105 | 17th August 2012
Madhur Tulsiani, Pratik Worah

$LS_+$ Lower Bounds from Pairwise Independence

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

TR11-084 | 23rd May 2011
Madhur Tulsiani, Julia Wolf

Quadratic Goldreich-Levin Theorems

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

TR10-172 | 11th November 2010
Prasad Raghavendra, David Steurer, Madhur Tulsiani

Reductions Between Expansion Problems

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

TR09-141 | 19th December 2009
Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

Improved Pseudorandom Generators for Depth 2 Circuits

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

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

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

TR09-113 | 9th November 2009
Anindya De, Luca Trevisan, Madhur Tulsiani

Non-uniform attacks against one-way functions and PRGs

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

TR09-061 | 2nd July 2009
Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

Optimal Sherali-Adams Gaps from Pairwise Independence

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

TR08-104 | 23rd November 2008
Madhur Tulsiani

CSP Gaps and Reductions in the Lasserre Hierarchy

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

TR08-103 | 22nd November 2008
Luca Trevisan, Madhur Tulsiani, Salil Vadhan

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

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

TR08-045 | 23rd April 2008
Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan

Dense Subsets of Pseudorandom Sets

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

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

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

TR06-098 | 17th August 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

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

ISSN 1433-8092 | Imprint