Buchumschlag

3-Query RLDCs are Strictly Stronger than 3-Query LDCs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gur, Tom, Minzer, Dor, Weissenberg, Guy, Zheng, Kai Zhe
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Near Optimal Hardness of Approximating $k$-CSP
von: Minzer, Dor, et al.
Veröffentlicht: (2025)

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

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
von: Cheng, Kuan, et al.
Veröffentlicht: (2026)

Near Optimal Alphabet-Soundness Tradeoff PCPs
von: Minzer, Dor, et al.
Veröffentlicht: (2024)

The Lens of Abelian Embeddings
von: Minzer, Dor
Veröffentlicht: (2026)

A Distance Amplification Lemma for Monotonicity
von: Minzer, Dor
Veröffentlicht: (2025)

Characterizing Direct Product Testing via Coboundary Expansion
von: Bafna, Mitali, et al.
Veröffentlicht: (2023)

On Approximability of Satisfiable k-CSPs: V
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Quasi-Linear Size PCPs with Small Soundness from HDX
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

Constant Degree Direct Product Testers with Small Soundness
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable k-CSPs: IV
von: Bhangale, Amey, et al.
Veröffentlicht: (2023)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

An Invariance Principle for the Multi-slice, with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2021)

Parallel Repetition for $3$-Player XOR Games
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

On Approximability of Satisfiable $k$-CSPs: VI
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

A Strong Direct Sum Theorem for Distributional Query Complexity
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
von: Bhangale, Amey, et al.
Veröffentlicht: (2025)

Query Complexity with Unknowns
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
von: Arunachalam, Srinivasan, et al.
Veröffentlicht: (2021)

Sensitivity and Query Complexity under Uncertainty
von: Benson, Deepu, et al.
Veröffentlicht: (2025)

Bounds for Hardness Condensation in the Query Model
von: Kayal, Chandrima, et al.
Veröffentlicht: (2026)

Diversity of Answers to Conjunctive Queries
von: Merkl, Timo Camillo, et al.
Veröffentlicht: (2023)

Direct Product Theorems for Randomized Query Complexity
von: Ben-David, Shalev, et al.
Veröffentlicht: (2025)

Consistent Query Answering over SHACL Constraints
von: Ahmetaj, Shqiponja, et al.
Veröffentlicht: (2024)

Product Mixing in Compact Lie Groups
von: Ellis, David, et al.
Veröffentlicht: (2024)

Pseudo-deterministic Quantum Algorithms
von: Aaronson, Hugo, et al.
Veröffentlicht: (2026)

Lower Bounds for Conjunctive Query Evaluation
von: Mengel, Stefan
Veröffentlicht: (2025)

Distribution-Free Proofs of Proximity
von: Aaronson, Hugo, et al.
Veröffentlicht: (2023)

Query-Efficient Fixpoints of $\ell_p$-Contractions
von: Haslebacher, Sebastian, et al.
Veröffentlicht: (2025)

Query Lower Bounds for Correlation Clustering under Memory Constraints
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

Towards Parameterized Hardness on Maintaining Conjunctive Queries
von: Wang, Qichen
Veröffentlicht: (2026)

Symmetric quantum computation
von: Castro-Silva, Davi, et al.
Veröffentlicht: (2025)

A Zero-Knowledge PCP Theorem
von: Gur, Tom, et al.
Veröffentlicht: (2024)

Good Locally Testable Codes with Small Alphabet and Small Query Size
von: First, Uriya, et al.
Veröffentlicht: (2025)

Query complexity of Boolean functions on the middle slice of the cube
von: Gerbner, Dániel, et al.
Veröffentlicht: (2023)

Quantum Communication Advantage in TFNP
von: Göös, Mika, et al.
Veröffentlicht: (2024)