Martin Sauerhoff

In this paper, we are concerned with randomized OBDDs and randomized

read-k-times branching programs. We present an example of a Boolean

function which has polynomial size randomized OBDDs with small,

one-sided error, but only non-deterministic read-once branching

programs of exponential size. Furthermore, we discuss a lower bound

technique for randomized ...
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 >>>

Petr Savicky

There are Boolean functions such that almost all orderings of

its variables yield an OBDD of polynomial size, but there are

also some exceptional orderings, for which the size is exponential.

We prove that for parity OBDDs the size for a random ordering

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

N. S. Narayanaswamy, C.E. Veni Madhavan

We present a new boolean function for which any Ordered Binary

Decision Diagram (OBDD) computing it has an exponential number

of nodes. This boolean function is obtained from Nisan's

pseudorandom generator to derandomize space bounded randomized

algorithms. Though the relation between hardness and randomness for

computational models is well ...
more >>>

Rustam Mubarakzjanov

Restricted branching programs are considered by the investigation

of relationships between complexity classes of Boolean functions.

Read-once ordered branching programs (or OBDDs) form the most restricted class

of this computation model.

Since the problem of proving exponential lower bounds on the complexity

for general probabilistic OBDDs is open so ...
more >>>

Jan Krajicek

We prove an exponential lower bound on the size of proofs

in the proof system operating with ordered binary decision diagrams

introduced by Atserias, Kolaitis and Vardi. In fact, the lower bound

applies to semantic derivations operating with sets defined by OBDDs.

We do not assume ...
more >>>

Farid Ablayev, Alexander Vasiliev

We develop quantum fingerprinting technique for constructing quantum

branching programs (QBPs), which are considered as circuits with an

ability to use classical bits as control variables.

We demonstrate our approach constructing optimal quantum ordered

binary decision diagram (QOBDD) for $MOD_m$ and $DMULT_n$ Boolean

functions. The construction of our technique also ...
more >>>

Airat Khasianov

We consider the \emph{Hidden Subgroup} in the context of quantum \emph{Ordered Binary Decision Diagrams}.

We show several lower bounds for this function.

In this paper we also consider a slightly more general definition of the

hidden subgroup problem (in contrast to that in \cite{khashsp1}). It turns out that ...
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 >>>

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

Alexander Knop

It is well-known that there is equivalence between ordered resolution and ordered binary decision diagrams (OBDD) [LNNW95]; i.e., for any unsatisfiable formula ?, the size of the smallest ordered resolution refutation of ? equal to the size of the smallest OBDD for the canonical search problem corresponding to ?. But ... more >>>

Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Atserias, Kolaitis, and Vardi [AKV04] showed that the proof system of Ordered Binary Decision Diagrams with conjunction and weakening, OBDD($\land$, weakening), simulates CP* (Cutting Planes with unary coefficients). We show that OBDD($\land$, weakening) can give exponentially shorter proofs than dag-like cutting planes. This is proved by showing that the Clique-Coloring ... more >>>

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>

Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov

This paper is motivated by seeking lower bounds on OBDD($\land$, weakening, reordering) refutations, namely OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1-NBP($\land$) refutations based on read-once nondeterministic branching programs. These generalize OBDD($\land$, reordering) refutations. There are polynomial size 1-NBP($\land$) refutations of the pigeonhole principle, hence ... more >>>

Dmitry Itsykson, Artur Riazanov

We prove that the proof system OBDD(and, weakening) is not automatable unless P = NP. The proof is based upon the celebrated result of Atserias and Muller [FOCS 2019] about the hardness of automatability for resolution. The heart of the proof is lifting with a multi-output indexing gadget from resolution ... more >>>