Branching programs

@Google Scholar Search for Papers
Papers (very incomplete)
Surveys
- [Lower bounds for deterministic and nondeterministic branching programs:Alexander Razborov, FCT 1991:29.04.08] (29.04.08)
ECCC Technical Reports
- On the Power of Different Types of Restricted Branching Programs (Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener, ECCC TR94-026)
- A Note on Read-k Times Branching Programs (Stasys Jukna, ECCC TR04-027)
- New Lower Bounds and Hierarchy Results for Restricted Branching Programs (Detlef Sieling, ECCC TR95-002)
- On the Power of Randomized Branching Programs (Farid M. Ablayev, Marek Karpinski, TR95-054)
- On Learning Branching Programs and Small Depth Circuits (Francesco Bergadano, Nader H. Bshouty, Christino Tamon, Stefano Varricchio, ECCC TR96-009)
- A large lower bound for 1-branching programs (Petr Savický and Stanislav Zák, ECCC TR96-036)
- The Isomorphism problem for One-Time-Only Branching Programs (Thomas Thierauf, ECCC TR96-040)
- A hierarchy for (1,+k)-branching programs with respect to k (Petr Savický and Stanislav Zák, ECCC TR06-050)
- A Lower Bound for Randomized Read-k-Times Branching Programs (Martin Sauerhoff, TR97-019)
- Randomization and nondeterminsm are incomparable for ordered read-once branching programs (Farid M. Ablayev, TR97-021)
- On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs (Stasys Jukna, Alexander A. Razborov, Petr Savický and Ingo Wegener, TR97-023)
- On Nondeterminism versus Randomness for Read-Once Branching Programs (Martin Sauerhoff, TR97-030)
- A subexponential lower bound for branching programs restricted with regard to some semantic aspects (Stanislav Zak, TR97-050)
- Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs (A. E. Andreev, J. L. Baskakov, A. E. F. Clementi, J. D. P. Rolim, ECCC TR97-053)
- The Satisfiability Problem for Probabilistic Ordered Branching Programs, Manindra Agrawal and Thomas Thierauf, ECCC TR97-060 (29.04.08)
- On Separating the Read-k-Times Branching Program Hierarchy (Jayram S. Thathachar, ECCC TR98-002)
- On the Power of Randomized Ordered Branching Programs (Farid Ablayev, Marek Karpinski, TR98-004)
- A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs (Farid Ablayev and Marek Karpinski, ECCC TR98-011)
- Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs (Martin Sauerhoff, ECCC TR98-018)
- On Branching Programs With Bounded Uncertainty (Stasys Jukna and Stanislav Zak, ECCC TR98-030)
- On the Computational Power of Randomized Branching Programs (Marek Karpinski, ECCC TR98-038)
- A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs (Detlef Sieling, ECCC TR98-045)
- A probabilistic nonequivalence test for syntactic (1,+k)-branching programs (Petr Zavitsky, ECCC TR98-051)
- Time-Space Tradeoffs for Branching Programs (Paul Beame, Michael Saks, Jayram S. Thathachar, TR98-053)
- Almost $k$-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs (Valentine Kabanets, TR99-004)
- A Non-linear Time Lower Bound for Boolean Branching Programs (Miklós Ajtai, ECCC TR99-026)
- On Complexity of Regular $(1,+k)$-Branching Programs (Farid M. Ablayev, TR99-044)
- Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication (Beate Bollig, ECCC TR00-048)
- A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism (Petr Zavitský, Detlef Sieling, ECCC TR01-017)
- Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable (Rustam Mubarakzjanov, ECCC TR01-037)
- On Uncertainty versus Size in Branching Programs (Stasys Jukna, Stanislav Zak, ECCC TR01-039)
- Branching program, commutator, and icosahedron, part I (Jui-Lin Lee, ECCC TR01-048)
- Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication (Beate Bollig, Philipp Woelfel, Stephan Waack, ECCC TR01-073)
- A Lower Bound Technique for Restricted Branching Programs and Applications (Philipp Woelfel, ECCC TR01-101)
- On one lower bound for branching programs (Elizaveta Okol'nishnikova, ECCC TR02-020)
- A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs (Beate Bollig, ECCC TR02-033)
- Lower Bounds for the Sum of Graph--driven Read--Once Parity Branching Programs (Matthias Homeister, ECCC TR03-068)
- Expanders and time-restricted branching programs (Stasys Jukna, ECCC TR05-079)
- Incremental branching programs (Anna Gal, Michal Koucky, Pierre McKenzie, ECCC TR05-136)
- The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function (Beate Bollig, ECCC TR07-110)
Use in crypto
- Private Branching Programs: On Communication-Efficient Cryptocomputing (Helger Lipmaa, eprint 2008/107)
Cryptology Pointers by Helger Lipmaa
Got any suggestions or additional links? Mail to <lipmaa>research.cyber.ee
NB! If you find any broken links, please be kind and report them to me together with their current location!

(C) Helger Lipmaa 1997-2009.