Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

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 >>>

Stasys Jukna

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 >>>

Detlef Sieling

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 >>>

Pavel Pudlak, Jiri Sgall

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 >>>

Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio

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 >>>

Petr Savicky, Stanislav Zak

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 >>>

Thomas Thierauf

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 >>>

Petr Savicky, Stanislav Zak

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 >>>

Farid Ablayev

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 >>>

Martin Sauerhoff

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 >>>

Stanislav Zak

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 >>>

Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim

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 >>>

Stasys Jukna, Stanislav Zak

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 >>>

Petr Savicky

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 >>>

Paul Beame, Michael Saks, Jayram S. Thathachar

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 >>>

Detlef Sieling

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 >>>

Farid Ablayev

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 >>>

Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

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 >>>

Martin Sauerhoff

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 >>>

Martin Sauerhoff

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 >>>

Stasys Jukna, Georg Schnitger

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 >>>

Beate Bollig, Philipp Woelfel, Stephan Waack

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 >>>

Philipp Woelfel

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 >>>

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

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 >>>

Beate Bollig

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 >>>

Ingo Wegener, Philipp Woelfel

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 >>>

Anna Gal, Michal Koucky, Pierre McKenzie

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 >>>

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

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 >>>

Meena Mahajan, B. V. Raghavendra Rao

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 >>>

Paul Beame, Widad Machmouchi

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 >>>

Parikshit Gopalan, Adam Klivans, Raghu Meka

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 >>>

Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan

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 >>>

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

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 >>>

Russell Impagliazzo, Raghu Meka, David Zuckerman

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 >>>

Michael Forbes, Amir Shpilka

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 >>>

Balagopal Komarath, Jayalal Sarma

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 >>>

Omer Reingold, Thomas Steinke, Salil Vadhan

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 >>>

Thomas Steinke

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 >>>

Oded Goldreich, Tom Gur, Ron Rothblum

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 >>>

Stanislav Zak

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 >>>

Kamil Khadiev

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 >>>

Paul Beame, Shayan Oveis Gharan, Xin Yang

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 >>>

Rohit Gurjar, Ben Lee Volk

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 >>>

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work ... more >>>

Kamil Khadiev, Aliya Khadiev, Alexander Knop

In this paper, we study quantum OBDD model, it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present ... more >>>

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $\theta$, for a given parameter $\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>>

Stanislav Žák

We present a mathematical model of the intuitive notions such as the

knowledge or the information arising at different stages of

computations on branching programs (b.p.). The model has two

appropriate

properties:\\

i) The "knowledge" arising at a stage of computation in question is

derivable from the "knowledge" arising ...
more >>>

Ran Raz, Wei Zhan

We study a new model of space-bounded computation, the {\it random-query} model. The model is based on a branching-program over input variables $x_1,\ldots,x_n$. In each time step, the branching program gets as an input a random index $i \in \{1,\ldots,n\}$, together with the input variable $x_i$ (rather than querying an ... more >>>

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A ... more >>>

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.

We prove that constant-width monotone branching programs of ... more >>>

Anastasia Sofronova, Dmitry Sokolov

Restricted branching programs capture various complexity measures like space in Turing machines or length of proofs in proof systems. In this paper, we focus on the application in the proof complexity that was discovered by Lovasz et al. '95 who showed the equivalence between regular Resolution and read-once branching programs ... more >>>

Robert Robere, Jeroen Zuiddam

We study the amortized circuit complexity of boolean functions.

Given a circuit model $\mathcal{F}$ and a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, the $\mathcal{F}$-amortized circuit complexity is defined to be the size of the smallest circuit that outputs $m$ copies of $f$ (evaluated on the same input), ...
more >>>

James Cook, Ian Mertz

An $m$-catalytic branching program (Girard, Koucky, McKenzie 2015) is a set of $m$ distinct branching programs for $f$ which are permitted to share internal (i.e. non-source non-sink) nodes. While originally introduced as a non-uniform analogue to catalytic space, this also gives a natural notion of amortized non-uniform space complexity for ... more >>>

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro

We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, ... more >>>

Aaron (Louie) Putterman, Edward Pyne

We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length $n$ and width $w$ in space

$$\tilde{O}\left(\log n+\sqrt{\log n}\cdot\log w\right).$$

In particular, we obtain an almost optimal space $\tilde{O}(\log n)$ derandomization of programs up to width $w=2^{\sqrt{\log n}}$.

Previously, ...
more >>>

Paul Beame, Niels Kornerup

Cumulative memory---the sum of space used over the steps of a computation---is a fine-grained measure of time-space complexity that is a more accurate measure of cost for algorithms with infrequent spikes in memory usage in the context of technologies such as cloud computing that allow dynamic allocation and de-allocation of ... more >>>

Huacheng Yu, Wei Zhan

We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the input of $n$ elements in $[n]$, outputs $O(n)$ elements, such that:

- There exists a randomized oblivious algorithm with space $O(\log n)$, time $O(n\log n)$ ... more >>>

Chin Ho Lee, Edward Pyne, Salil Vadhan

We give new upper and lower bounds on the power of several restricted classes of arbitrary-order read-once branching programs (ROBPs) and standard-order ROBPs (SOBPs) that have received significant attention in the literature on pseudorandomness for space-bounded computation.

Regular SOBPs of length $n$ and width $\lfloor w(n+1)/2\rfloor$ can exactly simulate general ... more >>>

James Cook, Ian Mertz

The Tree Evaluation Problem ($TreeEval$) (Cook et al. 2009) is a central candidate for separating polynomial time ($P$) from logarithmic space ($L$) via composition. While space lower bounds of $\Omega(\log^2 n)$ are known for multiple restricted models, it was recently shown by Cook and Mertz (2020) that TreeEval can be ... more >>>