All reports by Author Petr Savicky:

__
TR13-191
| 26th December 2013
__

Petr Savicky#### Boolean functions with a vertex-transitive group of automorphisms

Revisions: 2
,
Comments: 1

__
TR02-009
| 17th January 2002
__

Petr Savicky#### On determinism versus unambiquous nondeterminism for decision trees

__
TR01-017
| 14th February 2001
__

Petr Savicky, Detlef Sieling#### A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism

__
TR99-011
| 14th April 1999
__

Matthias Krause, Petr Savicky, Ingo Wegener#### Approximations by OBDDs and the variable ordering problem

__
TR98-068
| 12th November 1998
__

Petr Savicky#### On Random Orderings of Variables for Parity OBDDs

__
TR98-051
| 20th July 1998
__

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

__
TR97-057
| 3rd November 1997
__

Petr Savicky#### Complexity and Probability of some Boolean Formulas

__
TR97-023
| 3rd June 1997
__

S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener#### On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs

__
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

Petr Savicky

A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. Several constructions of vertex-transitive functions and some of their properties are presented.

Petr Savicky

Let $f$ be a Boolean function. Let $N(f)=\dnf(f)+\dnf(\neg f)$ be the

sum of the minimum number of monomials in a disjunctive normal form

for $f$ and $\neg f$. Let $p(f)$ be the minimum size of a partition

of the Boolean cube into disjoint subcubes such that $f$ is constant on

more >>>

Petr Savicky, Detlef Sieling

Restricted branching programs are considered in complexity theory in

order to study the space complexity of sequential computations and

in applications as a data structure for Boolean functions. In this

paper (\oplus,k)-branching programs and (\vee,k)-branching

programs are considered, i.e., branching programs starting with a

...
more >>>

Matthias Krause, Petr Savicky, Ingo Wegener

Ordered binary decision diagrams (OBDDs) and their variants

are motivated by the need to represent Boolean functions

in applications. Research concerning these applications leads

also to problems and results interesting from theoretical

point of view. In this paper, methods from communication

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

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

Petr Savicky

For any Boolean function $f$ let $L(f)$ be its formula size

complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and

every $k\le n/2$, we describe a probabilistic distribution

on formulas in the basis $\{\land,\oplus,1\}$ in some given set of

$n$ variables and of the ...
more >>>

S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener

It is known that if a Boolean function f in n variables

has a DNF and a CNF of size at most N then f also has a

(deterministic) decision tree of size $\exp(O(\log n\log^2 N)$.

We show that this simulation {\em cannot} be ...
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 >>>