Mark Braverman

activity

20232026

collaborators

4 papers

cs.CC2026

Parallel Repetition for k-Player XOR Games

Mark Braverman, Dor Minzer

In a $k$ -XOR game $Ψ$ over $F_{p}$ , a verifier samples challenges $(x_{1}, \dots, x_{k}) \sim μ$ where $μ$ is a distribution over $Σ_{1} \times \dots \times Σ_{k}$ , sends $x_{i}$ to player…

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

Parallel Repetition for $3$ -Player XOR Games

Amey Bhangale, Mark Braverman, Subhash Khot +2

In a $3$ - $XOR$ game $G$ , the verifier samples a challenge $(x, y, z) \sim μ$ where $μ$ is a probability distribution over $Σ \times Γ \times Φ$ , and a map $t\colon Σ\ti…

cs.CC2023

Parallel Repetition of k-Player Projection Games

Amey Bhangale, Mark Braverman, Subhash Khot +2

We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection…

Parallel Repetition for k-Player XOR Games

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems

Parallel Repetition for 3-Player XOR Games

Parallel Repetition of k-Player Projection Games

Parallel Repetition for $3$ -Player XOR Games