:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Gur, Tom, Minzer, Dor, Weissenberg, Guy, Zheng, Kai Zhe
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2512.12960
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
by: Cheng, Kuan, et al.
Published: (2026)

The Lens of Abelian Embeddings
by: Minzer, Dor
Published: (2026)

A Distance Amplification Lemma for Monotonicity
by: Minzer, Dor
Published: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A Strong Direct Sum Theorem for Distributional Query Complexity
by: Blanc, Guy, et al.
Published: (2024)

Product Mixing in Compact Lie Groups
by: Ellis, David, et al.
Published: (2024)

Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
by: Arunachalam, Srinivasan, et al.
Published: (2021)

Query Complexity with Unknowns
by: Mande, Nikhil S., et al.
Published: (2024)

Pseudo-deterministic Quantum Algorithms
by: Aaronson, Hugo, et al.
Published: (2026)

Sensitivity and Query Complexity under Uncertainty
by: Benson, Deepu, et al.
Published: (2025)

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

Diversity of Answers to Conjunctive Queries
by: Merkl, Timo Camillo, et al.
Published: (2023)

Distribution-Free Proofs of Proximity
by: Aaronson, Hugo, et al.
Published: (2023)

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

A Zero-Knowledge PCP Theorem
by: Gur, Tom, et al.
Published: (2024)

Direct Product Theorems for Randomized Query Complexity
by: Ben-David, Shalev, et al.
Published: (2025)

Consistent Query Answering over SHACL Constraints
by: Ahmetaj, Shqiponja, et al.
Published: (2024)

Lower Bounds for Conjunctive Query Evaluation
by: Mengel, Stefan
Published: (2025)

Quantum Communication Advantage in TFNP
by: Göös, Mika, et al.
Published: (2024)

Query-Efficient Fixpoints of $\ell_p$-Contractions
by: Haslebacher, Sebastian, et al.
Published: (2025)

Towards Parameterized Hardness on Maintaining Conjunctive Queries
by: Wang, Qichen
Published: (2026)

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

Query complexity of Boolean functions on the middle slice of the cube
by: Gerbner, Dániel, et al.
Published: (2023)

Good Locally Testable Codes with Small Alphabet and Small Query Size
by: First, Uriya, et al.
Published: (2025)