A hierarchy result for read-once branching programs with restricted parity nondeterminism

DOI10.1016/j.tcs.2005.03.016zbMath1077.68031OpenAlexW1587658859MaRDI QIDQ2566039

Detlef Sieling, Petr Savický

Publication date: 22 September 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.03.016

zbMATH Keywords

HierarchyRead-once branching programsLower bounds on complexityRestricted parity nondeterminism

Mathematics Subject Classification ID

Related Items (1)

Lower bounds for restricted read-once parity branching programs

Cites Work

• Unnamed Item
• Polynomial size \(\Omega\)-branching programs and their computational power
• Entropy of contact circuits and lower bounds on their complexity
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• An improved hierarchy result for partitioned BDDs
• Time-space tradeoffs for branching programs
• On lower bounds for read-\(k\)-times branching programs
• Time-space trade-off lower bounds for randomized computation of decision problems
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
• Graph-Based Algorithms for Boolean Function Manipulation
• Branching Programs and Binary Decision Diagrams

This page was built for publication: A hierarchy result for read-once branching programs with restricted parity nondeterminism