Some 3CNF properties are hard to test

No abstract is available for this paper.

• Publication year

  2003

• Venue

  Symposium on the Theory of Computing

• Publication date

  2003-06-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/780542.780594
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Testing graphs for colorability properties *

  2005cited by this paper
• THE ART OF UNINFORMED DECISIONS: A PRIMER TO PROPERTY TESTING

  2004cited by this paper
• Low-Density Parity-Check Codes

  2004influential reference
• Robust pcps of proximity, shorter pcps and applications to coding

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

  2003cited by this paper
• TESTING MEMBERSHIP IN LANGUAGES THAT HAVE SMALL WIDTH BRANCHING PROGRAMS

  2002cited by this paper
• CNF Properties are Hard to Test

  2002cited by this paper
• Locally testable codes and PCPs of almost-linear length

  2002cited by this paper
• A lower bound for testing 3-colorability in bounded-degree graphs

  2002influential reference
• Testing satisfiability

  2002cited by this paper
• Monotonicity testing over general poset domains

  2002cited by this paper
• Functions that have read-twice constant width branching programs are not necessarily testable

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

  2002cited by this paper
• Three theorems regarding testing graph properties

  2001cited by this paper
• Testing graphs for colorable properties

  2001cited by this paper
• Efficient Testing of Large Graphs

  2000cited by this paper
• Regular languages are testable with a constant number of queries

  1999cited by this paper
• Robust Chara terizations of Polynomials withAppli ations to Program Testing

  1996cited 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
• Computationally efficient error-correcting codes and holographic proofs

  1995influential reference
• Self-testing/correcting with applications to numerical problems

  1990cited by this paper
• Many hard examples for resolution

  1988influential reference
• Cambridge

  1969cited by this paper
• EÆ ient testing of large graphs

  year unknowncited by this paper

• Stability of homomorphisms, coverings and cocycles II: Examples, applications and open problems

  2025cites this paper
• Cocycle stability in permutations of random simplicial complexes

  2025cites this paper
• Improved energy barrier in higher-dimensional hypergraph product codes

  2025cites this paper
• Computational Complexity in Property Testing

  2025influential citation
• Stability of Homomorphisms, Coverings and Cocycles II: Examples, Applications and Open problems

  2023cites this paper
• Stability of homomorphisms, coverings and cocycles I: equivalence

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

  2023cites this paper
• Low-Degree Testing Over Grids

  2023cites this paper
• Testing of Index-Invariant Properties in the Huge Object Model

  2022cites this paper
• Good Locally Testable Codes

  2022cites this paper
• Explicit uniquely decodable codes for space bounded channels that achieve list-decoding capacity

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

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

  2021influential citation
• Locally testable codes with constant rate, distance, and locality

  2021influential citation
• The Subgraph Testing Model

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

  2020cites this paper
• Teaching Experience

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

  2020cites this paper
• On Local Testability in the Non-Signaling Setting

  2019cites this paper
• Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory

  2019cites this paper
• Approximating Constraint Satisfaction Problems on High-Dimensional Expanders

  2019cites this paper
• BIROn - Birkbeck Institutional Research Online

  2019influential citation
• Erasures vs. Errors in Local Decoding and Property Testing

  2019cites this paper
• Constant-Query Testability of Assignments to Constraint Satisfaction Problems

  2019influential citation
• LOCAL TESTING OF LATTICES∗

  2018cites this paper
• The Complexity of User Retention

  2018cites this paper
• From Local to Robust Testing via Agreement Testing

  2018cites this paper
• Partial Fulfillment of The Requirements for the Degree of Master of Science in Computer Science Eden Saig

  2018cites this paper
• C C ] 23 A ug 2 01 3 Locally Testable Codes and Cayley Graphs

  2018cites this paper
• Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP ∗ Oded Goldreich

  2018cites this paper
• An adaptivity hierarchy theorem for property testing

  2017cites this paper
• Local decoding and testing of polynomials over grids

  2017cites this paper
• Collaborative Discovery: A study of Guru-follower dynamics

  2017cites this paper
• Zero Knowledge Protocols from Succinct Constraint Detection

  2017cites this paper
• Bounds on 2-query Locally Testable Codes with affine tests

  2016cites this paper
• Multi-variate Abstractions of Algebraic Geometry Codes, With Applications

  2016cites this paper
• Testing Read-Once Formula Satisfaction

  2016cites this paper
• The Power and Limitations of Uniform Samples in Testing Properties of Figures

  2016cites this paper
• Local Testing for Membership in Lattices

  2016influential citation
• Erasure-Resilient Property Testing

  2016cites this paper
