A combinatorial characterization of smooth LTCs and applications
From MaRDI portal
Publication:2820271
DOI10.1002/RSA.20637zbMATH Open1409.94921OpenAlexW2288415650MaRDI QIDQ2820271FDOQ2820271
Authors: Eli Ben-Sasson, Michael Viderman 
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
Recommendations
- Combinatorial construction of locally testable codes (extended abstract)
- Combinatorial construction of locally testable codes
- Locally Testable Codes Require Redundant Testers
- Explicit strong LTCs with inverse poly-log rate and constant soundness
- Dense locally testable codes cannot have constant rate and distance
Cites Work
- Tensor products of weakly smooth codes are robust
- Proof verification and the hardness of approximation problems
- Locally testable codes and PCPs of almost-linear length
- Probabilistic checking of proofs
- Robust locally testable codes and products of codes
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Self-testing/correcting with applications to numerical problems
- Linearity testing in characteristic two
- Robust Characterizations of Polynomials with Applications to Program Testing
- Some 3CNF Properties Are Hard to Test
- New Extension of the Weil Bound for Character Sums with Applications to Coding
- A recursive approach to low complexity codes
- Log Space Recognition and Translation of Parenthesis Languages
- Algebraic property testing: the role of invariance
- Regular languages are testable with a constant number of queries
- Testing Membership in Languages that Have Small Width Branching Programs
- Combinatorial construction of locally testable codes
- Space complexity vs. query complexity
- A lower bound for the nondeterministic space complexity of context-free recognition
- The PCP theorem by gap amplification
- Simple PCPs with poly-log rate and query complexity
- Some Results on Tape-Bounded Turing Machines
- Language recognition by marking automata
- Limitation on the Rate of Families of Locally Testable Codes
- Locally Testable Codes Require Redundant Testers
- Lower bounds on space complexity for contextfree recognition
- Breaking the \(\epsilon\)-soundness bound of the linearity test over GF(2)
- Bracket-languages are recognizable in logarithmic space
Cited In (3)
This page was built for publication: A combinatorial characterization of smooth LTCs and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2820271)
