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

(referuje Ondřej Zajíček)

• 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

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

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

(referuje Tomáš Ebenlendr)

Arist Kojevnikov: Improved Lower Bounds for Resolution over Linear Inequalities.

(referuje Martin Pergel)

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

28. 2., 7. 3. 2007

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.