Buchumschlag

Good Locally Testable Codes with Small Alphabet and Small Query Size

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	First, Uriya, Lazarovici, Stav
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

On Good $2$-Query Locally Testable Codes from Sheaves on High Dimensional Expanders
von: First, Uriya A., et al.
Veröffentlicht: (2022)

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
von: First, Uriya A., et al.
Veröffentlicht: (2024)

The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients
von: First, Uriya A., et al.
Veröffentlicht: (2022)

Hypergraph Samplers: Typical and Worst Case Behavior
von: Alev, Vedat Levi, et al.
Veröffentlicht: (2026)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
von: Jackson, Andrew
Veröffentlicht: (2025)

Explicit Constant-Alphabet Subspace Design Codes
von: Goyal, Rohan, et al.
Veröffentlicht: (2026)

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

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
von: Hsieh, Jun-Ting, et al.
Veröffentlicht: (2024)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
von: Grigorescu, Elena, et al.
Veröffentlicht: (2025)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
von: Basu, Arpon, et al.
Veröffentlicht: (2024)

Width Hierarchy for k-OBDD of Small Width
von: Khadiev, Kamil
Veröffentlicht: (2015)

The Complexity of Contracting Bipartite Graphs into Small Cycles
von: Krithika, R., et al.
Veröffentlicht: (2022)

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

Separating Quantum and Classical Advice with Good Codes
von: Bostanci, John, et al.
Veröffentlicht: (2026)

Alphabet Reduction for Reconfiguration Problems
von: Ohsaka, Naoto
Veröffentlicht: (2024)

A Graphical #SAT Algorithm for Formulae with Small Clause Density
von: Laakkonen, Tuomas, et al.
Veröffentlicht: (2022)

On the Structure of Hamiltonian Graphs with Small Independence Number
von: Jedličková, Nikola, et al.
Veröffentlicht: (2024)

Improved Small Set Expansion in High Dimensional Expanders
von: Kaufman, Tali, et al.
Veröffentlicht: (2025)

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

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
von: Bharadwaj, G V Sumukha, et al.
Veröffentlicht: (2024)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
von: Alrabiah, Omar, et al.
Veröffentlicht: (2024)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
von: Li, Xin, et al.
Veröffentlicht: (2024)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
von: Drucker, Andrew, et al.
Veröffentlicht: (2024)

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
von: Janzer, Oliver, et al.
Veröffentlicht: (2024)

Small Hazard-free Transducers
von: Bund, Johannes, et al.
Veröffentlicht: (2018)

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
von: Durand, Martin
Veröffentlicht: (2026)

Improved List Size for Folded Reed-Solomon Codes
von: Srivastava, Shashank
Veröffentlicht: (2024)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
von: Gur, Tom, et al.
Veröffentlicht: (2025)

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

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

How to Verify that a Small Device is Quantum, Unconditionally
von: Malavolta, Giulio, et al.
Veröffentlicht: (2025)

The Complexity of Counting Small Sub-Hypergraphs
von: Bressan, Marco, et al.
Veröffentlicht: (2025)

The Query Complexity of Local Search in Rounds on General Graphs
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

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)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
von: Curticapean, Radu, et al.
Veröffentlicht: (2025)

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)

Azumaya Algebras With Orthogonal Involution Admitting an Improper Isometry
von: First, Uriya A.
Veröffentlicht: (2022)

Low-Degree Polynomials Are Good Extractors
von: Alrabiah, Omar, et al.
Veröffentlicht: (2024)