Some 3CNF Properties Are Hard to Test

DOI10.1137/S0097539704445445MaRDI QIDQ5700567zbMATH OpenFDO

Authors Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

Publication date 28 October 2005

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

Full work available at URL https://doi.org/10.1137/S0097539704445445

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

(41)

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

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)