• Lecture Notes on Locally Testable Codes and Proofs

  2016influential citation
• On Probabilistic Checking in Perfect Zero Knowledge

  2016cites this paper
• A combinatorial characterization of smooth LTCs and applications

  2016influential citation
• Secure Computation and Probabilistic Checking

  2016cites this paper
• Testing Assignments to Constraint Satisfaction Problems

  2016cites this paper
• Locally Testable Codes

  2016cites this paper
• Symmetric LDPC codes and local testing

  2016cites this paper
• Local Hamiltonians Whose Ground States Are Hard to Approximate

  2015cites this paper
• New Directions in Coding Theory : Capacity and Limitations

  2015cites this paper
• Local Hamiltonians with No Low-energy Trivial States

  2015cites this paper
• Quantum Expander Codes

  2015cites this paper
• Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability

  2015cites this paper
• Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

  2015cites this paper
• Locally Testable Codes and Small-Set Expanders Guru Guruganesh December 8 , 2014 A report based on the paper “ Making the Long Code Shorter , with applications to the Unique Games Conjecture

  2014cites this paper
• Additive combinatorics methods in computational complexity

  2014cites this paper
• Succinct Computational Integrity (SCI) and Probabilistically Checkable Proofs (PCP)

  2014cites this paper
• Locally testable codes and cayley graphs

  2013cites this paper
• Commuting Local Hamiltonians on Expanders, Locally Testable Quantum codes, and the qPCP conjecture

  2013cites this paper
• Strong LTCs with Inverse Polylogarithmic Rate and Soundness

  2013cites this paper
• High dimensional expanders and property testing

  2013cites this paper
• Testing Membership in Counter Automaton Languages

  2013cites this paper
• A new family of locally correctable codes based on degree-lifted algebraic geometry codes

  2013cites this paper
• Zero Knowledge LTCs and Their Applications

  2013cites this paper
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing

  2013cites this paper
• Strong LTCs with Inverse Poly-Log Rate and Constant Soundness

  2013cites this paper
• An Algebraic Characterization of Testable Boolean CSPs

  2013cites this paper
• On the concrete efficiency of probabilistically-checkable proofs

  2013cites this paper
• On the power of conditional samples in distribution testing

  2012cites this paper
• On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

  2012cites this paper
• Sparse affine-invariant linear codes are locally testable

  2012cites this paper
• Cs 59000 Ctt Current Topics in Theoretical Cs Lecture 20

  2012cites this paper
• A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes

  2012cites this paper
• Towards lower bounds on locally testable codes

  2012influential citation
• Some closure features of locally testable affine-invariant properties

  2012influential citation
• Testing Formula Satisfaction

  2012cites this paper
• Locally Testable Codes and Expanders Irit Dinur

  2012cites this paper
• Testing list H-homomorphisms

  2011cites this paper
• Reseach of security risk identification based on rough set theory for highway subgrade stability in the slope of reservoir

  2011cites this paper
• Characterizations of locally testable linear- and affine-invariant families

  2011cites this paper
• Towards lower bounds on locally testable codes via density arguments

  2011cites this paper
• Symmetric LDPC Codes are not Necessarily Locally Testable

  2011cites this paper
• Limits on the Rate of Locally Testable Affine-Invariant Codes

  2011cites this paper
• Testing Linear Properties: Some general themes

  2011cites this paper
• Testability of linear-invariant properties

  2011cites this paper
• A combination of testability and decodability by tensor products

  2011cites this paper
• Guest column: testing linear properties: some general theme

  2011cites this paper
• Short Locally Testable Codes and Proofs

  2011cites this paper
• Algebraic Property Testing

  2011influential citation
• Framework for Testing Linear-Invariant Properties

  2011cites this paper
• A query efficient non‐adaptive long code test with perfect completeness

  2010cites this paper
• Lower bounds for testing triangle-freeness in Boolean functions

  2010cites this paper
• Data Stream Algorithms for Codeword Testing

  2010cites this paper
• Short Locally Testable Codes and Proofs: A Survey in Two Parts

  2010cites this paper
• Invariance in Property Testing

  2010influential citation
• A Unified Framework for Testing Linear-Invariant Properties

  2010cites this paper
• Locally Testable vs. Locally Decodable Codes

  2010cites this paper
• Local computation in codes

  2010cites this paper
• On the Benefits of Adaptivity in Property Testing of Dense Graphs

  2010cites this paper
• Property Testing via Set-Theoretic Operations

  2010cites this paper
• Limitation on the Rate of Families of Locally Testable Codes

  2010cites this paper