Imagen de Portada

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bhangale, Amey, Braverman, Mark, Khot, Subhash, Liu, Yang P., Minzer, Dor, Mittal, Kunal
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Parallel Repetition for $3$-Player XOR Games
por: Bhangale, Amey, et al.
Publicado: (2024)

On Approximability of Satisfiable k-CSPs: V
por: Bhangale, Amey, et al.
Publicado: (2024)

On Approximability of Satisfiable k-CSPs: IV
por: Bhangale, Amey, et al.
Publicado: (2023)

On Approximability of Satisfiable $k$-CSPs: VI
por: Bhangale, Amey, et al.
Publicado: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
por: Bhangale, Amey, et al.
Publicado: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
por: Bhangale, Amey, et al.
Publicado: (2024)

An Invariance Principle for the Multi-slice, with Applications
por: Braverman, Mark, et al.
Publicado: (2021)

Biased Linearity Testing in the 1% Regime
por: Khot, Subhash, et al.
Publicado: (2025)

Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$
por: Bhangale, Amey, et al.
Publicado: (2023)

Near Optimal Hardness of Approximating $k$-CSP
por: Minzer, Dor, et al.
Publicado: (2025)

Improved Parallel Repetition for GHZ-Supported Games via Spreadness
por: Liu, Yang P., et al.
Publicado: (2026)

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
por: Mittal, Kunal
Publicado: (2025)

The Lens of Abelian Embeddings
por: Minzer, Dor
Publicado: (2026)

Characterizing Direct Product Testing via Coboundary Expansion
por: Bafna, Mitali, et al.
Publicado: (2023)

A Distance Amplification Lemma for Monotonicity
por: Minzer, Dor
Publicado: (2025)

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
por: Bhangale, Amey, et al.
Publicado: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2025)

Improved Round-by-round Soundness IOPs via Reed-Muller Codes
por: Minzer, Dor, et al.
Publicado: (2025)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
por: S., Karthik C., et al.
Publicado: (2021)

Quasi-Linear Size PCPs with Small Soundness from HDX
por: Bafna, Mitali, et al.
Publicado: (2024)

Constant Degree Direct Product Testers with Small Soundness
por: Bafna, Mitali, et al.
Publicado: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
por: Minzer, Dor, et al.
Publicado: (2024)

Near-Optimal Space Lower Bounds for Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2026)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
por: Gur, Tom, et al.
Publicado: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
por: Fei, Yumou, et al.
Publicado: (2025)

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
por: Barto, Libor, et al.
Publicado: (2021)

Baby PIH: Parameterized Inapproximability of Min CSP
por: Guruswami, Venkatesan, et al.
Publicado: (2023)

Strongly Refuting Random CSP without Literals
por: Chan, Siu On, et al.
Publicado: (2026)

Proof complexity of Mal'tsev CSP
por: Gaysin, Azza
Publicado: (2025)

Optimality of Frequency Moment Estimation
por: Braverman, Mark, et al.
Publicado: (2024)

Dichotomies for \#CSP on graphs that forbid a clique as a minor
por: Meng, Boning, et al.
Publicado: (2025)

Undirected Multicast Network Coding Gaps via Locally Decodable Codes
por: Braverman, Mark, et al.
Publicado: (2025)

Modular Counting CSP: Reductions and Algorithms
por: Kazeminia, Amirhossein, et al.
Publicado: (2025)

The Richness of CSP Non-redundancy
por: Brakensiek, Joshua, et al.
Publicado: (2025)

Hardness of Approximate Hylland-Zeckhauser Equilibria
por: Braverman, Mark, et al.
Publicado: (2026)

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

Streaming approximation resistance of every ordering CSP
por: Singer, Noah G., et al.
Publicado: (2021)

KRW Composition Theorems via Lifting
por: de Rezende, Susanna F., et al.
Publicado: (2020)

A New Information Complexity Measure for Multi-pass Streaming with Applications
por: Braverman, Mark, et al.
Publicado: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
por: S., Karthik C., et al.
Publicado: (2023)