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)- An adaptivity hierarchy theorem for property testing
- Proofs of proximity for context-free languages and read-once branching programs
- Non-interactive proofs of proximity
- Fast approximate probabilistically checkable proofs
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Smooth and strong PCPs
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- \textsc{Fractal}: post-quantum and transparent recursive proofs from holography
- On hitting-set generators for polynomials that vanish rarely
- A PCP of proximity for real algebraic polynomials
- Succinct non-interactive arguments via linear interactive proofs
- ZK-PCPs from leakage-resilient secret sharing
- A PCP theorem for interactive proofs and applications
- Linear-size constant-query IOPs for delegating computation
- On the (In)security of Kilian-based SNARGs
- PCPs and the hardness of generating synthetic data
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Low-degree test with polynomially small error
- Combinatorial PCPs with short proofs
- Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- scientific article; zbMATH DE number 1688375 (Why is no real title available?)
- Quasi-linear size zero knowledge from linear-algebraic PCPs
- Bounds on 2-query locally testable codes with affine tests
- A combinatorial characterization of smooth LTCs and applications
- A PCP characterization of AM
- Efficient Probabilistically Checkable Debates
- Short locally testable codes and proofs
- Bravely, moderately: a common theme in four recent works
- Probabilistically checkable proofs and codes
- Constant rate PCPs for circuit-SAT with sublinear query complexity
- Proofs of proximity for context-free languages and read-once branching programs
- Quantum locally testable codes
- Arguments of proximity (extended abstract)
- Verifying and decoding in constant depth
- Two-query PCP with subconstant error
- Robust PSPs of proximity, shorter PSPs and applications to coding
- Short PCPs with Polylog Query Complexity
- The tensor product of two good codes is not necessarily robustly testable
- On the rectangle method in proofs of robustness of tensor products
- Erasure-Resilient Property Testing
- Combinatorial PCPs with efficient verifiers
- On uniformity and circuit lower bounds
- New direct-product testers and 2-query PCPs
- Limitation on the Rate of Families of Locally Testable Codes
- Short locally testable codes and proofs: a survey in two parts
- Invariance in property testing
- Composition of low-error 2-query PCPs using decodable PCPs
- Shorter arithmetization of nondeterministic computations
- Composition of semi-LTCs by two-wise tensor products
- On the power of relaxed local decoding algorithms
- Relaxed locally correctable codes
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- Proofs of proximity for distribution testing
- Constant-round interactive proofs for delegating computation
- On axis-parallel tests for tensor product codes
- Fast Reed-Solomon interactive oracle proofs of proximity
- An exponential separation between MA and AM proofs of proximity
- scientific article; zbMATH DE number 7376033 (Why is no real title available?)
- Brief announcement: Erasure-resilience versus tolerance to errors
- Explicit strong LTCs with inverse poly-log rate and constant soundness
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- Hamiltonian sparsification and gap-simulation
- Probabilistic checking against non-signaling strategies from linearity testing
- From Local to Robust Testing via Agreement Testing
- Every Set in P Is Strongly Testable Under a Suitable Encoding
- Erasures vs. errors in local decoding and property testing
- From local to robust testing via agreement testing
- Bridging a Small Gap in the Gap Amplification of Assignment Testers
- On axis-parallel tests for tensor product codes
- Short PCPs with projection queries
- New direct-product testers and 2-query PCPs
- A combination of testability and decodability by tensor products
- Computational integrity with a public random string from quasi-linear PCPs
- Composition of low-error 2-query PCPs using decodable PCPs
- Constructing high order elements through subspace polynomials
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Relaxed locally correctable codes
- Efficient Construction of Rigid Matrices Using an NP Oracle
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- Sound 3-query PCPPs are long
- Sound 3-Query PCPPs Are Long
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Erasures versus errors in local decoding and property testing
- Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Succinct arguments for RAM programs via projection codes
- Sub-constant error probabilistically checkable proof of almost-linear size
- Derandomized parallel repetition via structured PCPs
- Rigid matrices from rectangular PCPs
- When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems
- Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
- Robustly self-ordered graphs: constructions and applications to property testing
- Testing distributions of huge objects
- Complexity theory. Abstracts from the workshop held June 2--7, 2024
- Asymptotically-good RLCCs with \((\log n)^{2+o(1)}\) queries
- Alphabet reduction for reconfiguration problems
- Linear relaxed locally decodable and correctable codes do not need adaptivity and two-sided error
- On testing group properties
- On the relaxed LDC of BGHSV: a survey that corrects the record
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)
