Perspective on complexity measures targeting read-once branching programs

DOI10.1016/J.IC.2024.105230MaRDI QIDQ6647765

Could not fetch data.

Publication date: 3 December 2024

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

zbMATH Keywords

blocking setscommunication complexitypartition numberrectanglecover numbersubfunctionsread-once branching programTseitin formulatree evaluation problemGEN function

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A simple function that requires exponential size read-once branching programs
• Boolean function complexity. Advances and frontiers.
• Entropy of contact circuits and lower bounds on their complexity
• On another Boolean matrix
• Complete problems for deterministic polynomial time
• The blocking number of an affine space
• Approximation of boolean functions by combinatorial rectangles
• On the spectrum of minimal blocking sets in \(\text{PG}(2,q)\)
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• Learning decision trees from random examples
• On lower bounds for read-\(k\)-times branching programs
• A very simple function that requires exponential size read-once branching programs.
• Pebbles and Branching Programs for Tree Evaluation
• On the complexity of branching programs and decision trees for clique functions
• Branching Programs and Binary Decision Diagrams
• Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
• Communication Complexity
• Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method
• Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.
• Read-Once Branching Programs for Tree Evaluation Problems
• Communication Complexity

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)