A New Lower Bound Theorem for Read-Only-Once Branching Programs and its Applications

No abstract is available for this paper.

• Publication year

  1992

• Venue

  Advances In Computational Complexity Theory

• Publication date

  1992-02-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1090/dimacs/013/11
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• No references are available for this paper.

• Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs

  2023cites this paper
• Streaming and Query Once Space Complexity of Longest Increasing Subsequence

  2023influential citation
• Perspective on complexity measures targetting read-once branching programs

  2023influential citation
• Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More

  2023cites this paper
• Read-Once Branching Programs for Tree Evaluation Problems

  2018cites this paper
• Computational Complexity of Tree Evaluation Problems and Branching Program Satisfiability Problems

  2015cites this paper
• The simplified weighted sum function and its average sensitivity

  2014cites this paper
• Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice

  2009cites this paper
• A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds

  2008cites this paper
• A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds

  2008cites this paper
• The Complexity of Classical and Quantum Branching Programs: A Communication Complexity Approach

  2005cites this paper
• BDDs--design, analysis, complexity, and applications

  2004cites this paper
• Über die Komplexität der Multiplikation in eingeschränkten Branchingprogrammmodellen

  2004cites this paper
• Approximation of Boolean Functions by Combinatorial Rectangles

  2003cites this paper
• Randomness versus Nondeterminism for Read-Once and Read- k Branching Programs

  2003cites this paper
• On lower bounds for parity branching programs

  2003cites this paper
• On the complexity of integer multiplication in branching programs with multiple tests and in read-once branching programs with limited nondeterminism

  2002cites this paper
• A Lower Bound Technique for Restricted Branching Programs and Applications

  2002influential citation
• The complexity of minimizing and learning OBDDs and FBDDs

  2002cites this paper
• Nonuniformly hard boolean functions and uniform complexity classes

  2001cites this paper
• A read-once branching program lower bound of Ω(2n/4) for integer multiplication using universal hashing

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

  2000cites this paper
• Approximation of Boolean Functions by Combinatorial Rectangles *

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

  2000cites this paper
• Almost k-wise independence and hard Boolean functions

  2000cites this paper
• Communication Complexity and BDD Lower Bound Techniques

  2000cites this paper
• Small Pseudo-Random Sets Yield Hard Functions: New Tight Explict Lower Bounds for Branching Programs

  1999cites this paper
• Mathematical Foundations of Computer Science 1999

  1999cites this paper
• Complexity theoretical results for randomized branching programs

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

  1999cites this paper
• The Complexity of Minimizing FBDDs

  1999cites this paper
• On separating the read-k-times branching program hierarchy

  1998cites this paper
• Lower Bounds for Randomized Read-k-Times Branching Programs (Extended Abstract)

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

  1998cites this paper
• Time-space Tradeoos for Branching Programs

  1998cites this paper
• On the Power of Randomized Ordered Branching Programs

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

  1998cites this paper
• On separating the read-k-times branching program hierarchy

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

  1997cites this paper
• Randomization and Nondeterminism Are Comparable for Ordered Read-Once Branching Programs

  1997cites this paper
• On Nondeterminism versus Randomness for Read-Once Branching Programs

  1997cites this paper
• On the Power of Randomized Branching Programs

  1996influential citation
• A large lower bound for 1-branching programs

  1996influential citation
• A hierarchy for (1,+k)-branching programs with respect to k

  1996cites this paper
• Restricted branching programs and hardware verification

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

  1995cites this paper
• Restricted Branching Programs and Hardware Veriication Restricted Branching Programs and Hardware Veriication Title: Assistant Professor of Mathematics

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

  1995cites this paper
• The Complexity of Minimizing and Learning FBDDs ∗

  year unknowncites this paper
• The Faculty of the Division of the Physical Sciences in Candidacy for the Degree of Doctor of Philosophy Department of Computer Science

  year unknowncites this paper