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

DOI10.1016/J.IPL.2005.05.004MaRDI QIDQ1041802zbMATH OpenOpenAlexFDO

Authors 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 algorithmsquery complexityproperty testingbranching programs

Mathematics Subject Classification ID

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

Recommendations

• Fundamentals of Computation Theory
• Property testing lower bounds via communication complexity
• Parameterized property testing of functions
• Parameterized property testing of functions
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries

Cites work

• scientific article; zbMATH DE number 1670655 (Why is no real title available?)
• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• scientific article; zbMATH DE number 1875421 (Why is no real title available?)
• Abstract Combinatorial Programs and Efficient Property Testers
• Efficient testing of large graphs
• Functions that have read-once branching programs of quadratic size are not necessarily testable
• Functions that have read‐twice constant width branching programs are not necessarily testable
• Monotonicity testing over general poset domains
• Property testing and its connection to learning and approximation
• Regular languages are testable with a constant number of queries
• Robust Characterizations of Polynomials with Applications to Program Testing
• Some 3CNF properties are hard to test
• Testing Membership in Languages that Have Small Width Branching Programs
• Testing graphs for colorability properties
• Testing of matrix properties

Cited in

(6)

• Fundamentals of Computation Theory
• Property testing lower bounds via communication complexity
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• Testability in group theory
• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
• Parameterized property testing of functions

This page was built for publication: A large lower bound on the query complexity of a simple Boolean function

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