Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > YANG P. LIU:
All reports by Author Yang P. Liu:

TR26-019 | 10th February 2026
Yang P. Liu, Shachar Lovett, Kunal Mittal

Improved Parallel Repetition for GHZ-Supported Games via Spreadness

We prove that for any 3-player game $\mathcal 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\pmod{2}$), the value of the $n$-fold parallel repetition of $\mathcal G$ decays exponentially fast: \[ \text{val}(\mathcal G^{\otimes n}) \leq \exp(-n^c)\] for all sufficiently large $n$, ... more >>>


TR25-173 | 5th November 2025
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer, Kunal Mittal

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems

Let $\mathcal{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 every $n\geq N$, the value of the $n$-fold parallel repetition of $\mathcal{G}$ is $$ \text{val}(\mathcal{G}^{\otimes n}) \leq \frac{1}{\underbrace{\log\log\cdots\log}_{C\text{ times}} n}, $$ ... more >>>


TR25-047 | 10th April 2025
Michael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni, Mehtaab Sawhney

Quasipolynomial bounds for the corners theorem

Let $G$ be a finite abelian group and $A$ be a subset of $G \times G$ which is corner--free, meaning that there are no $x, y \in G$ and $d \in G \setminus \{0\}$ such that $(x, y)$, $(x+d, y)$, $(x, y+d) \in A$. We prove that
$|A| \le |G|^2 ... more >>>




ISSN 1433-8092 | Imprint