Perspective on complexity measures targeting read-once branching programs

DOI10.1016/J.IC.2024.105230MaRDI QIDQ6647765zbMATH OpenFDO

Authors Yaqiao Li, Pierre McKenzie

Publication date 3 December 2024

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2024.105230

zbMATH Keywords

blocking setscommunication complexitycover numberGEN functionpartition numberread-once branching programrectanglesubfunctionstree evaluation problemTseitin formula

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A simple function that requires exponential size read-once branching programs
• A very simple function that requires exponential size read-once branching programs.
• Approximation of boolean functions by combinatorial rectangles
• Boolean function complexity. Advances and frontiers.
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Communication Complexity
• Complete problems for deterministic polynomial time
• Entropy of contact circuits and lower bounds on their complexity
• scientific article; zbMATH DE number 3890736 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 549860 (Why is no real title available?)
• scientific article; zbMATH DE number 1101474 (Why is no real title available?)
• scientific article; zbMATH DE number 1789913 (Why is no real title available?)
• scientific article; zbMATH DE number 3387244 (Why is no real title available?)
• Learning decision trees from random examples
• Lower bounds for nondeterministic semantic read-once branching programs
• Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
• On another Boolean matrix
• On lower bounds for read-\(k\)-times branching programs
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• On the complexity of branching programs and decision trees for clique functions
• On the spectrum of minimal blocking sets in \(\text{PG}(2,q)\)
• Pebbles and branching programs for tree evaluation
• Read-Once Branching Programs for Tree Evaluation Problems
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
• The blocking number of an affine space

This page was built for publication: Perspective on complexity measures targeting read-once branching programs

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