Fundamentals of Computation Theory

DOI10.1007/11537311MaRDI QIDQ5492933zbMATH OpenOpenAlexFDO

Authors Beate Bollig

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11537311

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A large lower bound on the query complexity of a simple Boolean function
• Testing Membership in Languages that Have Small Width Branching Programs
• Functions that have read‐twice constant width branching programs are not necessarily testable
• Functions that have read-once branching programs of quadratic size are not necessarily testable
• Testing Computability by Width Two OBDDs

Cited in

(9)

• Proofs of proximity for context-free languages and read-once branching programs
• Functions that have read‐twice constant width branching programs are not necessarily testable
• Proofs of proximity for context-free languages and read-once branching programs
• Functions that have read-once branching programs of quadratic size are not necessarily testable
• A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
• Testing Membership in Languages that Have Small Width Branching Programs
• A large lower bound on the query complexity of a simple Boolean function
• Length of polynomials over finite groups
• Abstract Combinatorial Programs and Efficient Property Testers

This page was built for publication: Fundamentals of Computation Theory

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