Robust pcps of proximity, shorter pcps and applications to coding

No abstract is available for this paper.

• Publication year

  2004

• Venue

  Symposium on the Theory of Computing

• Publication date

  2004-06-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1007352.1007361
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The PCP theorem by gap amplification

  2006cited by this paper
• Sub-constant error low degree test of almost-linear size

  2006cited by this paper
• Lower bounds for adaptive locally decodable codes

  2005cited by this paper
• Simple PCPs with poly-log rate and query complexity

  2005cited by this paper
• Short PCPs verifiable in polylogarithmic time

  2005cited by this paper
• Lower bounds for testing bipartiteness in dense graphs

  2004influential reference
• Fast approximate probabilistically checkable proofs

  2004cited by this paper
• Assignment testers: towards a combinatorial proof of the PCP-theorem

  2004cited by this paper
• Some 3CNF properties are hard to test

  2003cited by this paper
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets

  2003influential reference
• Locally testable codes and PCPs of almost-linear length

  2002influential reference
• A lower bound for testing 3-colorability in bounded-degree graphs

  2002cited by this paper
• Lecture 20: Boosting

  2002cited by this paper
• Exponential lower bound for 2-query locally decodable codes via a quantum argument

  2002cited by this paper
• Property Testing in Bounded Degree Graphs

  2002cited by this paper
• Breaking the O(n/sup 1/(2k-1)/) barrier for information-theoretic Private Information Retrieval

  2002cited by this paper
• Better lower bounds for locally decodable codes

  2002cited by this paper
• Some optimal inapproximability results

  2001cited by this paper
• How to go beyond the black-box simulation barrier

  2001cited by this paper
• A PCP characterization of NP with optimal amortized query complexity

  2000cited by this paper
• The random oracle methodology, revisited

  2000cited by this paper
• On the efficiency of local decoding procedures for error-correcting codes

  2000influential reference
• Computationally Sound Proofs

  2000cited by this paper
• Small PCPs with low query complexity

  2000influential reference
• Fast approximate PCPs

  1999influential reference
• Many-Valued Logics and Holographic Proofs

  1999cited by this paper
• Probabilistic checking of proofs: a new characterization of NP

  1998influential reference
• A Sample of Samplers - A Computational Perspective on Sampling (survey)

  1997cited by this paper
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem

  1997cited by this paper
• Robust Characterizations of Polynomials with Applications to Program Testing

  1996cited by this paper
• Property testing and its connection to learning and approximation

  1996influential reference
• Interactive proofs and the hardness of approximating cliques

  1996cited by this paper
• Linear-time encodable and decodable error-correcting codes

  1995cited by this paper
• Free bits, PCPs and non-approximability-towards tight results

  1995cited by this paper
• "-discrepancy Sets and Their Applications for Interpolation of Sparse Polynomials

  1995cited by this paper
• A parallel repetition theorem

  1995cited by this paper
• Computationally efficient error-correcting codes and holographic proofs

  1995cited by this paper
• On the Power of Multi-Prover Interactive Protocols

  1994cited by this paper
• Nearly-linear size holographic proofs

  1994influential reference
• Constructing Small Sets that are Uniform in Arithmetic Progressions

  1993cited by this paper
• Efficient probabilistically checkable proofs and applications to approximations

  1993cited by this paper
• Eecient Probabilistically Checkable Proofs and Applications to Approximation

  1993cited by this paper
• A note on efficient zero-knowledge proofs and arguments (extended abstract)

  1992cited by this paper
• Proof verification and hardness of approximation problems

  1992cited by this paper
• Simple Construction of Almost k-wise Independent Random Variables

  1992cited by this paper
• Checking computations in polylogarithmic time

  1991influential reference
• Fully parallelized multi prover protocols for NEXP-time

  1991cited by this paper
• Introduction to parallel algorithms and architectures

  1991cited by this paper
• Algebraic methods for interactive proof systems

  1990cited by this paper
• Self-testing/correcting with applications to numerical problems

  1990cited by this paper
• Construction of a thin set with small fourier coefficients

  1990cited by this paper
• Small-bias probability spaces: efficient constructions and applications

  1990cited by this paper
• An estimate for character sums

  1989cited by this paper
• Short Propositional Formulas Represent Nondeterministic Computations

  1988cited by this paper
• On the power of multi-power interactive protocols

  1988cited by this paper
• Relations Among Complexity Measures

  1979cited by this paper
• Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2

  1977cited by this paper
• Schnelle Multiplikation großer Zahlen

  1971cited by this paper
• Two-Tape Simulation of Multitape Turing Machines

  1966cited by this paper

• When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs

  2026cites this paper
• Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks

  2026cites this paper
• Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes

  2026cites this paper
• Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes

  2025cites this paper
• Proving the PCP Theorem with 1.5 proof compositions (or yet another PCP construction)

  2025cites this paper
• PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs

  2025cites this paper
• SIGACT News Complexity Theory Column 126 Locally Decodable Codes for Insertions and Deletions

  2025cites this paper
• Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead

  2025cites this paper
• Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies

  2025influential citation
• New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String

  2025cites this paper
• Amortized Locally Decodable Codes

  2025cites this paper
• On the Power of Computationally Sound Interactive Proofs of Proximity

  2025cites this paper
• Foundations of Data Availability Sampling

  2025cites this paper
• Yet Another Simple Proof of the PCRP Theorem

  2025influential citation
• Ideals, Gröbner Bases, and PCPs

  2025cites this paper
• Amortized Locally Decodable Codes for Insertions and Deletions

  2025cites this paper
• Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin

  2025cites this paper
• Succinct Non-interactive Arguments of Proximity

  2025cites this paper
• Khatam: Reducing the Communication Complexity of Code-Based SNARKs

  2024cites this paper
• How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions

  2024cites this paper
• Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

  2024cites this paper
• Sensitivity Lower Bounds for Approximaiton Algorithms

  2024cites this paper
• Open Problems Column

  2024cites this paper
• On the relaxed LDC of BGHSV: A survey that corrects the record

  2024influential citation
• Locally Testable Tree Codes

  2024influential citation
• Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate

  2024cites this paper
• On the vector subspaces of F2n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {F}_{2^n}$$\end{document} over w

  2024cites this paper
• A Zero-Knowledge PCP Theorem

  2024cites this paper
• Alphabet Reduction for Reconfiguration Problems

  2024influential citation
• Local Proofs Approaching the Witness Length

  2024cites this paper
• Computationally Relaxed Locally Decodable Codes, Revisited

  2023cites this paper
• On the Lower Bound on the Length of Relaxed Locally Decodable Codes

  2023influential citation
• Asymptotically-Good RLCCs with (log n ) 2+ o (1) Queries

  2023cites this paper
• Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms

  2023cites this paper
• Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error

  2023influential citation
• Gap Amplification for Reconfiguration Problems

  2023cites this paper
• On Testing Group Properties

  2023cites this paper
• Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols

  2023cites this paper
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis

  2023cites this paper
• IOPs with Inverse Polynomial Soundness Error

  2023cites this paper
• Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

  2023influential citation
• Relaxed Local Correctability from Local Testing

  2023influential citation
• Distribution-Free Proofs of Proximity

  2023cites this paper
• On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

  2023cites this paper
• Towards Stronger Depth Lower Bounds

  2023cites this paper
• Parameterized Inapproximability Hypothesis under ETH

  2023cites this paper
• Regularization of Low Error PCPs and an Application to MCSP

  2023cites this paper
• On Hitting-Set Generators for Polynomials that Vanish Rarely

  2022cites this paper
• Testing Distributions of Huge Objects

  2022cites this paper
• Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

  2022cites this paper
• Linear-Time Probabilistic Proofs Over Every Field

  2022cites this paper
• On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors

  2022cites this paper
• Verifiable and Provably Secure Machine Unlearning

  2022cites this paper
• Shielding Probabilistically Checkable Proofs: Zero-Knowledge PCPs from Leakage Resilience

  2022cites this paper
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

  2022cites this paper
• Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE

  2022cites this paper
• A PCP Theorem for Interactive Proofs and Applications

  2022cites this paper
• c3-Locally Testable Codes from Lossless Expanders

  2022cites this paper
• MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate Amicably

  2022cites this paper
• ZK-PCPs from Leakage-Resilient Secret Sharing

  2022cites this paper
• On the Range Avoidance Problem for Circuits

  2022influential citation
• MIP* = RE

  2021cites this paper
• Memory-Hard Puzzles in the Standard Model with Applications to Memory-Hard Functions and Resource-Bounded Locally Decodable Codes

  2021cites this paper
• Smooth and Strong PCPs

  2021cites this paper
• PCPs and Instance Compression from a Cryptographic Lens

  2021cites this paper
• Erasures versus errors in local decoding and property testing

  2021cites this paper
• Robustly self-ordered graphs: constructions and applications to property testing

  2021cites this paper
• Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma

  2021cites this paper
• Quantum Proofs of Proximity

  2021cites this paper
• Lifted Reed-Solomon Codes and Lifted Multiplicity Codes

  2021cites this paper
• Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP

  2021cites this paper
• Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions

  2021cites this paper
• Locally testable codes with constant rate, distance, and locality

  2021cites this paper
• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

  2020influential citation
• On Axis-Parallel Tests for Tensor Product Codes

  2020cites this paper
• Bridging a Small Gap in the Gap Amplification of Assignment Testers

  2020cites this paper
• A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification

  2020cites this paper
• Black-Box Constructions of Bounded-Concurrent Secure Computation

  2020cites this paper
• Local Proofs Approaching the Witness Length [Extended Abstract]

  2020cites this paper
• Fractal: Post-Quantum and Transparent Recursive Proofs from Holography

  2020cites this paper
• On the Power of Relaxed Local Decoding Algorithms

  2020influential citation
• Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

  2020cites this paper
• Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

  2020cites this paper
• Teaching Experience

  2020cites this paper
• Relaxed Locally Correctable Codes with Improved Parameters

  2020cites this paper
• PCPs and the Hardness of Generating Synthetic Data

  2020cites this paper
• Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs

  2020cites this paper
• Locally testable codes via high-dimensional expanders

  2020cites this paper
• Lifted Multiplicity Codes

  2020cites this paper
• A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy

  2020cites this paper
• Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation

  2020cites this paper
• On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract

  2020cites this paper
• On Locally Decodable Codes in Resource Bounded Channels

  2019cites this paper
• Towards dependable and trustworthy outsourced computing: A comprehensive survey and tutorial

  2019cites this paper
• C C ] 7 S ep 2 01 9 Hard properties with ( very ) short PCPPs and their applications

  2019cites this paper
• DEEP-FRI: Sampling outside the box improves soundness

  2019cites this paper
• Efficient Construction of Rigid Matrices Using an NP Oracle

  2019cites this paper
• Computation Verification for Noobs

  2019influential citation
• Hardness of Approximation Between P and NP

  2019cites this paper
• Hard properties with (very) short PCPPs and their applications

  2019cites this paper