Catalytic branching programs from groups and general protocols

DOI10.1145/3583085MaRDI QIDQ7022855zbMATH OpenFDO

Authors Hugo Côté, Pierre McKenzie

Publication date 24 February 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3583085

zbMATH Keywords

Boolean functionsbranching programscatalytic spacespace complexity

Mathematics Subject Classification ID

Boolean functions (06E30) Data structures (68P05) Communication complexity, information complexity (68Q11)

Cites work

• A note on amortized branching program complexity
• Amortized circuit complexity, formal complexity measures, and catalytic algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Branching Programs and Binary Decision Diagrams
• Computing with a full memory: catalytic space
• Dag-like communication and its applications
• Efficient oblivious branching programs for threshold and mod functions
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Lower bounds to the complexity of symmetric Boolean functions
• Monotone circuit lower bounds from resolution
• On extracting computations from propositional proofs (a survey)
• On the size of binary decision diagrams representing Boolean functions
• Pebbles and branching programs for tree evaluation
• Reversible space equals deterministic space
• Towards optimal simulations of formulas by bounded-width programs
• Trading time and space in catalytic branching programs
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic

This page was built for publication: Catalytic branching programs from groups and general protocols

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