Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
From MaRDI portal
Recommendations
- Robust PSPs of proximity, shorter PSPs and applications to coding
- Approximability of Dense Instances of Nearest Codeword Problem
- Deterministic Approximation Algorithms for the Nearest Codeword Problem
- A new construction of minimum distance robust codes
- scientific article; zbMATH DE number 3985112
- scientific article; zbMATH DE number 3793938
- Locally testable codes and PCPs of almost-linear length
- On computing nearest neighbors with applications to decoding of binary linear codes
- Bounds for binary codes relative to pseudo-distances of \(k\) points
- Approximability of identifying codes and locating-dominating codes
Cited in
(only showing first 100 items - show all)- Short PCPs with Polylog Query Complexity
- On axis-parallel tests for tensor product codes
- Low-degree test with polynomially small error
- Towards stronger depth lower bounds
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- Proving as fast as computing: succinct arguments with constant prover overhead
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Explicit strong LTCs with inverse poly-log rate and constant soundness
- Complexity theory. Abstracts from the workshop held June 2--7, 2024
- Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
- Probabilistically checkable proofs and codes
- Bravely, moderately: a common theme in four recent works
- Efficient construction of rigid matrices using an NP oracle
- Limitation on the Rate of Families of Locally Testable Codes
- Short PCPs with projection queries
- PCPs and the hardness of generating synthetic data
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- New direct-product testers and 2-query PCPs
- Robustly self-ordered graphs: constructions and applications to property testing
- Robust PSPs of proximity, shorter PSPs and applications to coding
- On hitting-set generators for polynomials that vanish rarely
- Every Set in P Is Strongly Testable Under a Suitable Encoding
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Regularization of low error PCPs and an application to MCSP
- Hamming weight proofs of proximity with one-sided error
- Combinatorial PCPs with short proofs
- On the (In)security of Kilian-based SNARGs
- Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
- Erasure-Resilient Property Testing
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Towards lower bounds on locally testable codes via density arguments
- Testing distributions of huge objects
- Succinct arguments for RAM programs via projection codes
- Bridging a Small Gap in the Gap Amplification of Assignment Testers
- Derandomized parallel repetition via structured PCPs
- From local to robust testing via agreement testing
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- A PCP of proximity for real algebraic polynomials
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Bounds on 2-query locally testable codes with affine tests
- Proofs of proximity for context-free languages and read-once branching programs
- Non-interactive proofs of proximity
- An adaptivity hierarchy theorem for property testing
- Short locally testable codes and proofs: a survey in two parts
- On the power of relaxed local decoding algorithms
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Fast approximate probabilistically checkable proofs
- Composition of low-error 2-query PCPs using decodable PCPs
- The tensor product of two good codes is not necessarily robustly testable
- On the rectangle method in proofs of robustness of tensor products
- A combination of testability and decodability by tensor products
- New direct-product testers and 2-query PCPs
- Efficient Probabilistically Checkable Debates
- Succinct non-interactive arguments via linear interactive proofs
- Composition of low-error 2-query PCPs using decodable PCPs
- Erasures versus errors in local decoding and property testing
- Efficient Construction of Rigid Matrices Using an NP Oracle
- Proofs of proximity for context-free languages and read-once branching programs
- Relaxed locally correctable codes
- scientific article; zbMATH DE number 7376033 (Why is no real title available?)
- Smooth and strong PCPs
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- Arguments of proximity (extended abstract)
- Two-query PCP with subconstant error
- Local proofs approaching the witness length
- Constant rate PCPs for circuit-SAT with sublinear query complexity
- Probabilistic checking against non-signaling strategies from linearity testing
- Sound 3-query PCPPs are long
- Constructing high order elements through subspace polynomials
- ZK-PCPs from leakage-resilient secret sharing
- Proofs of proximity for distribution testing
- An exponential separation between MA and AM proofs of proximity
- Relaxed locally correctable codes
- Relaxed locally correctable codes with improved parameters
- A PCP characterization of AM
- Erasures vs. errors in local decoding and property testing
- Quasi-linear size zero knowledge from linear-algebraic PCPs
- Short locally testable codes and proofs
- Computational integrity with a public random string from quasi-linear PCPs
- Sub-constant error probabilistically checkable proof of almost-linear size
- Characterizations of locally testable linear- and affine-invariant families
- Fast Reed-Solomon interactive oracle proofs of proximity
- \textsc{Fractal}: post-quantum and transparent recursive proofs from holography
- A combinatorial characterization of smooth LTCs and applications
- scientific article; zbMATH DE number 1688375 (Why is no real title available?)
- Asymptotically-good RLCCs with \((\log n)^{2+o(1)}\) queries
- Linear-size constant-query IOPs for delegating computation
- On axis-parallel tests for tensor product codes
- Combinatorial PCPs with efficient verifiers
- On uniformity and circuit lower bounds
- Alphabet reduction for reconfiguration problems
- Linear relaxed locally decodable and correctable codes do not need adaptivity and two-sided error
- Invariance in property testing
- On testing group properties
- On the relaxed LDC of BGHSV: a survey that corrects the record
- On the lower bound on the length of relaxed locally decodable codes
- On the locally testable code of Dinur \textit{et al.} (2021)
- Constant-round interactive proofs for delegating computation
- Rigid matrices from rectangular PCPs
- Verifying and decoding in constant depth
This page was built for publication: Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5757455)
