Subhash Khot

activity

20242026

most citedOn Approximability of Satisfiable k-CSPs: V

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

collaborators

8 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.LG2026

Conditioned free-energy density of proteins using unbalanced solutions to constraint satisfaction problems

Pratik Worah, Subhash Khot, Srinivasa Varadhan

We show that computing the log-partition function (free-energy) of conditioned inhomogeneous Curie--Weiss spin Hamiltonians reduces to an unbalanced $2 \to 1$ norm computation, and…

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

cs.CC2025

Biased Linearity Testing in the 1% Regime

Subhash Khot, Kunal Mittal

We study linearity testing over the $p$ -biased hypercube $({0, 1}^{n}, I^¼_{p}^{\otimes n})$ in the 1% regime. For a distribution $I^½$ supported over $\{x\in \{0,1\}^k:\sum_{i=1}^k x_i…

math.CO2024

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…