All reports by Author Farid Ablayev:

__
TR08-085
| 19th June 2008
__

Farid Ablayev, Airat Khasianov, Alexander Vasiliev#### On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

Revisions: 1

__
TR08-059
| 20th May 2008
__

Farid Ablayev, Alexander Vasiliev#### On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting

Revisions: 1

__
TR02-013
| 30th January 2002
__

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett#### Quantum and Stochastic Programs of Bounded Width

Revisions: 1

__
TR99-044
| 30th September 1999
__

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

__
TR98-050
| 6th July 1998
__

Farid Ablayev, Svetlana Ablayeva#### A Discrete Approximation and Communication Complexity Approach to the Superposition Problem

__
TR98-011
| 29th January 1998
__

Farid Ablayev, Marek Karpinski#### A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs

__
TR98-004
| 13th January 1998
__

Farid Ablayev, Marek Karpinski#### On the Power of Randomized Ordered Branching Programs

__
TR97-021
| 16th May 1997
__

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

__
TR95-054
| 24th November 1995
__

Farid Ablayev, Marek Karpinski#### On the Power of Randomized Branching Programs

Farid Ablayev, Airat Khasianov, Alexander Vasiliev

We consider Generalized Equality, the Hidden Subgroup,

and related problems in the context of quantum Ordered Binary

Decision Diagrams. For the decision versions of considered problems

we show polynomial upper bounds in terms of quantum OBDD width. We

apply a new modification of the fingerprinting technique and present

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

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

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

Farid Ablayev, Svetlana Ablayeva

The superposition (or composition) problem is a problem of

representation of a function $f$ by a superposition of "simpler" (in a

different meanings) set $\Omega$ of functions. In terms of circuits

theory this means a possibility of computing $f$ by a finite circuit

with 1 fan-out gates $\Omega$ of functions. ...
more >>>

Farid Ablayev, Marek Karpinski

We prove an exponential lower bound ($2^{\Omega(n/\log n)}$) on the

size of any randomized ordered read-once branching program

computing integer multiplication. Our proof depends on proving

a new lower bound on Yao's randomized one-way communication

complexity of certain boolean functions. It generalizes to some

other ...
more >>>

Farid Ablayev, Marek Karpinski

We introduce a model of a {\em randomized branching program}

in a natural way similar to the definition of a randomized circuit.

We exhibit an explicit boolean function

$f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that:

1) $f_{n}$ can be computed by a polynomial size 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 >>>

Farid Ablayev, Marek Karpinski

We define the notion of a randomized branching program in

the natural way similar to the definition of a randomized

circuit. We exhibit an explicit function $f_{n}$ for which

we prove that:

1) $f_{n}$ can be computed by polynomial size randomized

...
more >>>