Petr Savický
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Petr Savický has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Alexander Razborov
Steklov Mathematical Institute
1 shared publication - Ingo Wegener
FB Informatik, LS II, Universität Dortmund, 44221 Dortmund, Germany , DE
1 shared publication - Ingo Wegener
FB Informatik Universität Dortmund LS2 44221 Dortmund Germany
1 shared publication - Ingo Wegener
University of Dortmund
1 shared publication - Matthias Krause
Theoretische Informatik, University of Mannheim, 68131 Mannheim, Germany
1 shared publication - Stasys Jukna
Department of Computer Science, University of Trier, D-54286 Trier, Germany
1 shared publication
Latest Publications
- 3 August 2005
- Published by Elsevier in Information and Computation
- Vol. 201 (2) , 160-177
On the influence of the variable ordering for algorithmic learning using OBDDs
- 3 August 2005
- Published by Elsevier in Information and Computation
- Vol. 201 (2) , 160-177
On the influence of the variable ordering for algorithmic learning using OBDDs
- 1 May 2000
- Published by Wiley in Random Structures & Algorithms
- Vol. 16 (3) , 233-239
On random orderings of variables for parity ordered binary decision diagrams
- 1 May 2000
- Published by Wiley in Random Structures & Algorithms
- Vol. 16 (3) , 233-239
On random orderings of variables for parity ordered binary decision diagrams
- 1 December 1999
- Published by Springer Nature in computational complexity
- Vol. 8 (4) , 357-370
On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs- 1 December 1999
- Published by Springer Nature in computational complexity
- Vol. 8 (4) , 357-370
On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs- 1 December 1998
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 7 (4) , 451-463
Complexity and Probability of Some Boolean Formulas
For any Boolean function f, let L(f) be its formula size complexity in the basis {∧, [oplus ] 1}. For every n and every k[les ]n/2, we describe a probabilistic distribution on formulas in the basis {∧, [oplus ] 1} in some given set of n variables and of size at most [lscr ](k)=4k. Let pn,k(f) be the probability that the formula chosen from the distribution computes the function f. For every function f with L(f)[les ][lscr ](k)α, where α=log4(3/2), we have pn,k(f)>0. Moreover, for every function f, if pn,k(f)>0, thenformula herewhere c>1 is an absolute constant. Although the upper and lower bounds are exponentially small in [lscr ](k), they are quasi-polynomially related whenever [lscr ](k)[ges ]lnΩ(1)n. The construction is a step towards developing a model appropriate for investigation of the properties of a typical (random) Boolean function of some given complexity.
- 1 December 1998
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 7 (4) , 451-463
Complexity and Probability of Some Boolean Formulas
For any Boolean function f, let L(f) be its formula size complexity in the basis {∧, [oplus ] 1}. For every n and every k[les ]n/2, we describe a probabilistic distribution on formulas in the basis {∧, [oplus ] 1} in some given set of n variables and of size at most [lscr ](k)=4k. Let pn,k(f) be the probability that the formula chosen from the distribution computes the function f. For every function f with L(f)[les ][lscr ](k)α, where α=log4(3/2), we have pn,k(f)>0. Moreover, for every function f, if pn,k(f)>0, thenformula herewhere c>1 is an absolute constant. Although the upper and lower bounds are exponentially small in [lscr ](k), they are quasi-polynomially related whenever [lscr ](k)[ges ]lnΩ(1)n. The construction is a step towards developing a model appropriate for investigation of the properties of a typical (random) Boolean function of some given complexity.
- 1 April 1997
- Published by Springer Nature in Acta Informatica
- Vol. 34 (4) , 245-256
Efficient algorithms for the transformation between different types of binary decision diagrams
- 1 April 1997
- Published by Springer Nature in Acta Informatica
- Vol. 34 (4) , 245-256
Efficient algorithms for the transformation between different types of binary decision diagrams