Amey Bhangale

activity

20242026

most citedOn Approximability of Satisfiable k-CSPs: V

2 citations · 2 across the 3 of their papers we have counts for

collaborators

10 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.CC2026★ 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.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…