Testing Basic Boolean Formulae
From MaRDI portal
Publication:4785704
DOI10.1137/S0895480101407444zbMath1041.68050OpenAlexW2055194501MaRDI QIDQ4785704
Dana Ron, Michal Parnas, 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
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (27)
Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ A query efficient non-adaptive long code test with perfect completeness ⋮ Testing juntas ⋮ Reducing Testing Affine Spaces to Testing Linearity of Functions ⋮ On one-sided testing affine subspaces ⋮ An optimal tester for \(k\)-Linear ⋮ Local correction of juntas ⋮ Efficiently testing sparse \(\text{GF}(2)\) polynomials ⋮ Sample-Based High-Dimensional Convexity Testing. ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Efficient Sample Extractors for Juntas with Applications ⋮ Almost Optimal Testers for Concise Representations. ⋮ Property testing lower bounds via communication complexity ⋮ Testing Juntas: A Brief Survey ⋮ Testing by Implicit Learning: A Brief Survey ⋮ Invariance in Property Testing ⋮ Query-Efficient Dictatorship Testing with Perfect Completeness ⋮ Proximity Oblivious Testing and the Role of Invariances ⋮ Proximity Oblivious Testing and the Role of Invariances ⋮ A Canonical Form for Testing Boolean Function Properties ⋮ Almost optimal distribution-free junta testing ⋮ A unified framework for testing linear‐invariant properties ⋮ Testing computability by width-two OBDDs ⋮ Unnamed Item ⋮ An Improved Dictatorship Test with Perfect Completeness ⋮ Lower bounds for testing triangle-freeness in Boolean functions ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities
This page was built for publication: Testing Basic Boolean Formulae
