Yang P. Liu

activity

20232026

most citedOn Approximability of Satisfiable

k

-CSPs: VII

1 citations · 3 across the 6 of their papers we have counts for

collaborators

7 papers

math.CO2026

A Counting Lemma for Somewhat Restricted 3-APs

Amey Bhangale, Subhash Khot, Yang P. Liu +1

For a prime $p \geq 3$ , a somewhat restricted $3$ -AP in $F_{p}^{n}$ is a triplet $(x, x + a, x + 2 a)$ , where $x \in F_{p}^{n}$ and $a \in {0, 1, 2}^{n}$ . We prove a counting lemma fo…

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…

math.CO2024★ 1 cited

Reasonable Bounds for Combinatorial Lines of Length Three

Amey Bhangale, Subhash Khot, Yang P. Liu +1

We prove that any subset $A \subseteq [3]^{n}$ with $3^{- n} ∣ A ∣ \geq (lo g lo g lo g lo g n)^{- c}$ contains a combinatorial line of length $3$ , i.e., $x, y, z \in A$ , not all equal, with…

cs.CC2024★ 1 cited

On Approximability of Satisfiable $k$ -CSPs: VII

Amey Bhangale, Subhash Khot, Yang P. Liu +1

Let $Σ_{1}, \dots, Σ_{k}$ be finite alphabets, and let $μ$ be a distribution over $Σ_{1} \times \dots \times Σ_{k}$ in which the probability of each atom is at least $α$ . We prove that if $…

cs.CC2024★ 1 cited

On Approximability of Satisfiable $k$ -CSPs: VI

Amey Bhangale, Subhash Khot, Yang P. Liu +1

We prove local and global inverse theorems for general $3$ -wise correlations over pairwise-connected distributions. Let $μ$ be a distribution over $Σ \times Γ \times Φ$ such that the…

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…

A Counting Lemma for Somewhat Restricted 3-APs

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems

Reasonable Bounds for Combinatorial Lines of Length Three

On Approximability of Satisfiable k-CSPs: VII

On Approximability of Satisfiable k-CSPs: VI

Parallel Repetition for 3-Player XOR Games

Parallel Repetition of k-Player Projection Games

On Approximability of Satisfiable $k$ -CSPs: VII

On Approximability of Satisfiable $k$ -CSPs: VI

Parallel Repetition for $3$ -Player XOR Games