Functions that have read-once branching programs of quadratic size are not necessarily testable

DOI10.1016/S0020-0190(03)00230-8zbMath1175.68092OpenAlexW1997711080MaRDI QIDQ1014387

Beate Bollig, Ingo Wegener

Publication date: 28 April 2009

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00230-8

zbMATH Keywords

computational complexitybinary decision diagramsbranching programsproperty testing

Mathematics Subject Classification ID

General topics in the theory of software (68N01)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds to the complexity of symmetric Boolean functions
• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• 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
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing metric properties
• Testing of matrix properties
• Efficient testing of large graphs