On the public citation graph

An exponential lower bound for one-time-only branching programs

https://doi.org/10.1007/bfb0030340
0 signed · 66 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1109/sfcs.1979.34openalex-snapshot
Random walks, universal traversal sequences, and the complexity of maze problems
inferredcites →https://doi.org/10.1145/800061.808736openalex-snapshot
Bounds for width two branching programs
inferredcites →https://doi.org/10.1145/800061.808737openalex-snapshot
Multi-party protocols

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/inco.2000.3022openalex-snapshot
On the Descriptive and Algorithmic Power of Parity Ordered Binary Decision Diagrams
inferred← citeshttps://doi.org/10.1006/jcss.2001.1818openalex-snapshot
Lower Bounds for Linearly Transformed OBDDs and FBDDs
inferred← citeshttps://doi.org/10.1007/10719839_20openalex-snapshot
Almost k-Wise Independence and Hard Boolean Functions
inferred← citeshttps://doi.org/10.1007/3-540-18740-5_55openalex-snapshot
Exponential lower bounds for real-time branching programs
inferred← citeshttps://doi.org/10.1007/3-540-44612-5_60openalex-snapshot
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
inferred← citeshttps://doi.org/10.1007/3-540-45322-9_4openalex-snapshot
Randomized Branching Programs
inferred← citeshttps://doi.org/10.1007/3-540-45687-2_34openalex-snapshot
Optimal Free Binary Decision Diagrams for Computation of EARn
inferred← citeshttps://doi.org/10.1007/3-540-45841-7_35openalex-snapshot
A Lower Bound Technique for Restricted Branching Programs and Applications
inferred← citeshttps://doi.org/10.1007/3-540-46691-6_29openalex-snapshot
Lower Bounds for Linear Transformed OBDDs and FBDDs
inferred← citeshttps://doi.org/10.1007/3-540-48340-3_23openalex-snapshot
The Complexity of Minimizing FBDDs
inferred← citeshttps://doi.org/10.1007/3-540-51498-8_28openalex-snapshot
On oblivious branching programs of linear length
inferred← citeshttps://doi.org/10.1007/3-540-54458-5_49openalex-snapshot
Lower bounds for deterministic and nondeterministic branching programs
inferred← citeshttps://doi.org/10.1007/3-540-56402-0_56openalex-snapshot
Analysis and manipulation of Boolean functions in terms of decision graphs
inferred← citeshttps://doi.org/10.1007/3-540-57568-5_251openalex-snapshot
Time space tradeoffs (getting closer to the barrier?)
inferred← citeshttps://doi.org/10.1007/3-540-57568-5_269openalex-snapshot
Separating complexity classes related to bounded alternating Ω-branching programs
inferred← citeshttps://doi.org/10.1007/3-540-60246-1_138openalex-snapshot
A superpolynomial lower bound for (1,+k(n))-branching programs
inferred← citeshttps://doi.org/10.1007/978-1-4757-6048-4_49openalex-snapshot
Communication Complexity and BDD Lower Bound Techniques
inferred← citeshttps://doi.org/10.1007/978-3-031-49190-0_3openalex-snapshot
Streaming and Query Once Space Complexity of Longest Increasing Subsequence
inferred← citeshttps://doi.org/10.1007/978-3-642-22661-8openalex-snapshot
Average Time Complexity of Decision Trees
inferred← citeshttps://doi.org/10.1007/978-3-642-60322-8_15openalex-snapshot
Equivalence Problems and Lower Bounds for Branching Programs
inferred← citeshttps://doi.org/10.1007/978-94-011-5678-3_16openalex-snapshot
On Comparison Between the Sizes of Read-k-Times Branching Programs
inferred← citeshttps://doi.org/10.1007/bf01200404openalex-snapshot
On lower bounds for read-k-times branching programs
inferred← citeshttps://doi.org/10.1007/bfb0016269openalex-snapshot
Lower bounds on the complexity of local circuits
inferred← citeshttps://doi.org/10.1007/bfb0017159openalex-snapshot
Branching programs as a tool for proving lower bounds on vlsi computations and optimal algorithms for systolic arrays
inferred← citeshttps://doi.org/10.1007/bfb0023460openalex-snapshot
On the descriptive and algorithmic power of parity ordered binary decision diagrams
inferred← citeshttps://doi.org/10.1007/bfb0029596openalex-snapshot
Restricted branching programs and their computational power
inferred← citeshttps://doi.org/10.1007/bfb0029991openalex-snapshot
A hierarchy for (1, +k)-branching programs with respect to k
inferred← citeshttps://doi.org/10.1007/bfb0030285openalex-snapshot
Mathematical Foundations of Computer Science 1984
inferred← citeshttps://doi.org/10.1007/bfb0036199openalex-snapshot
On the hierarchy of nondeterministic branching k-programs
inferred← citeshttps://doi.org/10.1007/pl00001608openalex-snapshot
A separation of syntactic and nonsyntactic (1,+k)-branching programs
inferred← citeshttps://doi.org/10.1007/s00224-007-9067-9openalex-snapshot
Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice
inferred← citeshttps://doi.org/10.1016/0012-365x(95)90790-ropenalex-snapshot
Efficient data structures for Boolean functions
inferred← citeshttps://doi.org/10.1016/0022-0000(87)90010-9openalex-snapshot
A lower bound for read-once-only branching programs
inferred← citeshttps://doi.org/10.1016/0196-6774(86)90020-9openalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0304-3975(88)90166-1openalex-snapshot
Entropy of contact circuits and lower bounds on their complexity
inferred← citeshttps://doi.org/10.1016/0304-3975(94)00181-hopenalex-snapshot
On the size of binary decision diagrams representing Boolean functions
inferred← citeshttps://doi.org/10.1016/0890-5401(91)90039-5openalex-snapshot
On oblivious branching programs of linear length
inferred← citeshttps://doi.org/10.1016/j.ic.2024.105230openalex-snapshot
Perspective on complexity measures targeting read-once branching programs
inferred← citeshttps://doi.org/10.1016/s0019-9958(86)80018-3openalex-snapshot
An exponential lower bound for real-time branching programs
inferred← citeshttps://doi.org/10.1016/s0020-0190(97)00041-0openalex-snapshot
A simple function that requires exponential size read-once branching programs
inferred← citeshttps://doi.org/10.1016/s0020-0190(98)00042-8openalex-snapshot
A very simple function that requires exponential size read-once branching programs
inferred← citeshttps://doi.org/10.1016/s0166-218x(01)00324-9openalex-snapshot
The complexity of minimizing and learning OBDDs and FBDDs
inferred← citeshttps://doi.org/10.1016/s0166-218x(03)00297-xopenalex-snapshot
BDDs—design, analysis, complexity, and applications
inferred← citeshttps://doi.org/10.1016/s0166-218x(98)00042-0openalex-snapshot
Neither reading few bits twice nor reading illegally helps much
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00568-6openalex-snapshot
Approximation of boolean functions by combinatorial rectangles
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00643-6openalex-snapshot
Almost k-wise independence and hard Boolean functions
inferred← citeshttps://doi.org/10.1016/s0304-3975(96)00183-1openalex-snapshot
A lower bound on branching programs reading some bits twice
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00034-0openalex-snapshot
Hierarchy theorems for kOBDDs and kIBDDs
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00219-9openalex-snapshot
A read-once lower bound and a (1,+k)-hierarchy for branching programs
inferred← citeshttps://doi.org/10.1051/ita/1988220404471openalex-snapshot
Lower bounds on the complexity of real-time branching programs
inferred← citeshttps://doi.org/10.1051/ita/1995290100751openalex-snapshot
A note on read-$k$ times branching programs
inferred← citeshttps://doi.org/10.1051/ita:1999113openalex-snapshot
Communication Complexity and Lower Bounds on Multilective Computations
inferred← citeshttps://doi.org/10.1109/ccc.2002.1004343openalex-snapshot
On the complexity of integer multiplication in branching programs with multiple tests and in read-once branching programs with limited nondeterminism
inferred← citeshttps://doi.org/10.1137/s0097539795290349openalex-snapshot
A Lower Bound for Integer Multiplication with Read-Once Branching Programs
inferred← citeshttps://doi.org/10.1145/12130.12134openalex-snapshot
Two lower bounds for branching programs
inferred← citeshttps://doi.org/10.1145/225058.225098openalex-snapshot
A lower bound for integer multiplication with read-once branching programs
inferred← citeshttps://doi.org/10.1145/2751320openalex-snapshot
Pebbling, Entropy, and Branching Program Size Lower Bounds
inferred← citeshttps://doi.org/10.1145/3170709openalex-snapshot
Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs
inferred← citeshttps://doi.org/10.1145/3282433openalex-snapshot
Read-Once Branching Programs for Tree Evaluation Problems
inferred← citeshttps://doi.org/10.1145/380752.380835openalex-snapshot
A read-once branching program lower bound of Ω(2n/4) for integer multiplication using universal hashing
inferred← citeshttps://doi.org/10.3233/fi-1999-39401openalex-snapshot
On Average Time Complexity of Decision Trees and Branching Programs
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.30openalex-snapshot
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs
inferred← citeshttps://doi.org/10.53846/goediss-2588openalex-snapshot
Obere und untere Schranken für eingeschränkte Parity-Branchingprogramme
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.