Imagen de Portada

Improved Parallel Repetition for GHZ-Supported Games via Spreadness

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Liu, Yang P., Lovett, Shachar, Mittal, Kunal
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
por: Bhangale, Amey, et al.
Publicado: (2025)

Corners in Quasirandom Groups via Sparse Mixing
por: Jaber, Michael, et al.
Publicado: (2024)

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

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
por: Chattopadhyay, Arkadev, et al.
Publicado: (2025)

The Log-Rank Conjecture: New Equivalent Formulations
por: Hambardzumyan, Lianna, et al.
Publicado: (2025)

List Decoding Quotient Reed-Muller Codes
por: Gotlib, Omri, et al.
Publicado: (2025)

Refuting approaches to the log-rank conjecture for XOR functions
por: Hatami, Hamed, et al.
Publicado: (2023)

Quasipolynomial bounds for the corners theorem
por: Jaber, Michael, et al.
Publicado: (2025)

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

Explicit separations between randomized and deterministic Number-on-Forehead communication
por: Kelley, Zander, et al.
Publicado: (2023)

Certificate Games and Consequences for the Classical Adversary Bound
por: Chakraborty, Sourav, et al.
Publicado: (2022)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
por: Komarath, Balagopal, et al.
Publicado: (2026)

Computational Complexity of Game Boy Games
por: Tirmazi, Hayder, et al.
Publicado: (2024)

Superposition detection and QMA with non-collapsing measurements
por: Bassirian, Roozbeh, et al.
Publicado: (2024)

On Efficient Computation of DiRe Committees
por: Relia, Kunal
Publicado: (2024)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
por: Han, Zicheng, et al.
Publicado: (2026)

Game Derandomization
por: Epstein, Samuel
Publicado: (2024)

Pseudorandomness of Expander Walks via Fourier Analysis on Groups
por: Jeronimo, Fernando Granha, et al.
Publicado: (2025)

Approximate Degree Composition for Recursive Functions
por: Chakraborty, Sourav, et al.
Publicado: (2024)

On query complexity measures and their relations for symmetric functions
por: Mittal, Rajat, et al.
Publicado: (2021)

Breaking the Temporal Complexity Barrier: Bucket Calculus for Parallel Machine Scheduling
por: Mohammad, Noor Islam S.
Publicado: (2026)

A complexity phase transition at the EPR Hamiltonian
por: Marwaha, Kunal, et al.
Publicado: (2026)

Work-Efficient Parallel Counting via Sampling
por: Liu, Hongyang, et al.
Publicado: (2024)

On the Complexity of Decoded Quantum Interferometry
por: Marwaha, Kunal, et al.
Publicado: (2025)

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
por: Mao, Xinyu, et al.
Publicado: (2024)

Bounds for Hardness Condensation in the Query Model
por: Kayal, Chandrima, et al.
Publicado: (2026)

Parallel Play Saves Quantifiers
por: Carmosino, Marco, et al.
Publicado: (2024)

A General Framework for Low Soundness Homomorphism Testing
por: Mittal, Tushant, et al.
Publicado: (2025)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
por: MIT Hardness Group, et al.
Publicado: (2024)

Relations between monotone complexity measures based on decision tree complexity
por: Byramji, Farzan, et al.
Publicado: (2024)

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
por: Li, Shuangle, et al.
Publicado: (2024)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
por: Guruswami, Venkatesan, et al.
Publicado: (2021)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
por: MIT Hardness Group, et al.
Publicado: (2024)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
por: Gryaznov, Svyatoslav, et al.
Publicado: (2024)

Correction to “The Spread of Information in Virtual Communities”
Publicado: (2025)

Explicit Codes approaching Generalized Singleton Bound using Expanders
por: Jeronimo, Fernando Granha, et al.
Publicado: (2025)

Quantum Merlin-Arthur with an internally separable proof
por: Bassirian, Roozbeh, et al.
Publicado: (2024)

Ruling Out Low-rank Matrix Multiplication Tensor Decompositions with Symmetries via SAT
por: Yang, Jason
Publicado: (2024)

Improving the Leading Constant of Matrix Multiplication
por: Alman, Josh, et al.
Publicado: (2024)