Subhash Khot

most citedOn Approximability of Satisfiable

k

-CSPs: VII

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

collaborators

5 papers

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}, μ_{p}^{\otimes n})$ in the 1% regime. For a distribution $ν$ supported over $\{x\in \{0,1\}^k:\sum_{i=1}^k x_i=0…

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…

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems

Biased Linearity Testing in the 1% Regime

Reasonable Bounds for Combinatorial Lines of Length Three

On Approximability of Satisfiable k-CSPs: VII

On Approximability of Satisfiable k-CSPs: VI

On Approximability of Satisfiable $k$ -CSPs: VII

On Approximability of Satisfiable $k$ -CSPs: VI