A note on amortized branching program complexity

DOI10.4230/LIPICS.CCC.2017.4MaRDI QIDQ5111134zbMATH OpenFDO

Authors Aaron Potechin

Publication date 26 May 2020

Full work available at URL https://arxiv.org/abs/1611.06632

zbMATH Keywords

amortizationbranching programsspace complexity

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Networks and circuits as models of computation; circuit complexity (68Q06) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3913677
• Branching program size is almost linear in formula size
• Comparing the sizes of nondeterministic branching read-k-times programs
• scientific article; zbMATH DE number 2102760
• Stochastic Algorithms: Foundations and Applications

Cited in

(7)

• Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations
• Computing with a full memory: catalytic space
• Catalytic branching programs from groups and general protocols
• Unambiguous, randomized, and symmetric catalytic computation
• Asymptotic spectra: theory, applications, and extensions
• Fully characterizing lossy catalytic computation
• Quantum catalytic space

This page was built for publication: A note on amortized branching program complexity

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