A large lower bound on the query complexity of a simple Boolean function

DOI10.1016/j.ipl.2005.05.004zbMath1177.68251OpenAlexW2042957148MaRDI QIDQ1041802

Beate Bollig

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.05.004

zbMATH Keywords

computational complexityrandomized algorithmsbranching programsproperty testingquery complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Cites Work

• Functions that have read-once branching programs of quadratic size are not necessarily testable
• Regular Languages are Testable with a Constant Number of Queries
• Testing Membership in Languages that Have Small Width Branching Programs
• Property testing and its connection to learning and approximation
• Monotonicity testing over general poset domains
• Some 3CNF properties are hard to test
• Functions that have read‐twice constant width branching programs are not necessarily testable
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing of matrix properties
• Abstract Combinatorial Programs and Efficient Property Testers
• Efficient testing of large graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item