Seminář z výpočetní složitosti
Pavel Pudlák, Jiří Sgall
Předchozí program semináře, zimní semestr 1999 [Previous program, Fall
1999]
10. 1. 2000 (pondělí [Monday], 10.05, MÚ Žitná
25, 3. patro)
Yuval Ishai, Eyal Kushilevitz: Improved Upper Bounds on Information-Theoretic
Private Information Retrieval.
STOC 1999: 79-88
(Referuje Martin Mares)
13. 12. 1999 (pondělí [Monday], 10.05, MÚ Žitná 25,
3. patro)
Daniel Kral:
Ordered binary decision diagrams (OBDDs) and parity order decision
binary diagrams have proved their importance as data structures representing
Boolean functions. In addition to parity OBDDs we study their generalization
which we call parity AOBDDs, give the algebraic characterization theorem
and compare their minimal size to the size of parity OBDDs.
We prove the existence of node-minimal parity (A)OBDDs without arcs
testing conditions x_i=0, and give an efficient algorithm for finding such
parity
(A)OBDDs. We define so-called uniqueness conditions, use them to obtain
a canonical form for parity OBDDs and discuss similar results for parity
AOBDDs.
Algorithms for minimalization and finding the form which satisfies
the uniqueness conditions for parity OBDDs running in time O(S^3) and for
parity AOBDDs running in time O(nS^3) are presented; both the algorithms
are quite simple.
All our results are also extended to the case of shared parity OBDDs
and shared parity AOBDDs - data structures for representation of Boolean
function sequences.
29. 11. 1999 (pondělí [Monday], 10.05, MÚ Žitná
25, 3. patro)
Valiantovy výsledky o použití argumentu z teorie grafů pro dolní odhady
na Booleovské obvody.
(referuje P. Pudlak)
25. 10. 1999 (pondělí [Monday], 10.00, MÚ Žitná
25, 3. patro)
S. Žák: Branching programy s omezenou neurcitosti.
Netradicni pohled na sekvencni pocitani. Nova metoda dolnich odhadu
pro obecne branching programy. Pokus o zachyceni pojmu "jednoducha" funkce.
Dolni meze.
11.10., 18. 10., 8.11., 15. 11., 6.12. 1999 (pondělí
[Monday], 10.00,
MÚ Žitná 25, 3. patro)
Miklos Ajtai: Determinism versus Non-Determinism for Linear Time RAMs
with Memory Restrictions
Electronic Colloquium on Computational Complexity, ECCC
Report TR98-077, 1998
Miklos Ajtai: A Non-linear Time Lower Bound for Boolean Branching
Programs
Electronic Colloquium on Computational Complexity, ECCC
Report TR99-026, 1999
(referuje P. Pudlak a J. Sgall)
4. 10. 1999 (pondělí [Monday], 10.00, MÚ Žitná
25, 3. patro)
Úvodní seminář bude úvod do branching programů (přednese buď Pavel Pudlák
nebo já), abychom se pak mohli pustit do Ajtaiova nového dolního odhadu.