Functions that have read-once branching programs of quadratic size are not necessarily testable
From MaRDI portal
Publication:1014387
DOI10.1016/S0020-0190(03)00230-8zbMath1175.68092MaRDI QIDQ1014387
Publication date: 28 April 2009
Published in: Information Processing Letters (Search for Journal in Brave)
68N01: General topics in the theory of software
Related Items
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