A Lower Bound for Read-Once-Only Branching Programs

Abstract We give a C n lower bound for read-once-only branching programs computing an explicit Boolean function. For n = ( 2 ν , the function computes the parity of the number of triangles in a graph on ν vertices. This improves previous exp ( c √ n )) lower bounds for other graph functions by Wegener and Zak. The result implies a linear lower bound for the space complexity of this Boolean function on “eraser machines,” i.e., machines that erase each input bit immediately after having read it.

• Publication year

  1987

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  1987-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0022-0000(87)90010-9
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the complexity of branching programs and decision trees for clique functions

  1988cited by this paper
• The monotone circuit complexity of boolean functions

  1987cited by this paper
• Limits on the power of concurrent-write parallel machines

  1986cited by this paper
• Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)

  1985cited by this paper
• Separating the polynomial-time hierarchy by oracles

  1985cited by this paper
• An Exponential Lower Bound for One-Time-Only Branching Programs

  1984cited by this paper
• A Lower Bound on Complexity of Branching Programs (Extended Abstract)

  1984cited by this paper
• Lower bounds by probabilistic arguments

  1983cited by this paper
• A time-space tradeoff for sorting on non-oblivious machines

  1979cited by this paper
• Combinatorial problems and exercises

  1979cited by this paper
• The Complexity of Equivalence and Containment for Free Single Variable Program Schemes

  1978cited by this paper
• A fast algorithm for the string editing problem and decision graph complexity

  1976cited by this paper
• The Complexity of Computing

  1976cited by this paper
• Representation of switching circuits by binary-decision programs

  1959cited by this paper

• Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs

  2017cites this paper
• BRANCHING PROGRAM UNIFORMIZATION, REWRITING LOWER BOUNDS, AND GEOMETRIC GROUP THEORY

  2017cites this paper
• Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs

  2015cites this paper
• List of my favorite publications

  2014cites this paper
• List of publications in reverse chronological order with clickable links

  2014cites this paper
• Free binary decision diagrams for the computation of EARn

  2006cites this paper
• On lower bounds for read-k-times branching programs

  2005cites this paper
• Optimal Free Binary Decision Diagrams for Computation of EARn

  2002cites this paper
• Time-Space Tradeoffs for Branching Programs 1

  2001cites this paper
• A read-once lower bound and a (1, +k)-hierarchy for branching programs

  2000cites this paper
• The Computational Complexity of Equivalence and Isomorphism Problems

  2000cites this paper
• On the Power of Automata Based Proof Systems

  1999cites this paper
• Time-space tradeoffs for branching programs

  1998cites this paper
• Neither Reading Few Bits Twice Nor Reading Illegally Helps Much

  1998cites this paper
• On the Hierarchy of Nondeterministic Branching k-Programs

  1997cites this paper
• On Comparison Between the Sizes of Read-k-Times Branching Programs

  1997cites this paper
• A Hierarchy for (1, +k)-Branching Programs with Respect of k

  1997cites this paper
• A large lower bound for 1-branching programs

  1996cites this paper
• A hierarchy for (1,+k)-branching programs with respect to k

  1996cites this paper
• A lower bound for integer multiplication with read-once branching programs

  1995cites this paper
• A Simple Function that Requires Exponential Size Read-Once Branching Programs

  1995cites this paper
• On the Size of Binary Decision Diagrams Representing Boolean Functions

  1995cites this paper
• Time Space Tradeoffs (Getting Closer to the Barrier?)

  1993cites this paper
• Branching Programs as a Tool for Proving Lower Bounds on VLSI Computations and Optimal Algorithms for Systolic Arrays

  1988cites this paper
• Çôøøññð Ööö Òòöý ××óò Ööñ× Óö Óñôùøøøøóò Óó Ê Ò

  year unknowncites this paper