Kunal Mittal

collaborators

3 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

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics

Kunal Mittal

We show equivalences between several high-dimensional problems in extremal combinatorics and parallel repetition of multiplayer (multiprover) games over large answer alphabets. Thi…

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…