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

DOI10.1016/j.ipl.2005.05.004zbMath1177.68251MaRDI 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 complexity; randomized algorithms; branching programs; property testing; query complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

68W20: Randomized algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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