On the public citation graph
On lower bounds for read-k-times branching programs
0 signed · 146 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/j.1538-7305.1959.tb01585.xopenalex-snapshot
Representation of Switching Circuits by Binary-Decision Programs
inferredcites →https://doi.org/10.1007/3-540-18170-9_185openalex-snapshot
The complexity of symmetric boolean functions
inferredcites →https://doi.org/10.1007/3-540-54458-5_49openalex-snapshot
Lower bounds for deterministic and nondeterministic branching programs
inferredcites →https://doi.org/10.1007/bfb0030340openalex-snapshot
An exponential lower bound for one-time-only branching programs
inferredcites →https://doi.org/10.1016/0022-0000(84)90029-1openalex-snapshot
Time-space tradeoffs for matrix multiplication and the discrete fourier transform on any general sequential random-access computer
inferredcites →https://doi.org/10.1016/0022-0000(87)90010-9openalex-snapshot
A lower bound for read-once-only branching programs
inferredcites →https://doi.org/10.1016/0022-0000(88)90002-5openalex-snapshot
Meanders and their applications in lower bounds arguments
inferredcites →https://doi.org/10.1016/0022-0000(91)90014-vopenalex-snapshot
Time-space tradeoffs for algebraic problems on general sequential machines
inferredcites →https://doi.org/10.1016/0304-3975(90)90080-2openalex-snapshot
Lower bounds to the complexity of symmetric Boolean functions
inferredcites →https://doi.org/10.1016/0304-3975(91)90021-sopenalex-snapshot
Separating the eraser Turing machine classes Le, NLe, co-NLe and Pe
inferredcites →https://doi.org/10.1016/0304-3975(93)90257-topenalex-snapshot
The computational complexity of universal hashing
inferredcites →https://doi.org/10.1016/s0022-0000(70)80006-xopenalex-snapshot
Relationships between nondeterministic and deterministic tape complexities
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1109/sct.1989.41831openalex-snapshot
Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
inferredcites →https://doi.org/10.1109/sct.1991.160274openalex-snapshot
Superlinear lower bounds for bounded-width branching programs
inferredcites →https://doi.org/10.1109/t-aiee.1938.5057767openalex-snapshot
A symbolic analysis of relay and switching circuits
inferredcites →https://doi.org/10.1137/0211022openalex-snapshot
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
inferredcites →https://doi.org/10.1137/0217058openalex-snapshot
Nondeterministic Space is Closed under Complementation
inferredcites →https://doi.org/10.1137/0220017openalex-snapshot
A general Sequential Time-Space Tradeoff for Finding Unique Elements
inferredcites →https://doi.org/10.1145/100216.100246openalex-snapshot
The computational complexity of universal hashing
inferredcites →https://doi.org/10.1145/73007.73008openalex-snapshot
Multiparty protocols and logspace-hard pseudorandom sequences
inferredcites →https://doi.org/10.82444/warw.33787051openalex-snapshot
Lower bounds on the complexity of 1-time only branching programs
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.2002.3174openalex-snapshot
On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs
inferred← citeshttps://doi.org/10.1006/jcss.1996.0050openalex-snapshot
New Lower Bounds and Hierarchy Results for Restricted Branching Programs
inferred← citeshttps://doi.org/10.1006/jcss.1997.1530openalex-snapshot
Efficient Oblivious Branching Programs for Threshold and Mod Functions
inferred← citeshttps://doi.org/10.1006/jcss.1999.1648openalex-snapshot
On Arithmetic Branching Programs
inferred← citeshttps://doi.org/10.1006/jcss.2001.1778openalex-snapshot
Time–Space Tradeoffs for Branching Programs
inferred← citeshttps://doi.org/10.1006/jcss.2001.1786openalex-snapshot
Spectral Methods for Matrix Rigidity with Applications to Size–Depth Trade-offs and Communication Complexity
inferred← citeshttps://doi.org/10.1007/11537311_4openalex-snapshot
On the Incompressibility of Monotone DNFs
inferred← citeshttps://doi.org/10.1007/11571155_11openalex-snapshot
On Some Bounds on the Size of Branching Programs (A Survey)
inferred← citeshttps://doi.org/10.1007/11571155_16openalex-snapshot
The Complexity of Classical and Quantum Branching Programs: A Communication Complexity Approach
inferred← citeshttps://doi.org/10.1007/3-540-36494-3_28openalex-snapshot
Randomness versus Nondeterminism for Read-Once and Read-k Branching Programs
inferred← citeshttps://doi.org/10.1007/3-540-44612-5_18openalex-snapshot
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
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-44679-6_4openalex-snapshot
Separating Oblivious and Non-oblivious BPs
inferred← citeshttps://doi.org/10.1007/3-540-44693-1_18openalex-snapshot
On Multipartition Communication Complexity
inferred← citeshttps://doi.org/10.1007/3-540-44693-1_37openalex-snapshot
On the Minimal Hardware Complexity of Pseudorandom Function Generators
inferred← citeshttps://doi.org/10.1007/3-540-45322-9_4openalex-snapshot
Randomized Branching Programs
inferred← citeshttps://doi.org/10.1007/3-540-48523-6_15openalex-snapshot
Small Pseudo-Random Sets Yield Hard Functions: New Tight Explicit Lower Bounds for Branching Programs
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/3-540-60922-9_50openalex-snapshot
The “log rank” conjecture for modular communication complexity
inferred← citeshttps://doi.org/10.1007/3-540-61440-0_141openalex-snapshot
On the power of randomized branching programs
inferred← citeshttps://doi.org/10.1007/3-540-63165-8_177openalex-snapshot
Randomization and nondeterminism are comparable for ordered read-once branching programs
inferred← citeshttps://doi.org/10.1007/978-0-387-35608-2_8openalex-snapshot
Parity Graph-Driven Read-Once Branching Programs and An Exponential Lower Bound for Integer Multiplication
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-20624-5_38openalex-snapshot
MCSP is Hard for Read-Once Nondeterministic Branching Programs
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-319-13524-3_27openalex-snapshot
No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth
inferred← citeshttps://doi.org/10.1007/978-3-319-98355-4_9openalex-snapshot
Classical and Quantum Computations with Restricted Memory
inferred← citeshttps://doi.org/10.1007/978-3-322-84823-9_19openalex-snapshot
Komplexitätstheoretische Ergebnisse für Randomisierte Branchingprogramme
inferred← citeshttps://doi.org/10.1007/978-3-540-31856-9_21openalex-snapshot
Dynamic Complexity Theory Revisited
inferred← citeshttps://doi.org/10.1007/978-3-540-85238-4_37openalex-snapshot
Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
inferred← citeshttps://doi.org/10.1007/978-3-642-03816-7_16openalex-snapshot
Branching Programs for Tree Evaluation
inferred← citeshttps://doi.org/10.1007/978-3-642-24508-4openalex-snapshot
Boolean Function Complexity: Advances and Frontiers
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_9openalex-snapshot
Finding the Median (Obliviously) with Bounded Space
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/bf01268140openalex-snapshot
Top-down lower bounds for depth-three circuits
inferred← citeshttps://doi.org/10.1007/bf01294594openalex-snapshot
Separating complexity classes related to bounded alternating ?-branching programs
inferred← citeshttps://doi.org/10.1007/bfb0028553openalex-snapshot
Lower bounds for randomized read-k-times branching programs
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/bfb0036199openalex-snapshot
On the hierarchy of nondeterministic branching k-programs
inferred← citeshttps://doi.org/10.1007/bfb0055830openalex-snapshot
Communication complexity and lower bounds on multilective computations
inferred← citeshttps://doi.org/10.1007/pl00001612openalex-snapshot
The “log rank” conjecture for modular communication complexity
inferred← citeshttps://doi.org/10.1007/s00037-007-0231-zopenalex-snapshot
New Results on the Complexity of the Middle Bit of Multiplication
inferred← citeshttps://doi.org/10.1007/s00037-013-0072-xopenalex-snapshot
Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits
inferred← citeshttps://doi.org/10.1007/s000370100002openalex-snapshot
Pseudorandom functions in $ \textit{TC}^{0} $ and cryptographic limitations to proving lower bounds
inferred← citeshttps://doi.org/10.1007/s00224-001-1011-9openalex-snapshot
The Satisfiability Problem for Probabilistic Ordered Branching Programs
inferred← citeshttps://doi.org/10.1007/s00224-002-1050-xopenalex-snapshot
The Power of Nondeterminism and Randomness for Oblivious Branching Programs
inferred← citeshttps://doi.org/10.1007/s00224-006-1312-0openalex-snapshot
Dynamic Complexity Theory Revisited
inferred← citeshttps://doi.org/10.1007/s00224-007-2013-zopenalex-snapshot
On the Incompressibility of Monotone DNFs
inferred← citeshttps://doi.org/10.1007/s00224-007-9049-yopenalex-snapshot
Incremental 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.1007/s00224-016-9714-0openalex-snapshot
On Oblivious Branching Programs with Bounded Repetition that Cannot Efficiently Compute CNFs of Bounded Treewidth
inferred← citeshttps://doi.org/10.1007/s00224-020-09996-3openalex-snapshot
Satisfiability Algorithm for Syntactic Read-k-times Branching Programs
inferred← citeshttps://doi.org/10.1007/s00224-022-10113-9openalex-snapshot
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP
inferred← citeshttps://doi.org/10.1007/s002240010005openalex-snapshot
An Improved Hierarchy Result for Partitioned BDDs
inferred← citeshttps://doi.org/10.1007/s00453-013-9747-6openalex-snapshot
Limitations of Incremental Dynamic Programming
inferred← citeshttps://doi.org/10.1016/0020-0190(94)00094-8openalex-snapshot
Time–space tradeoffs for integer multiplication on various types of input oblivious sequential machines
inferred← citeshttps://doi.org/10.1016/j.dam.2024.09.028openalex-snapshot
The splitting power of branching programs of bounded repetition and CNFs of bounded width
inferred← citeshttps://doi.org/10.1016/j.ic.2004.05.002openalex-snapshot
On multi-partition communication complexity
inferred← citeshttps://doi.org/10.1016/j.ic.2005.04.003openalex-snapshot
On the computational power of probabilistic and quantum branching program
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/j.ipl.2008.11.001openalex-snapshot
A nondeterministic space-time tradeoff for linear codes
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.01.052openalex-snapshot
Lower bounds for restricted read-once parity branching programs
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.05.035openalex-snapshot
Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
inferred← citeshttps://doi.org/10.1016/j.tcs.2008.09.012openalex-snapshot
Expanders and time-restricted branching programs
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.07.003openalex-snapshot
Yet harder knapsack problems
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(02)00305-0openalex-snapshot
Comparing the sizes of nondeterministic branching read-k-times programs
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(00)00216-4openalex-snapshot
On BPP versus NP∪coNP for ordered read-once branching programs
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(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.1016/s0890-5401(02)93174-3openalex-snapshot
On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs
inferred← citeshttps://doi.org/10.1016/s0890-5401(03)00118-4openalex-snapshot
A lower bound for integer multiplication on randomized ordered read-once branching programs
inferred← citeshttps://doi.org/10.1017/s0963548302005333openalex-snapshot
Triangle-Freeness is Hard to Detect
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.1051/ita:2001113openalex-snapshot
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
inferred← citeshttps://doi.org/10.1051/ita:2003010openalex-snapshot
Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
inferred← citeshttps://doi.org/10.1109/ccc.1998.694592openalex-snapshot
On arithmetic branching programs
inferred← citeshttps://doi.org/10.1109/ccc.2001.933884openalex-snapshot
On the non-approximability of Boolean functions by OBDDs and read-k-times branching programs
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.1109/isit.2006.262116openalex-snapshot
Minimum Distance of Codes and Their Branching Program Complexity
inferred← citeshttps://doi.org/10.1109/sfcs.1994.365684openalex-snapshot
Efficient oblivious branching programs for threshold functions
inferred← citeshttps://doi.org/10.1109/sfcs.1995.492457openalex-snapshot
Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743453openalex-snapshot
Time-space tradeoffs for branching programs
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892078openalex-snapshot
Super-linear time-space tradeoff lower bounds for randomized computation
inferred← citeshttps://doi.org/10.1109/sffcs.1999.814578openalex-snapshot
A non-linear time lower bound for Boolean branching programs
inferred← citeshttps://doi.org/10.1134/s1990478910020122openalex-snapshot
A lower bound on the computation complexity of characteristic functions for BCH-codes by branching programs
inferred← citeshttps://doi.org/10.1134/s1995080215020092openalex-snapshot
Width hierarchy for k-OBDD of small width
inferred← citeshttps://doi.org/10.1134/s1995080216060159openalex-snapshot
On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
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/182591.182614openalex-snapshot
Dyn-FO (preliminary version): a parallel, dynamic complexity class
inferred← citeshttps://doi.org/10.1145/2077336.2077337openalex-snapshot
Pebbles and Branching Programs for Tree Evaluation
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/276698.276881openalex-snapshot
On separating the read-k-times branching program hierarchy
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/3417758openalex-snapshot
Strongly Exponential Separation between Monotone VP and Monotone VNP
inferred← citeshttps://doi.org/10.1145/3728715openalex-snapshot
Cumulative Memory Lower Bounds for Randomized and Quantum Computation
inferred← citeshttps://doi.org/10.1145/509907.510006openalex-snapshot
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
inferred← citeshttps://doi.org/10.1145/636865.636867openalex-snapshot
Time-space trade-off lower bounds for randomized computation of decision problems
inferred← citeshttps://doi.org/10.1145/780542.780571openalex-snapshot
Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
inferred← citeshttps://doi.org/10.17877/de290r-7870openalex-snapshot
Über die Komplexität der Multiplikation in eingeschränkten Branchingprogrammmodellen
inferred← citeshttps://doi.org/10.4230/dagsemproc.06111.15openalex-snapshot
Quantum vs. Classical Read-Once 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.4230/lipics.icalp.2016.36openalex-snapshot
Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
inferred← citeshttps://doi.org/10.48550/arxiv.1005.2642openalex-snapshot
Pebbles and Branching Programs for Tree Evaluation
inferred← citeshttps://doi.org/10.48550/arxiv.1510.05486openalex-snapshot
Two types of branching programs with bounded repetition that cannot efficiently compute monotone 3-CNFs
inferred← citeshttps://doi.org/10.48550/arxiv.1604.01560openalex-snapshot
Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs
inferred← citeshttps://doi.org/10.48550/arxiv.1811.01347openalex-snapshot
Some Results on the Circuit Complexity of Bounded Width Circuits and Nondeterministic Circuits
inferred← citeshttps://doi.org/10.48550/arxiv.1903.01630openalex-snapshot
Strongly Exponential Separation Between Monotone VP and Monotone VNP
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0608085openalex-snapshot
A Quadratic Time-Space Tradeoff for Unrestricted Deterministic Decision Branching Programs
inferred← citeshttps://doi.org/10.53846/goediss-2524openalex-snapshot
On Lower Bounds for Parity Branching Programs
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.