Amey Bhangale

activity

20142026

most citedRigid Matrices From Rectangular PCPs

16 citations · 45 across the 22 of their papers we have counts for

collaborators

29 papers

math.CO2026

A Counting Lemma for Somewhat Restricted 3-APs

Amey Bhangale, Subhash Khot, Yang P. Liu +1

For a prime $p \geq 3$ , a somewhat restricted $3$ -AP in $F_{p}^{n}$ is a triplet $(x, x + a, x + 2 a)$ , where $x \in F_{p}^{n}$ and $a \in {0, 1, 2}^{n}$ . We prove a counting lemma fo…

cs.DS2026

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover

Amey Bhangale, Yezhou Zhang

We study the \emph{generalized min-sum set cover} (GMSSC) problem, where given a collection of hyperedges $E$ with arbitrary covering requirements $\{k_e \in \mathbb{Z}^+ : e \in E…

cs.CC2026

Optimal Inapproximability of Generalized Linear Equations over a Finite Group

Amey Bhangale, Yezhou Zhang

Constraint satisfaction problems (CSPs) consist of a set of variables taking values from some finite domain and a set of local constraints on these variables. The objective is to f…

cs.DS2025

Optimal Online Bipartite Matching in Degree-2 Graphs

Amey Bhangale, Arghya Chakraborty, Prahladh Harsha

Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same c…

cs.CC2025

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems

Amey Bhangale, Mark Braverman, Subhash Khot +3

Let $G$ be a $k$ -player game with value $< 1$ , whose query distribution is such that no marginal on $k - 1$ players admits a non-trivial Abelian embedding. We show that for…

math.CO2024★ 1 cited

Reasonable Bounds for Combinatorial Lines of Length Three

Amey Bhangale, Subhash Khot, Yang P. Liu +1

We prove that any subset $A \subseteq [3]^{n}$ with $3^{- n} ∣ A ∣ \geq (lo g lo g lo g lo g n)^{- c}$ contains a combinatorial line of length $3$ , i.e., $x, y, z \in A$ , not all equal, with…

cs.CC2024★ 1 cited

On Approximability of Satisfiable $k$ -CSPs: VII

Amey Bhangale, Subhash Khot, Yang P. Liu +1

Let $Σ_{1}, \dots, Σ_{k}$ be finite alphabets, and let $μ$ be a distribution over $Σ_{1} \times \dots \times Σ_{k}$ in which the probability of each atom is at least $α$ . We prove that if $…

cs.CC2024★ 1 cited

On Approximability of Satisfiable $k$ -CSPs: VI

Amey Bhangale, Subhash Khot, Yang P. Liu +1

We prove local and global inverse theorems for general $3$ -wise correlations over pairwise-connected distributions. Let $μ$ be a distribution over $Σ \times Γ \times Φ$ such that the…

cs.CC2024

Parallel Repetition for $3$ -Player XOR Games

Amey Bhangale, Mark Braverman, Subhash Khot +2

In a $3$ - $XOR$ game $G$ , the verifier samples a challenge $(x, y, z) \sim μ$ where $μ$ is a probability distribution over $Σ \times Γ \times Φ$ , and a map $t\colon Σ\ti…

cs.CC2024★ 2 cited

On Approximability of Satisfiable k-CSPs: V

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], w…

cs.CC2023

Parallel Repetition of k-Player Projection Games

Amey Bhangale, Mark Braverman, Subhash Khot +2

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…

math.CO2023★ 2 cited

Effective Bounds for Restricted $3$ -Arithmetic Progressions in $F_{p}^{n}$

Amey Bhangale, Subhash Khot, Dor Minzer

