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)
Michal Koucký: High Entropy Random Selection Protocols18. 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.