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

**23. 5. 2006 **(úterý [Tuesday], 11.00,
MÚ Žitná 25)

(referuje Marek Krčál)

Abstract: We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded bias (according to some measure) even if one of the two parties deviates from the protocol (even using unlimited computational resources). Specifically, we require that the output's statistical difference from the uniform distribution on {0,1}^n is bounded by a constant less than 1. We present a protocol for the above problem that has 2 log* n + O(1) rounds, improving a previous n-round protocol of Goldreich, Goldwasser, and Linial (FOCS `91). We then prove a matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least log* n- log* log* n-O(1) rounds. As far as we know, this is the first nontrivial lower bound on the round complexity of random selection protocols (of any type) that does not impose additional constraints (e.g. on communication or ``simulatability'').

**9. 5., 16. 5. 2006 **(úterý [Tuesday], 11.00,
MÚ Žitná 25)

**E. Viola: On Probabilistic Time versus Alternating Time. **

(referuje
Martin Pergel)

Abstract: Sipser and Gács,
and independently Lautemann, proved in '83 that probabilistic
polynomial time is contained in the second level of the polynomial-time
hierarchy, i.e. BPP is in \Sigma_2 P. This is essentially the only
non-trivial upper bound that we have on the power of probabilistic
computation. More precisely, the Sipser-Gács-Lautemann simulation shows
that probabilistic time can be simulated deterministically, using two
quantifiers, **with a quadratic blow-up in the running time**. That is,
BPTime(t) is contained in \Sigma_2 Time(t^2).

We discuss whether this quadratic blow-up in the running time is
necessary. We show that the quadratic blow-up is indeed necessary for
black-box simulations that use two quantifiers, such as those of
Sipser, Gács, and Lautemann. To obtain this result, we prove a new
circuit lower bound for computing **approximate majority**, i.e.
computing the majority of a given bit-string whose fraction of 1's is
bounded away from 1/2 (by a constant): We show that small depth-3
circuits for approximate majority must have bottom fan-in Omega(log n).

On the positive side, we obtain that probabilistic time can be
simulated deterministically, using three quantifiers, in quasilinear
time. That is, BPTime(t) is contained in \Sigma_3 Time(t polylog t).
Along the way, we show that approximate majority can be computed by
uniform polynomial-size depth-3 circuits. This is a uniform version of
a striking result by Ajtai that gives *non-uniform* polynomial-size
depth-3 circuits for approximate majority.

**2. 5. 2006 **(úterý [Tuesday], 11.00,
MÚ Žitná 25)

G. Cormode,
S. Muthukrishnan: What's hot and what's not: tracking most frequent
items
dynamically.

ACM
Trans. Database Syst. 30(1): 249-278 (2005).

(referuje Ondřej Zajíček)

N. Alon, Y. Matias and M. Szegedy:

The space complexity of
approximating the frequency moments, J. Comp. Sys. Sci. 58
(1999),
137-147.

(referuje Tomáš Ebenlendr)

Marek Krčál: Complexity of graph
planarity testing

Abstract:
We will give the second proof that the problem of
planarity testing is in \SL (symmetric nondeterministic LOGSPACE). It
will be done by showing a reduction of the problem to planarity of
graph with maximal degree three. Note that usual replacing vertices of
degree bigger than three by "little circles" can spoil planarity, we
need to be smarter. Planarity of graphs with maximal degree three was
already solved in paper "Symmetric complementation" by John Reif.

Our approach is very different and hopefully more intuitive than the
one in the first proof by Meena Mahajan and Eric Allender ("Complexity
of planarity testing"), which is pure \SL implementation of a very
complicated parallel algorithm by John Reif.

This result together with recent breakthrough by Omer Reingold that
\SL=\L ("Undirected {ST}-connectivity in log-space") completely solves
the question of complexity of planarity problem, because planarity is
hard for \L (it is again shown in "Complexity of planarity testing").

Abstract: I will give an introduction to the area of sublinear algorithms which includes sublinear approximation algorithms and property testing. In general sublinear algorithms are once which on input of size n run in time o(n), e.g., poly-logarithmic time. Typically they are randomized and one cannot expect an exact solution of his problem from them but rather an approximate one.

I will show such algorithms for three problems: clustering data, testing a graph connectivity, and testing whether a sequence is sorted. The talk will loosely follow the survey paper of Kumar and Rubinfeld of the same title.