scientific article; zbMATH DE number 7330814
From MaRDI portal
Publication:5857610
DOI10.4086/toc.2020.v016a018zbMath1477.68110OpenAlexW3131688971MaRDI QIDQ5857610
Tom Gur, Govind Ramnarayan, Ron D. Rothblum
Publication date: 1 April 2021
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2020.v016a018
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Related Items
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP ⋮ Every Set in P Is Strongly Testable Under a Suitable Encoding
Cites Work
- Unnamed Item
- Unnamed Item
- Combinatorial PCPs with short proofs
- Highly resilient correctors for polynomials
- Self-testing/correcting with applications to numerical problems
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- An adaptivity hierarchy theorem for property testing
- Non-interactive proofs of proximity
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Bounds on the Size of Locally Recoverable Codes
- A Family of Optimal Locally Recoverable Codes
- On the Locality of Codeword Symbols
- Bravely, Moderately: A Common Theme in Four Recent Works
- A linear time erasure-resilient code with nearly optimal recovery
- Proof verification and the hardness of approximation problems
- Locally testable codes and PCPs of almost-linear length
- Towards 3-query locally decodable codes of subexponential length
- Combinatorial Construction of Locally Testable Codes
- Two-query PCP with subconstant error
- Undirected connectivity in log-space
- Probabilistic checking of proofs
- Algebraic methods for interactive proof systems
- Error Detecting and Error Correcting Codes
- High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
- Robust Characterizations of Polynomials with Applications to Program Testing
- 3-Query Locally Decodable Codes of Subexponential Length
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- On the Power of Relaxed Local Decoding Algorithms
- Strong Locally Testable Codes with Relaxed Local Decoders
- How Long Can Optimal Locally Repairable Codes Be?
- Constant-round interactive proofs for delegating computation
- Locally Recoverable Codes on Algebraic Curves
- Introduction to Property Testing
- Class of constructive asymptotically good algebraic codes
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Locally Decodable Codes
- Sound 3-Query PCPPs Are Long
