New lower bounds and hierarchy results for restricted branching programs

DOI10.1007/3-540-59071-4_61zbMath1528.68096MaRDI QIDQ6184383

Ingo Wegener, Detlef Sieling

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph driven BDDs -- a new data structure for Boolean functions
• Lower bounds on communication complexity
• Meanders and their applications in lower bounds arguments
• Lower bounds for depth-restricted branching programs
• Efficient data structures for Boolean functions
• On lower bounds for read-\(k\)-times branching programs
• Different Modes of Communication
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Graph-Based Algorithms for Boolean Function Manipulation
• On the complexity of branching programs and decision trees for clique functions
• Rounds in Communication Complexity Revisited

This page was built for publication: New lower bounds and hierarchy results for restricted branching programs