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

Pavel Pudlák, Jiří Sgall

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

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

Saurabh Sanghvi and Salil Vadhan: The Round Complexity of Two-Party Random Selection. STOC'05
(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, im­proving 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)

Abstract: Most database management systems maintain statistics on the underlying relation. One of the important statistics is that of the ``hot items'' in the relation: those that appear many times (most frequently, or more than some threshold). For example, end­biased histograms keep the hot items as part of the histogram and are used in selectivity estimation. Hot items are used as simple outliers in data mining, and in anomaly detection in networking applications. We present a new algorithm for dynamically determining the hot items at any time in the relation that is undergoing deletion operations as well as inserts. Our algorithm maintains a small space data structure that monitors the transactions on the relation, and when required, quickly outputs all hot items, without rescanning the relation in the database. With user ­specified probability, it is able to report all hot items. Our algorithm relies on the idea of ``group testing'', is simple to implement, and has provable quality, space and time guarantees. Previously known algorithms for this problem that make similar quality and performance guarantees can not handle deletions, and those that handle deletions can not make similar guarantees without rescanning the database. Our experiments with real and synthetic data shows that our algorithm is remarkably accurate in dynamically tracking the hot items independent of the rate of insertions and deletions.

28. 3., 4. 4., 11. 4. 2006 (úterý [Tuesday], 11.00, MÚ Žitná 25, 1. patro zadní budovy)

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)

Abstract: The frequency moments of a sequence containing m_i elements of type i, are the numbers Fk = \sum  m_i^k. We consider the space complexity of randomized algorithms that approximate the numbers Fk, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F0; F1 and F2 can be approximated in logarithmic space, whereas the approximation of Fk for k >=6 requires n^Omega(1) space. Applications to data bases are mentioned as well.

21. 3. 2006 (úterý [Tuesday], 11.00, MÚ Žitná 25, 1. patro zadní budovy)

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

7. 3. 2006 (úterý [Tuesday], 11.00, MÚ Žitná 25, 1. patro zadní budovy)

Michal Koucký: Sublinear time algorithms

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.