Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with branching programs:
TR94-026 | 12th December 1994
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

On the Power of Different Types of Restricted Branching Programs

Almost the same types of restricted branching programs (or
binary decision diagrams BDDs) are considered in complexity
theory and in applications like hardware verification. These
models are read-once branching programs (free BDDs) and certain
types of oblivious branching programs (ordered and indexed BDDs
with k layers). The complexity of ... more >>>

TR94-027 | 12th December 1994
Stasys Jukna

A Note on Read-k Times Branching Programs

A syntactic read-k times branching program has the restriction
that no variable occurs more than k times on any path (whether or not
consistent). We exhibit an explicit Boolean function f which cannot
be computed by nondeterministic syntactic read-k times branching programs
of size less than exp(\sqrt{n}}k^{-2k}), ... more >>>

TR95-002 | 1st January 1995
Detlef Sieling

New Lower Bounds and Hierarchy Results for Restricted Branching Programs

In unrestricted branching programs all variables may be tested
arbitrarily often on each path. But exponential lower bounds are only
known, if on each path the number of tests of each variable is bounded
(Borodin, Razborov and Smolensky (1993)). We examine branching programs
in which for each path the ... more >>>

TR95-010 | 16th February 1995
Pavel Pudlak, Jiri Sgall

An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

We prove an unexpected upper bound on a communication game proposed
by Jeff Edmonds and Russell Impagliazzo as an approach for
proving lower bounds for time-space tradeoffs for branching programs.
Our result is based on a generalization of a construction of Erdos,
Frankl and Rodl of a large 3-hypergraph ... more >>>

TR96-009 | 17th January 1996
Francesco Bergadano, Nader H. Bshouty, Christino Tamon, Stefano Varricchio

On Learning Branching Programs and Small Depth Circuits

This paper studies the learnability of branching programs and small depth
circuits with modular and threshold gates in both the exact and PAC learning
models with and without membership queries. Some of the results extend earlier
works in [GG95,ERR95,BTW95]. The main results are as follows. For
branching programs we ... more >>>

TR96-036 | 28th May 1996
Petr Savicky, Stanislav Zak

A large lower bound for 1-branching programs

Revisions: 1

