A combinatorial characterization of smooth LTCs and applications
From MaRDI portal
Publication:2820271
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
- A lower bound for the nondeterministic space complexity of context-free recognition
- A recursive approach to low complexity codes
- Algebraic property testing: the role of invariance
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Bracket-languages are recognizable in logarithmic space
- Breaking the \(\epsilon\)-soundness bound of the linearity test over GF(2)
- Combinatorial construction of locally testable codes
- Language recognition by marking automata
- Limitation on the Rate of Families of Locally Testable Codes
- Linearity testing in characteristic two
- Locally Testable Codes Require Redundant Testers
- Locally testable codes and PCPs of almost-linear length
- Log Space Recognition and Translation of Parenthesis Languages
- Lower bounds on space complexity for contextfree recognition
- New Extension of the Weil Bound for Character Sums with Applications to Coding
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Regular languages are testable with a constant number of queries
- Robust Characterizations of Polynomials with Applications to Program Testing
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Robust locally testable codes and products of codes
- Self-testing/correcting with applications to numerical problems
- Simple PCPs with poly-log rate and query complexity
- Some 3CNF Properties Are Hard to Test
- Some Results on Tape-Bounded Turing Machines
- Space complexity vs. query complexity
- Tensor products of weakly smooth codes are robust
- Testing Membership in Languages that Have Small Width Branching Programs
- The PCP theorem by gap amplification
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)
