All reports by Author Stanislav Zak:

__
TR15-029
| 18th February 2015
__

Stanislav Zak#### Inherent logic and complexity

__
TR10-088
| 17th May 2010
__

Jiri Sima, Stanislav Zak#### A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

Revisions: 2
,
Comments: 3

__
TR01-039
| 18th May 2001
__

Stasys Jukna, Stanislav Zak#### On Uncertainty versus Size in Branching Programs

Revisions: 1

__
TR98-030
| 9th June 1998
__

Stasys Jukna, Stanislav Zak#### On Branching Programs With Bounded Uncertainty

__
TR97-050
| 27th October 1997
__

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

__
TR96-050
| 23rd September 1996
__

Petr Savicky, Stanislav Zak#### A hierarchy for (1,+k)-branching programs with respect to k

__
TR96-036
| 28th May 1996
__

Petr Savicky, Stanislav Zak#### A large lower bound for 1-branching programs

Revisions: 1

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

Jiri Sima, Stanislav Zak

The relationship between deterministic and probabilistic computations is one of the central issues in complexity theory. This problem can be tackled by constructing polynomial time hitting set generators which, however, belongs to the hardest problems in computer science even for severely restricted computational models. In our work, we consider read-once ... more >>>

Stasys Jukna, Stanislav Zak

We propose an information-theoretic approach to proving lower

bounds on the size of branching programs. The argument is based on

Kraft-McMillan type inequalities for the average amount of

uncertainty about (or entropy of) a given input during the various

stages of computation. The uncertainty is measured by the average

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

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

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

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