Some 3CNF Properties Are Hard to Test

DOI10.1137/S0097539704445445MaRDI QIDQ5700567zbMATHFDO

Authors Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

Publication date 28 October 2005

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

lower boundsproperty testinglocally testable codessublinear algorithmsCNF formulae

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Some 3CNF properties are hard to test
• Testing formula satisfaction
• Property testers for dense constraint satisfaction programs on finite domains
• Testing Read-Once Formula Satisfaction
• Linearity testing in characteristic two

Cited in

(40)

• An adaptivity hierarchy theorem for property testing
• Composition of semi-LTCs by two-wise tensor products
• Erasure-Resilient Property Testing
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Hierarchy theorems for property testing
• Lower bounds for testing triangle-freeness in Boolean functions
• From local to robust testing via agreement testing
• A combinatorial characterization of smooth LTCs and applications
• An algebraic characterization of testable Boolean CSPs
• Bounds on 2-query locally testable codes with affine tests
• Characterizations of locally testable linear- and affine-invariant families
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Hierarchy theorems for property testing
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• Symmetric LDPC codes and local testing
• Erasures versus errors in local decoding and property testing
• Erasures vs. errors in local decoding and property testing
• A unified framework for testing linear-invariant properties
• Testing list \(H\)-homomorphisms
• Testing low-degree polynomials over prime fields
• The power and limitations of uniform samples in testing properties of figures
• On the benefits of adaptivity in property testing of dense graphs
• From Local to Robust Testing via Agreement Testing
• Local decoding and testing of polynomials over grids
• Limitation on the Rate of Families of Locally Testable Codes
• The subgraph testing model
• Some 3CNF properties are hard to test
• Invariance in property testing
• Towards lower bounds on locally testable codes via density arguments
• Symmetric LDPC codes and local testing
• Constant-query testability of assignments to constraint satisfaction problems
• Local testing of lattices
• A combination of testability and decodability by tensor products
• Property testing of massively parametrized problems -- a survey
• A query efficient non-adaptive long code test with perfect completeness
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• On the Query Complexity of Testing Orientations for Being Eulerian
• Sparse affine-invariant linear codes are locally testable
• Testing formula satisfaction
• 2-transitivity is insufficient for local testability

This page was built for publication: Some 3CNF Properties Are Hard to Test

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5700567)