Seminář z výpočetní složitosti

Pavel Pudlák, Jiří Sgall

Předchozí program semináře, letní semestr 2007 [Previous program, Spring 2007]

23. 5. 2007 (středa [Wednesday], 14:30, MÚ Žitná 25)

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Cryptography from Anonymity. FOCS'06. Final conference version.
(referuje Ondřej Zajíček)

Abstract: There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on anonymity in a variety of cryptographic contexts. Our results go in two directions.
• Feasibility. We show that anonymous communication over insecure channels can be used to implement unconditionally secure point-to-point channels, and hence general multi-party protocols with unconditional security in the presence of an honest majority. In contrast, anonymity cannot be generally used to obtain unconditional security when there is no honest majority.
• Efficiency. We show that anonymous channels can yield substantial efficiency improvements for several natural secure computation tasks. In particular, we present the first solution to the problem of private information retrieval (PIR) which can handle multiple users while being close to optimal with respect to both communication and computation. A key observation that underlies these results is that local randomization of inputs, via secret-sharing, when combined with the global mixing of the shares, provided by anonymity, allows to carry out useful computations on the inputs while keeping the inputs private.

9. 5. 2007 (středa [Wednesday], 14:30, MÚ Žitná 25)

Troy Lee: A rank technique for formula size lower bounds

Abstract: We introduce a new technique for proving formula size lower bounds based on matrix rank. A simple form of this technique gives bounds at least as large as those given by the method of Khrapchenko, originally used to prove an $n^2$ lower bound on the parity function. Applying our method to the parity function, we are able to give an exact expression for the formula size of parity: if $n=2^\ell +k$, where $0\le k < 2^\ell$, then the formula size of parity on $n$ bits is exactly $2^\ell(2^\ell+3k)=n^2+k2^\ell-k^2$. Such a bound cannot be proven by any of the lower bound techniques of Khrapchenko, Ne\v{c}iporuk, Koutsoupias, or the quantum adversary method, which are limited by $n^2$.

2. 5. 2007 (středa [Wednesday], 14:30, MÚ Žitná 25)

Dmitry Gavinski: Classical interaction cannot replace a quantum message
The transparencies (and the paper) can be found here: http://www.iqc.ca/~dgavinsky/talks/index.html (the newest item).

Abstract: We give a communication problem between two players, Alice and Bob, that can be solved by Alice sending a quantum message to Bob, for which any classical interactive protocol requires exponentially more communication. No prior knowledge is required, either quantum or classical :-)
28. 3., 11. 4. 2007 (středa [Wednesday], 14:30, MÚ Žitná 25)

Amnon Ta-Shma and Uri Zwick: Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. SODA'07.
(referuje Tomáš Ebenlendr)

Abstract: We obtain several improved solutions for the determini stic rendezvous problem in general undirected graphs. Our solutions answer several problems left open in a rec ent paper by Dessmark et al. We also introduce an interesting variant of the rendezvous problem which we call the deterministic treasure hunt problem. Both the rendezvous and the treasure hunt problems motivate the study of universal traversal sequences and universal exploration sequences with some strengthened properties. We call such sequences strongly universal traversal (exploration) sequences. We give an explicit construction of strongly universal exploration sequences. The exist ence of strongly universal traversal sequences, as well as the solution of the most difficult variant of the det erministic treasure hunt problem, are left as intriguing open problems.

21. 3. 2007 (středa [Wednesday], 14:30, MÚ Žitná 25)

Arist Kojevnikov: Improved Lower Bounds for Resolution over Linear Inequalities. ECCC TR07-010.
(referuje Martin Pergel)

Abstract: We continue a study initiated by Krajicek of a Resolution-like proof system working with clauses of linear inequalities, R(CP). For all proof systems of this kind Krajicek proved an exponential lower bound that depends on the maximal absolute value of coefficients in the given proof and the maximal clause width. In this paper we improve his lower bound for two restricted versions of R(CP)-like proof systems. For tree-like R(CP)-like proof systems we remove a dependence on the maximal absolute value of coefficients. Proof follows from an upper bound on the real communication complexity of a polyhedra. For R(CP) we remove a dependence on the maximal clause width. Proof follows from the fact that in R(CP) at each step we modify at most one inequality in a clause. Hence, we can use information about other inequalities from previous steps and do not need to check all inequalities in the clause.

14. 3. 2007 (středa [Wednesday], 14:30, MÚ Žitná 25)

Jan Krajíček: Spodní odhad pro OBDD důkazový systém.
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams. ECCC TR07-007.

Abstrakt:  Dokazeme exponencialni spodni odhad pro delky dukazu v dukazovem systemu, ktery pracuje se OBDD (definovan Atseriasem, Kolaitisem a Vardim). Nepredpokladame zadny specialni tvar dukazu ani zadne specialni usporadani promennych. Dukaz pouziva efektivni interpolaci pro semanticke derivace.

28. 2., 7. 3. 2007 (středa [Wednesday], 14:30, MÚ Žitná 25)

Pavel Pudlák: O složitosti monotónniho lineárního programovaní

Abstrakt: Dokazat netrivialni dolni odhady na velikost linearnich programu je stejne obtizne, jako dokazat dolni odhady na slozitost booleovskych obvodu. Tedy vysledek tohoto druhu by znamenal velky prulom. V prednasce se budu zabyvat problemem, ktery je pravdepodobne podstatne lehci. Budeme uvazovat linearni programy jako prostredek k pocitani monotonnich funkci. Podstatne je, ze vstupy do techto programu jsou zadany take monotonnim zpusobem. Ukazeme zatim jen castecny vysledek: exponencialni dolni odhad pro pripad, ze matice linearnich monotonnich programu jsou v urcitem smyslu velice huste.