Kunal Mittal

collaborators

Showing cs.CCShow all

4 papers · 1 filter

cs.CC2026

Improved Parallel Repetition for GHZ-Supported Games via Spreadness

Yang P. Liu, Shachar Lovett, Kunal Mittal

We prove that for any 3-player game $G$ , whose query distribution has the same support as the GHZ game (i.e., all $x, y, z \in {0, 1}$ satisfying $x + y + z = 0 (mod 2)$ ), the val…

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…