Testing Basic Boolean Formulae

DOI10.1137/S0895480101407444MaRDI QIDQ4785704zbMATH OpenOpenAlexFDO

Authors Michal Parnas, Dana Ron, Alex Samorodnitsky

Publication date 5 January 2003

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

randomized algorithmsapproximation algorithmsBoolean functionsproperty testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1833420
• Distribution-Free Testing Lower Bounds for Basic Boolean Functions
• Distribution-free testing lower bound for basic Boolean functions
• Testing formula satisfaction
• Tight bounds for the distribution-free testing of monotone conjunctions

Cited in

(31)

• A unified framework for testing linear-invariant properties
• Almost optimal distribution-free junta testing
• scientific article; zbMATH DE number 1833420 (Why is no real title available?)
• Testing juntas
• Testing by implicit learning: a brief survey
• Testing Read-Once Formula Satisfaction
• A canonical form for testing Boolean function properties
• Exploring crypto dark matter: new simple PRF candidates and their applications
• Query-efficient dictatorship testing with perfect completeness
• Local correction of juntas
• Efficient sample extractors for juntas with applications
• On one-sided testing affine subspaces
• Proximity Oblivious Testing and the Role of Invariances
• Lower Bounds for Testing Computability by Small Width OBDDs
• On one-sided testing affine subspaces
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Property testing lower bounds via communication complexity
• Proximity oblivious testing and the role of invariances
• Testing submodularity and other properties of valuation functions
• Testing juntas: a brief survey
• Invariance in property testing
• Efficiently testing sparse \(\text{GF}(2)\) polynomials
• Sample-based high-dimensional convexity testing
• An improved dictatorship test with perfect completeness
• Lower bounds for testing triangle-freeness in Boolean functions
• An optimal tester for \(k\)-Linear
• A query efficient non-adaptive long code test with perfect completeness
• Testing computability by width-two OBDDs
• Almost Optimal Testers for Concise Representations.
• Testing formula satisfaction
• Reducing Testing Affine Spaces to Testing Linearity of Functions

This page was built for publication: Testing Basic Boolean Formulae

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