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