Subhash Khot

activity

20242026

most citedOn Approximability of Satisfiable k-CSPs: V

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

collaborators

Showing 2025Show all

2 papers · 1 filter

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…