Branching programs (b.p.'s) or decision diagrams are a general
graph-based model of sequential computation. B.p.'s of polynomial
size are a nonuniform counterpart of LOG. Lower bounds for
different kinds of restricted b.p.'s are intensively investigated.
An important restriction are so called 1-b.p.'s, where each
computation reads each input bit at ... more >>>

TR96-040 | 21st May 1996
Thomas Thierauf

The Isomorphismproblem for One-Time-Only Branching Programs

Revisions: 1 , Comments: 1

We investigate the computational complexity of the
isomorphism problem for one-time-only branching programs (BP1-Iso):
on input of two one-time-only branching programs B and B',
decide whether there exists a permutation of the variables of B'
such that it becomes equivalent to B.

Our main result is a two-round interactive ... more >>>

TR96-050 | 23rd September 1996
Petr Savicky, Stanislav Zak

A hierarchy for (1,+k)-branching programs with respect to k

Branching programs (b.p.'s) or decision diagrams are a general
graph-based model of sequential computation. The b.p.'s of
polynomial size are a nonuniform counterpart of LOG. Lower bounds
for different kinds of restricted b.p.'s are intensively
investigated. An important restriction are so called $k$-b.p.'s,
where each computation reads each input ... more >>>

TR97-021 | 16th May 1997
Farid Ablayev

Randomization and nondeterminsm are incomparable for ordered read-once branching programs

In the manuscript F. Ablayev and M. Karpinski, On the power of
randomized branching programs (generalization of ICALP'96 paper
results for the case of pure boolean function, available at
http://www.ksu.ru/~ablayev) we exhibited a simple boolean functions
$f_n$ in $n$ variables such that:

1) $f_{n}$ can be computed ... more >>>

TR97-030 | 25th August 1997
Martin Sauerhoff

On Nondeterminism versus Randomness for Read-Once Branching Programs

Randomized branching programs are a probabilistic model of computation
defined in analogy to the well-known probabilistic Turing machines.
In this paper, we present complexity theoretic results for randomized
read-once branching programs.
Our main result shows that nondeterminism can be more powerful than
randomness for read-once branching programs. We present a ... more >>>

TR97-050 | 27th October 1997
Stanislav Zak

A subexponential lower bound for branching programs restricted with regard to some semantic aspects

Branching programs (b.p.s) or binary decision diagrams are a
general graph-based model of sequential computation. The b.p.s of
polynomial size are a nonuniform counterpart of LOG. Lower bounds
for different kinds of restricted b.p.s are intensively
investigated. The restrictions based on the number of tests of
more >>>

TR97-053 | 10th November 1997
Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim

Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs

Revisions: 2

We show the following Reduction Lemma: any
$\epsilon$-biased sample space with respect to (Boolean) linear
tests is also $2\epsilon$-biased with respect to
any system of independent linear tests. Combining this result with
the previous constructions of $\epsilon$-biased sample space with
respect to linear tests, we obtain the first efficient
more >>>

TR98-030 | 9th June 1998
Stasys Jukna, Stanislav Zak

On Branching Programs With Bounded Uncertainty

We propose an information-theoretic approach to proving
lower bounds on the size of branching programs (b.p.). The argument
is based on Kraft-McMillan type inequalities for the average amount of
uncertainty about (or entropy of) a given input during various
stages of the computation. ... more >>>

TR98-051 | 20th July 1998
Petr Savicky

A probabilistic nonequivalence test for syntactic (1,+k)-branching programs

Branching programs are a model for representing Boolean
functions. For general branching programs, the
satisfiability and nonequivalence tests are NP-complete.
For read-once branching programs, which can test each
variable at most once in each computation, the satisfiability
test is trivial and there is also a probabilistic polynomial
time test ... more >>>

TR98-053 | 30th August 1998
Paul Beame, Michael Saks, Jayram S. Thathachar

Time-Space Tradeoffs for Branching Programs

Comments: 1

We obtain the first non-trivial time-space tradeoff lower bound for
functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a
Boolean function f that requires exponential size to be computed by any
branching program of length cn, for some constant c>1. We also give the first
separation result between the ... more >>>

TR99-019 | 7th June 1999
Detlef Sieling

Lower Bounds for Linear Transformed OBDDs and FBDDs

Linear Transformed Ordered Binary Decision Diagrams (LTOBDDs) have
been suggested as a generalization of OBDDs for the representation and
manipulation of Boolean functions. Instead of variables as in the
case of OBDDs parities of variables may be tested at the nodes of an
LTOBDD. By this extension it is ... more >>>

TR99-044 | 30th September 1999
Farid Ablayev

On Complexity of Regular $(1,+k)$-Branching Programs

A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an
ordinary branching program with the following restrictions: (i)
along every consistent path at most $k$ variables are tested more
than once, (ii) for each node $v$ on all paths from the source to
$v$ the same set $X(v)\subseteq X$ of variables is ... more >>>

TR00-025 | 20th May 2000
Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

Super-linear time-space tradeoff lower bounds for randomized computation

We prove the first time-space lower bound tradeoffs for randomized
computation of decision problems. The bounds hold even in the
case that the computation is allowed to have arbitrary probability
of error on a small fraction of inputs. Our techniques are an
extension of those used by Ajtai in his ... more >>>

TR00-057 | 25th July 2000
Martin Sauerhoff

An Improved Hierarchy Result for Partitioned BDDs

One of the great challenges of complexity theory is the problem of
analyzing the dependence of the complexity of Boolean functions on the
resources nondeterminism and randomness. So far, this problem could be
solved only for very few models of computation. For so-called
partitioned binary decision diagrams, which are a ... more >>>

TR00-058 | 1st August 2000
Martin Sauerhoff

Approximation of Boolean Functions by Combinatorial Rectangles

This paper deals with the number of monochromatic combinatorial
rectangles required to approximate a Boolean function on a constant
fraction of all inputs, where each rectangle may be defined with
respect to its own partition of the input variables. The main result
of the paper is that the number of ... more >>>

TR01-049 | 11th July 2001
Stasys Jukna, Georg Schnitger

On Multi-Partition Communication Complexity of Triangle-Freeness

Comments: 2

We show that recognizing the $K_3$-freeness and $K_4$-freeness of
graphs is hard, respectively, for two-player nondeterministic
communication protocols with exponentially many partitions and for
nondeterministic (syntactic) read-$s$ times branching programs.

The key ingradient is a generalization of a coloring lemma, due to
Papadimitriou and Sipser, which says that for every ... more >>>

TR01-073 | 24th October 2001
Beate Bollig, Philipp Woelfel, Stephan Waack

Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Revisions: 1

Branching programs are a well-established computation model
for Boolean functions, especially read-once branching programs
have been studied intensively. Exponential lower bounds for
deterministic and nondeterministic read-once branching programs
are known for a long time. On the other hand, the problem of
proving superpolynomial lower bounds ... more >>>

TR01-101 | 14th December 2001
Philipp Woelfel

A Lower Bound Technique for Restricted Branching Programs and Applications

We present a new lower bound technique for two types of restricted
Branching Programs (BPs), namely for read-once BPs (BP1s) with
restricted amount of nondeterminism and for (1,+k)-BPs. For this
technique, we introduce the notion of (strictly) k-wise l-mixed
Boolean functions, which generalizes the concept of l-mixedness ... more >>>

TR02-013 | 30th January 2002
Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

Quantum and Stochastic Programs of Bounded Width

Revisions: 1

We prove upper and lower bounds on the power of quantum and stochastic
branching programs of bounded width. We show any NC^1 language can
be accepted exactly by a width-2 quantum branching program of
polynomial length, in contrast to the classical case where width 5 is
necessary unless \NC^1=\ACC. ... more >>>

TR02-033 | 11th June 2002
Beate Bollig

A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

Branching programs are a well-established computation
model for boolean functions, especially read-once
branching programs (BP1s) have been studied intensively.
A very simple function $f$ in $n^2$ variables is
exhibited such that both the function $f$ and its negation
$\neg f$ can be computed by $\Sigma^3_p$-circuits,
the ... more >>>

TR04-107 | 24th November 2004
Ingo Wegener, Philipp Woelfel

New Results on the Complexity of the Middle Bit of Multiplication

Revisions: 1

It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MUL_{n-1,n}.
This paper contains several new results on its complexity.
First, the size s of randomized read-k branching programs, or, equivalently, its space (log s) is investigated.
A randomized algorithm for MUL_{n-1,n} with k=O(log ... more >>>

TR05-136 | 14th November 2005
Anna Gal, Michal Koucky, Pierre McKenzie

Incremental branching programs

In this paper we propose the study of a new model of restricted
branching programs which we call incremental branching programs.
This is in line with the program proposed by Cook in 1974 as an
approach for separating the class of problems solvable in logarithmic
space from problems solvable ... more >>>

TR07-087 | 11th July 2007
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

Arithmetizing classes around NC^1 and L

The parallel complexity class NC^1 has many equivalent models such as
polynomial size formulae and bounded width branching
programs. Caussinus et al. \cite{CMTV} considered arithmetizations of
two of these classes, #NC^1 and #BWBP. We further this study to
include arithmetization of other classes. In particular, we show that
counting paths ... more >>>

TR08-048 | 8th April 2008
Meena Mahajan, B. V. Raghavendra Rao

Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae

Functions in arithmetic NC1 are known to have equivalent constant
width polynomial degree circuits, but the converse containment is
unknown. In a partial answer to this question, we show that syntactic
multilinear circuits of constant width and polynomial degree can be
depth-reduced, though the resulting circuits need not be ... more >>>

TR10-104 | 29th June 2010
Paul Beame, Widad Machmouchi

Making RAMs Oblivious Requires Superlogarithmic Overhead

Revisions: 3 , Comments: 1

We prove a time-space tradeoff lower bound of $T =
\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for
randomized oblivious branching programs to compute $1GAP$, also
known as the pointer jumping problem, a problem for which there is a
simple deterministic time $n$ and space $O(\log n)$ RAM (random
access machine) algorithm.

In ... more >>>

TR10-133 | 20th August 2010
Parikshit Gopalan, Adam Klivans, Raghu Meka

Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs

We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with total weight W and accuracy parameter eps, our algorithm produces a (1 + eps)-multiplicative approximation in time poly(n,log W,1/eps). We also give algorithms ... more >>>

TR11-117 | 3rd September 2011
Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan

Pseudorandomness for read-once formulas

We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in $n$ inputs and arbitrary gates of fan-in at most $d = O(n/\log n)$, the pseudorandom generator uses $(1 - \Omega(1))n$ bits of randomness and produces an output ... more >>>

TR11-134 | 9th October 2011
Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

Separating multilinear branching programs and formulas

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of ... more >>>

TR12-057 | 7th May 2012
Russell Impagliazzo, Raghu Meka, David Zuckerman

Pseudorandomness from Shrinkage

Revisions: 2

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models ... more >>>

TR12-115 | 11th September 2012
Michael Forbes, Amir Shpilka

Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

Revisions: 1

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing (PIT) algorithms for read-once oblivious algebraic branching programs (ABPs). This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work had no known such black-box algorithm. Here we ... more >>>

TR13-006 | 8th January 2013
Balagopal Komarath, Jayalal Sarma

Pebbling, Entropy and Branching Program Size Lower Bounds

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al.(2011). Proving an exponential lower bound for the size of the non-deterministic thrifty branching programs would separate NL from P under the thrifty hypothesis. In this ... more >>>

TR13-086 | 13th June 2013
Omer Reingold, Thomas Steinke, Salil Vadhan

Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

TR14-076 | 27th May 2014
Thomas Steinke

Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs

Revisions: 1

We present an explicit pseudorandom generator for oblivious, read-once, width-$3$ branching programs, which can read their input bits in any order. The generator has seed length $\tilde{O}( \log^3 n ).$ The previously best known seed length for this model is $n^{1/2+o(1)}$ due to Impagliazzo, Meka, and Zuckerman (FOCS '12). Our ... more >>>

TR15-024 | 16th February 2015
Oded Goldreich, Tom Gur, Ron Rothblum

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>>

TR15-029 | 18th February 2015
Stanislav Zak

Inherent logic and complexity

Abstract. The old intuitive question "what does the machine think" at
different stages of its computation is examined. Our paper is based on
the formal de nitions and results which are collected in the branching
program theory around the intuitive question "what does the program
know about the contents of ... more >>>

TR15-048 | 14th February 2015
Kamil Khadiev

Width Hierarchy for $k$-OBDD of Small Width

Revisions: 1

In this paper was explored well known model $k$-OBDD. There are proven width based hierarchy of classes of boolean functions which computed by $k$-OBDD. The proof of hierarchy is based on sufficient condition of Boolean function's non representation as $k$-OBDD and complexity properties of Boolean
function SAF. This function is ... more >>>

TR17-120 | 31st July 2017
Paul Beame, Shayan Oveis Gharan, Xin Yang

Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions

Revisions: 1

We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior ... more >>>

TR17-122 | 28th July 2017
Rohit Gurjar, Ben Lee Volk

Pseudorandom Bits for Oblivious Branching Programs

We construct a pseudorandom generator which fools read-$k$ oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polynomial width branching programs, the seed lengths in our constructions are $\tilde{O}(n^{1-1/2^{k-1}})$ (for the ... more >>>

ISSN 1433-8092 | Imprint