We propose a framework of algorithm vs. hardness for all Max-CSPs and demonstrate it for a large class of predicates. This framework extends the work of Raghavendra [STOC, 2008], who showed a similar result for almost satisfiable Max-CSPs.

Our framework is based on a new hybrid approximation algorithm, which uses ... more >>>

We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection games with value less than 1.

For a prime $p$, a restricted arithmetic progression in $\mathbb{F}_p^n$ is a triplet of vectors $x, x+a, x+2a$ in which the common difference $a$ is a non-zero element from $\{0,1,2\}^n$. What is the size of the largest $A\subseteq \mathbb{F}_p^n$ that is free of restricted arithmetic progressions? We show that the ... more >>>

We prove a stability result for general $3$-wise correlations over distributions satisfying mild connectivity properties. More concretely, we show that if $\Sigma,\Gamma$ and $\Phi$ are alphabets of constant size, and $\mu$ is a pairwise connected distribution over $\Sigma\times\Gamma\times\Phi$ with no $(\mathbb{Z},+)$ embeddings in which the probability of each atom is ... more >>>

Let $\Sigma$ be an alphabet and $\mu$ be a distribution on $\Sigma^k$ for some $k \geq 2$. Let $\alpha > 0$ be the minimum probability of a tuple in the support of $\mu$ (denoted by $supp(\mu)$). Here, the support of $\mu$ is the set of all tuples in $\Sigma^k$ that ... more >>>

In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property ... more >>>

We show that the value of the $n$-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

We consider the $P$-CSP problem for $3$-ary predicates $P$ on satisfiable instances. We show that under certain conditions on $P$ and a $(1,s)$ integrality gap instance of the $P$-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness $s+\varepsilon$, for every constant $\varepsilon>0$. ... more >>>

A seminal result of H\r{a}stad [J. ACM, 48(4):798–859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant ... more >>>

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL
Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a
new approach: looking at the first Fourier level of the function after a suitable random restriction and
applying the Log-Sobolev ... more >>>

A systematic study of simultaneous optimization of constraint satisfaction problems was initiated in [BKS15]. The simplest such problem is the simultaneous Max-Cut. [BKKST18] gave a $.878$-minimum approximation algorithm for simultaneous Max-Cut which is {\em almost optimal} assuming the Unique Games Conjecture (UGC). For a single instance Max-Cut, [GW95] gave an ... more >>>

We propose a variant of the $2$-to-$1$ Games Conjecture that we call the Rich $2$-to-$1$ Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the $2$-to-$1$ Games Conjecture, we hope to understand ... more >>>

We prove that for every constant $c$ and $\epsilon = (\log n)^{-c}$, there is no polynomial time algorithm that when given an instance of 3LIN with $n$ variables where an $(1 - \epsilon)$-fraction of the clauses are satisfiable, finds an assignment that satisfies at least $(\frac{1}{2} + \epsilon)$-fraction of clauses ... more >>>

The $2$-to-$2$ Games Theorem of [KMS-1, DKKMS-1, DKKMS-2, KMS-2] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>0$. We show that the reduction ... more >>>

This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers
t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if
their intersection is of size t. The Johnson graph arises often ... more >>>

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes
the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a
contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves ... more >>>

The paper investigates expansion properties of the Grassmann graph,
motivated by recent results of [KMS, DKKMS] concerning hardness
of the Vertex-Cover and of the $2$-to-$1$ Games problems. Proving the
hypotheses put forward by these papers seems to first require a better
understanding of these expansion properties.

We consider the edge ... more >>>

A Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is called a dictator if it depends on exactly one variable i.e $f(x_1, x_2, \ldots, x_n) = x_i$ for some $i\in [n]$. In this work, we study a $k$-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems.

We propose a combinatorial hypothesis regarding a subspace vs. subspace agreement test, and prove that if correct it leads to a proof of the 2-to-1 Games Conjecture, albeit with imperfect completeness.

We present an adaptive tester for the unateness property of Boolean functions. Given a function $f:\{0,1\}^n \to \{0,1\}$ the tester makes $O(n \log(n)/\epsilon)$ adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 any function that is $\epsilon$-far from being unate.
more >>>

We present a candidate reduction from the $3$-Lin problem to the $2$-to-$2$ Games problem and present a combinatorial hypothesis about
Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in
a certain non-standard sense. A reduction that is sound in this non-standard sense
implies that ... more >>>

This paper studies how well the standard LP relaxation approximates a $k$-ary constraint satisfaction problem (CSP) on label set $[L]$. We show that, assuming the Unique Games Conjecture, it achieves an approximation within $O(k^3\cdot \log L)$ of the optimal approximation factor. In particular we prove the following hardness result: let ... more >>>

In the $Gap-clique(k, \frac{k}{2})$ problem, the input is an $n$-vertex graph $G$, and the goal is to decide whether $G$ contains a clique of size $k$ or contains no clique of size $\frac{k}{2}$. It is an open question in the study of fixed parameterized tractability whether the $Gap-clique(k, \frac{k}{2})$ problem ... more >>>

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we
give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function
$f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from
being monotone ... more >>>

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.
Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution ... more >>>

We show that it is quasi-NP-hard to color $2$-colorable $12$-uniform hypergraphs with $2^{(\log n)^{\Omega(1) }}$ colors where $n$ is the number of vertices. Previously, Guruswami et al. [GHHSV14] showed that it is quasi-NP-hard to color $2$-colorable $8$-uniform hypergraphs with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors. Their result is obtained by composing a ... more >>>

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

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

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

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

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\epsilon)} n}})$, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than $2^{\log ^{1-\epsilon}n}.$ This improves upon the previous hardness factor of $(\log n)^\delta$ for some $\delta ... more >>>

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each
equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is
an informal statement of our ... more >>>

In this paper, we consider the problem of approximately solving a
system of homogeneous linear equations over reals, where each
equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations
exactly, we restrict the assignments to be ``non-trivial". Here is
an informal statement of our ... more >>>

We study the polynomial reconstruction problem for low-degree
multivariate polynomials over finite fields. In the GF[2] version of this problem, we are given a set of points on the hypercube and target values $f(x)$ for each of these points, with the promise that there is a polynomial over GF[2] of ... more >>>

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise.

Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of $\GW + \eps$, for all $\eps > 0$; here $\GW \approx .878567$ denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>>

We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, ... more >>>

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is
to find a minimum subset of vertices that ``hits'' every edge. We
show that for every integer $k \geq 5$, E$k$-Vertex-Cover is
NP-hard to approximate within a factor of $(k-3-\epsilon)$, for
an arbitrarily small constant $\epsilon > 0$.

This almost matches the ... more >>>