All reports by Author Amey Bhangale:

__
TR24-129
| 27th August 2024
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable k-CSPs: V

__
TR23-198
| 8th December 2023
__

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer#### Parallel Repetition of k-Player Projection Games

__
TR23-116
| 12th August 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$

__
TR23-112
| 30th July 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable k-CSPs: IV

__
TR23-055
| 20th April 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: II

Revisions: 1

__
TR23-054
| 20th April 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: III

__
TR22-061
| 30th April 2022
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: I

__
TR21-142
| 1st October 2021
__

Amey Bhangale, Prahladh Harsha, Sourya Roy#### Mixing of 3-term progressions in Quasirandom Groups

__
TR20-130
| 30th August 2020
__

Amey Bhangale, Subhash Khot#### Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

__
TR20-075
| 6th May 2020
__

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal#### Rigid Matrices From Rectangular PCPs

Revisions: 2

__
TR19-148
| 1st November 2019
__

Amey Bhangale, Subhash Khot#### Simultaneous Max-Cut is harder to approximate than Max-Cut

Revisions: 1

__
TR19-048
| 2nd April 2019
__

Per Austrin, Amey Bhangale, Aditya Potukuchi#### Simplified inpproximability of hypergraph coloring via t-agreeing families

__
TR19-004
| 11th January 2019
__

Amey Bhangale, Subhash Khot#### UG-hardness to NP-hardness by Losing Half

Revisions: 1

__
TR18-073
| 21st April 2018
__

Amey Bhangale#### NP-hardness of coloring $2$-colorable hypergraph with poly-logarithmically many colors

__
TR17-030
| 15th February 2017
__

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari#### An Improved Dictatorship Test with Perfect Completeness

__
TR16-205
| 22nd December 2016
__

Amey Bhangale, Irit Dinur, Inbal Livni Navon#### Cube vs. Cube Low Degree Test

__
TR16-112
| 18th July 2016
__

Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz#### Bicovering: Covering edges with two small subsets of vertices

__
TR15-069
| 21st April 2015
__

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat#### On Fortification of General Games

Revisions: 1

__
TR14-098
| 30th July 2014
__

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva#### Simultaneous Approximation of Constraint Satisfaction Problems

Amey Bhangale, Subhash Khot, Dor Minzer

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

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer

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.

more >>>Amey Bhangale, Subhash Khot, Dor Minzer

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

Amey Bhangale, Subhash Khot, Dor Minzer

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

Amey Bhangale, Subhash Khot, Dor Minzer

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

Amey Bhangale, Subhash Khot, Dor Minzer

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

Amey Bhangale, Subhash Khot, Dor Minzer

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

Amey Bhangale, Prahladh Harsha, Sourya Roy

In this note, we show the mixing of three-term progressions $(x, xg, xg^2)$ in every finite quasirandom group, fully answering a question of Gowers. More precisely, we show that for any $D$-quasirandom group $G$ and any three sets $A_1, A_2, A_3 \subset G$, we have

\[ \left|\Pr_{x,y\sim G}\left[ x \in ...
more >>>

Amey Bhangale, Subhash Khot

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

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

We introduce a variant of PCPs, that we refer to as *rectangular* PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the *row* of each query and the other determining the *column*.

We ... more >>>

Amey Bhangale, Subhash Khot

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

Per Austrin, Amey Bhangale, Aditya Potukuchi

We reprove the results on the hardness of approximating hypergraph coloring using a different technique based on bounds on the size of extremal $t$-agreeing families of $[q]^n$. Specifically, using theorems of Frankl-Tokushige [FT99], Ahlswede-Khachatrian [AK98] and Frankl [F76] on the size of such families, we give simple and unified proofs ... more >>>

Amey Bhangale, Subhash Khot

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

Amey Bhangale

We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,

(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.

(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.

In terms of ... more >>>

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

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.

... more >>>Amey Bhangale, Irit Dinur, Inbal Livni Navon

We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension $3$) that intersect on a ... more >>>

Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz

We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and that every edge $e$ belongs to either the graph induced by $A$ or to the graph induced by $B$. The ... more >>>

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

A recent result of Moshkovitz~\cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel ... more >>>

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

Given $k$ collections of 2SAT clauses on the same set of variables $V$, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.

Our main result is that ... more >>>