Dagstuhl Seminar 08381
Computational Complexity of Discrete Problems
September 14-19, 2008

                            Talk Schedule
                           ===============

The regular sessions are from 09.00 till 12.00 and from 15.30 till 18.00.
Wednesday afternoon is reserved for a hike. The program ends Friday at noon.


Monday morning:

  09.00: Welcome and introductions

  09.45: Thomas Holenstein
         Parallel repetition: overview and the theorem

  10.25: break

  10.40: Oded Regev
         Rounding parallel repetitions of unique games

  11.30: Venkat Guruswami
         Beating the random ordering is hard


Monday afternoon:
 
  15.30: Eli Ben-Sasson
         Univariate solutions for low-degree multivariate problems

  16.30: break

  16.45: Chris Umans
         Fast polynomial factorization and modular composition

  17.25: Beate Bollig
         On the OBDD complexity of the most significant bit of 
         integer multiplication


Tuesday morning:

  09.00: Ronen Shaltiel
         Unconditional weak derandomization of weak algorithms: 
         explicit versions of Yao's lemma

  09.45: Jaikumar Radhakrishnan
         Finding duplicates in a data stream

  10.25: break

  10.40: Amir Shpilka
         Explicit construction of a small epsilon-net for 
         linear threshold function

  11.20: Amnon Ta-Shma
         A combinatorial construction of almost-Ramanujan graphs 
         using the zig-zag product


Tuesday afternoon:

  15.30: Valentine Kabanets
         Uniform direct product theorems: simplified, optimized, and 
         derandomized

  16.20: break

  16.35: Mark Braverman
         The complexity of simulating Brownian motion

  17:05: Markus Blaeser
         Randomness efficient zero testing of blackbox polynomials

  17.35: Open problem session


Wednesday morning:

  09.00: Sasha Sherstov
         The pattern matrix method for lower bounds on 
         bounded-error communication

  09.40: Philipp Woelfel
         Separating deterministic from randomized multiparty communication

  10.20: break

  10.35: Troy Lee
         Norms and duality for communication complexity
         lower bounds

  11.20: Anna Gal
         Lower bounds on streaming algorithms for
         approximating the length of the longest increasing subsequence


Thursday morning:

  09.00: Martin Grohe
         Descriptive complexity and graphs with excluded minors

  09.45: Jakob Nordstroem
         Understanding space in resolution: 
         optimal lower bounds and exponential trade-offs

  10.25: break

  10.40: Stasys Jukna
         Entropy of operators or Nechiporuk for depth-2 circuits

  11.15: Kristoffer Arnsfelt Hansen
         Depth reduction for circuits with a single layer of modular
         counting gates

  11.35: Michal Koucky
         Amplifying lower bounds by means of self-reducibility


Thursday afternoon:

  15.30: Miroslaw Kutylowski
         Traffic analysis and complexity of anonymous communication

  16.00: Ruediger Reischuk
         Universal steganography

  16.40: break

  16.55: Martin Dietzfelbinger
         Tight bounds for blind search on the integers

  17.25: Lance Fortnow
         Program equilibria and discounted computation time


Friday morning:

  09.15: Johan Hastad
         Some results on approximation resistance

  09.45: Stephan Waack
         A generalization of the classification noise model of PAC learning
         and its applications to protein-protein interaction

  10.15: break

  10.30: Amir Shpilka
         Reconstruction of depth-3 arithmetic circuits

  11.15: concluding discussion