Bounds on locally testable codes with unique tests

DOI10.1145/2090236.2090253zbMath1347.68169OpenAlexW2002144166MaRDI QIDQ2826056

Gillat Kol, Ran Raz

Publication date: 7 October 2016

Published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2090236.2090253

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Other types of codes (94B60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (3)

Bounds on 2-query locally testable codes with affine tests ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Limitation on the Rate of Families of Locally Testable Codes

Cites Work

• Unnamed Item
• The reproducible properties of correct forecasts
• The dimensions of individual strings and sequences
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• The Complexity of Forecast Testing
• The Well-Calibrated Bayesian
• Asymptotic calibration
• Dimension in Complexity Classes
• Universal prediction
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES

This page was built for publication: Bounds on locally testable codes with unique tests