For a prime $p$ , a restricted arithmetic progression in $F_{p}^{n}$ is a triplet of vectors $x, x + a, x + 2 a$ in which the common difference $a$ is a non-zero element from $\{0,1…

cs.CC2023★ 1 cited

On Approximability of Satisfiable k-CSPs: IV

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 $Σ, Γ$ and $Φ$ are alphabe…

cs.CC2021

Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs

Amey Bhangale, Aleksa Stankovic

Factor graph of an instance of a constraint satisfaction problem with n variables and m constraints is the bipartite graph between [m] and [n] describing which variable appears in…

math.CO2021★ 1 cited

Mixing of 3-term progressions in Quasirandom Groups

Amey Bhangale, Prahladh Harsha, Sourya Roy

In this note, we show the mixing of three-term progressions $(x, xg, x g^{2})$ in every finite quasirandom groups, fully answering a question of Gowers. More precisely, we show that f…

cs.CC2020

Optimal Inapproximability of Satisfiable $k$ -LIN over Non-Abelian Groups

Amey Bhangale, Subhash Khot

A seminal result of Håstad [J. ACM, 48(4):798--859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{∣ G ∣} + ε$ fraction of the constraints of a…

cs.CC2020

Hardness of Approximation of (Multi-)LCS over Small Alphabet

Amey Bhangale, Diptarka Chakraborty, Rajendra Kumar

The problem of finding longest common subsequence (LCS) is one of the fundamental problems in computer science, which finds application in fields such as computational biology, tex…

cs.CC2020★ 16 cited

Rigid Matrices From Rectangular PCPs

Amey Bhangale, Prahladh Harsha, Orr Paradise +1

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…

cs.CC2019

Simplified inpproximability of hypergraph coloring via t-agreeing families

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}$ . Sp…

cs.CC2018

Improved Inapproximability of Rainbow Coloring

Per Austrin, Amey Bhangale, Aditya Potukuchi

A rainbow $q$ -coloring of a $k$ -uniform hypergraph is a $q$ -coloring of the vertex set such that every hyperedge contains all $q$ colors. We prove that given a rainbow $(k - 2\lflo…

cs.CC2018★ 1 cited

Near-optimal approximation algorithm for simultaneous Max-Cut

Amey Bhangale, Subhash Khot, Swastik Kopparty +2

In the simultaneous Max-Cut problem, we are given $k$ weighted graphs on the same set of $n$ vertices, and the goal is to find a cut of the vertex set so that the minimum, over the…

cs.DM2017

A short note on the joint entropy of n/2-wise independence

Amey Bhangale, Aditya Potukuchi

In this note, we prove a tight lower bound on the joint entropy of $n$ unbiased Bernoulli random variables which are $n /2$ -wise independent. For general $k$ -wise independence, we g…

cs.DS2017★ 5 cited

Improved approximation algorithm for the Dense-3-Subhypergraph Problem

Amey Bhangale, Rajiv Gandhi, Guy Kortsarz

The study of Dense- $3$ -Subhypergraph problem was initiated in Chlamt{á}c et al. [Approx'16]. The input is a universe $U$ and collection $S$ of subsets of $U$ , each of size $…

cs.CC2017

An Improved Dictatorship Test with Perfect Completeness

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

A Boolean function $f : {0, 1}^{n} \to {0, 1}$ is called a dictator if it depends on exactly one variable i.e $f (x_{1}, x_{2}, \dots, x_{n}) = x_{i}$ for some $i \in [n]$ . In this wor…

A Counting Lemma for Somewhat Restricted 3-APs

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover

Optimal Inapproximability of Generalized Linear Equations over a Finite Group

Optimal Online Bipartite Matching in Degree-2 Graphs

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems

Reasonable Bounds for Combinatorial Lines of Length Three

On Approximability of Satisfiable k-CSPs: VII

On Approximability of Satisfiable k-CSPs: VI

Parallel Repetition for 3-Player XOR Games

On Approximability of Satisfiable k-CSPs: V

Parallel Repetition of k-Player Projection Games

Effective Bounds for Restricted 3-Arithmetic Progressions in Fpn​

On Approximability of Satisfiable k-CSPs: IV

Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs

Mixing of 3-term progressions in Quasirandom Groups

Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

Hardness of Approximation of (Multi-)LCS over Small Alphabet

Rigid Matrices From Rectangular PCPs

Simplified inpproximability of hypergraph coloring via t-agreeing families

Improved Inapproximability of Rainbow Coloring

Near-optimal approximation algorithm for simultaneous Max-Cut

A short note on the joint entropy of n/2-wise independence

Improved approximation algorithm for the Dense-3-Subhypergraph Problem

An Improved Dictatorship Test with Perfect Completeness

On Approximability of Satisfiable $k$ -CSPs: VII

On Approximability of Satisfiable $k$ -CSPs: VI

Parallel Repetition for $3$ -Player XOR Games

Effective Bounds for Restricted $3$ -Arithmetic Progressions in $F_{p}^{n}$

Optimal Inapproximability of Satisfiable $k$ -LIN over Non-Abelian Groups