A combinatorial characterization of smooth LTCs and applications
From MaRDI portal
Publication:2820271
DOI10.1002/rsa.20637zbMath1409.94921OpenAlexW2288415650MaRDI QIDQ2820271
Michael Viderman, Eli Ben-Sasson
Publication date: 15 September 2016
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20637
Cites Work
- Unnamed Item
- Unnamed Item
- Space complexity vs. query complexity
- A lower bound for the nondeterministic space complexity of context-free recognition
- Bracket-languages are recognizable in logarithmic space
- Lower bounds on space complexity for contextfree recognition
- Self-testing/correcting with applications to numerical problems
- Regular Languages are Testable with a Constant Number of Queries
- Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)
- Linearity testing in characteristic two
- Testing Membership in Languages that Have Small Width Branching Programs
- Proof verification and the hardness of approximation problems
- Locally testable codes and PCPs of almost-linear length
- Combinatorial Construction of Locally Testable Codes
- Simple PCPs with poly-log rate and query complexity
- Probabilistic checking of proofs
- A recursive approach to low complexity codes
- Log Space Recognition and Translation of Parenthesis Languages
- Robust Characterizations of Polynomials with Applications to Program Testing
- Limitation on the Rate of Families of Locally Testable Codes
- Locally Testable Codes Require Redundant Testers
- Robust locally testable codes and products of codes
- New Extension of the Weil Bound for Character Sums with Applications to Coding
- Some Results on Tape-Bounded Turing Machines
- Language recognition by marking automata
- Some 3CNF Properties Are Hard to Test
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- The PCP theorem by gap amplification
This page was built for publication: A combinatorial characterization of smooth LTCs and applications
