«DEC MAY Jun 1 2009 2010 2011 3 captures 2 Oct 09 - 1 May 10

Close Help

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

Pavel Pudlák, Jiří Sgall

Předchozí program semináře, zimní semestr 2006 [Previous program, Fall 2006]

29. 1. 2007 (pondělí [Monday], 13:00, MÚ Žitná 25)

David Peleg (Weizmann Institute, Israel): Localized Network Representations

Abstract: Labeling schemes are schemes for labeling the nodes of a graph in a way that will allow one to efficiently extract information concerning various properties of the nodes locally and directly from their labels. Of particular interest are compact label-based representations (i.e., ones using short labels). The talk will survey some known results concerning labeling schemes for graphs, including upper and lower bounds for several interesting functions and graph families, and will also discuss directions for future research.

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

Parikshit Gopalan: Constructing Ramsey Graphs from Boolean Function Representations. CCC'06. Also ECCC TR05-143.
(referuje Tomáš Ebenlendr)

Abstract: Explicit construction of Ramsey graphs or graphs with no large clique or independent set has remained a challenging open problem for a long time. While Erdos's probabilistic argument shows the existence of graphs on 2^n vertices with no clique or independent set of size 2n, the best known explicit constructions are far from this bound Constructing Ramsey graphs is closely related to polynomial representations of Boolean functions; Grolmusz has shown that a low degree representation for the OR function can be used to explicitly construct Ramsey graphs. We generalize the above relation by proposing a new framework.We propose a new definition of OR representations: a pair of polynomials represent the OR function on if the union of their zero sets contains all points in the hypercube except the origin.We give a simple construction of a Ramsey graph using such polynomials.Furthermore, we show that all the best known constructions, ones to due to Frankl-Wilson, Grolmusz and Alon are captured by this framework; they can all be derived from various OR representations of degree $O(sqrt{n})$ based on symmetric polynomials. Thus the barrier to better Ramsey constructions through current techniques appears to be the construction of lower degree representations. Using new algebraic techniques, we show that the above Ramsey constructions cannot be improved using symmetric polynomials.

13. 12., 20. 12. 2006 (středa [Wednesday], 14:30, MÚ Žitná 25)

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen: On the Complexity of Numerical Analysis. CCC'06. Also ECCC TR05-037.
(referuje Ondřej Zajíček)

Abstract: We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of understanding the complexity of the following problem, which we call PosSLP: Given a division-free straight-line program producing an integer N, decide whether N>0. We show that PosSLP lies in the counting hierarchy, and we show that if A is any language in the Boolean part of Polynomial-time over the Reals accepted by a machine whose machine constants are algebraic real numbers, then A is in P^PosSLP. Combining our results with work of Tiwari, we show that the Euclidean Traveling Salesman Problem lies in the counting hierarchy -- the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE.

29. 11. 2006 (středa [Wednesday], 14:30, MÚ Žitná 25)

Alexander S. Kulikov: Efficient Approaches to Proving Upper Bounds for NP-hard Problems

Abstract: In the talk we will discuss interesting approaches to designing efficient exact algorithms for NP-hard problems. These include splitting algorithms and automated analysis of their running time, local search algorithms, and combined complexity measures for estimating the running time of recursive algorithms. We will give the main ideas of the proofs of currently best known upper bounds for well-known NP-hard problems such as satisfiability, maximum satisfiability, maximum cut, maximum independent set. We will also formulate several open problems in this area.

15. 11., 22. 11., 6. 12. 2006 (středa [Wednesday], 14:30, MÚ Žitná 25)

E. Croot: The Szemeredi Regularity Lemma (course notes)
J. Komlos, M.Simonovits: Szemeredi's regularity lemma and its applications in graph theory, in: Combinatorics, Paul Erdos is Eighty (Volume 2). Also DIMACS TR: 96-10
(referuje Martin Pergel)

Abstract: Szemeredi's Regularity Lemma is an important tool in discrete mathematics. It says that, in some sense, all graphs can be approximated by random-looking graphs. We will cover its proof from the course notes by Croot and some typical applications and generalizations from the survey by Komlos and Simonovits.

1. 11. 2006 (středa [Wednesday], 14:30, MÚ Žitná 25)

N. Alon, N. Duffield, C. Lund, and M. Thorup. Estimating sums of arbitrary selections with few probes. PODS'05.
(referuje Tomáš Ebenlendr)

Abstract: Suppose we have a large table T of items i, each with a weight w_i, e.g., people and their salary. In a general preprocessing step for estimating arbitrary subset sums, we assign each item a random priority depending on its weight. Suppose we want to estimate the sum of an arbitrary subset I \subset T. For any q>2, considering only the q highest priority items from I, we obtain an unbiased estimator of the sum whose relative standard deviation is O(1/sqrt{q}). Thus to get an expected approximation factor of 1+-eps, it suffices to consider O(1/eps^2) items from I. Our estimator needs no knowledge of the number of items in the subset I, but we can also estimate that number if we want to estimate averages.
The above scheme performs the same role as the on-line aggregation of Hellerstein et al. (SIGMOD'97) but it has the advantage of having expected good performance for any possible sequence of weights. In particular, the performance does not deteriorate in the common case of heavy-tailed weight distributions. This point is illustrated experimentally both with real and synthetic data.
We will also show that our approach can be used to improve Cohen's size estimation framework (FOCS'94).

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

18. 10. 2006 (středa [Wednesday], 14:30, MÚ Žitná 25)

Noga Alon, Oded Schwartz, Asaf Shapira:
An elementary construction of constant-degree expanders. SODA'07. Also ECCC TR06-119.
(referuje Ondřej Zajíček)

Abstract: We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by Reingold, Vadhan, and Wigderson to give an iterative construction of bounded-degree expanders. Here we give a simpler construction, which applies the replacement product (only twice!) to turn the Cayley expanders of Alon and Roichman, whose degree is polylog n, into constant degree expanders. This enables us to prove the required expansion using a new simple combinatorial analysis of the replacement product (instead of the spectral analysis used in Reingold, Vadhan, and Wigderson).

11. 10. 2006 (středa [Wednesday], 14:30, MÚ Žitná 25)

A. Chattopadhyay, N. Goyal, P. Pudlak, D. Therien:
Lower bounds for circuits with MOD_m gates. FOCS'06
(referuje Pavel Pudlák)

Abstract: Circuits in which all gates are MOD_m need \Omega(n) gates to compute MOD_q, when m and q are co-prime. Our argument is based on a new theorem about the boolean solutions of systems of linear equations over Z_m. We shall also show some applications of this lower bound to other types of circuits.