LZI - Schloss Dagstuhl - Talks + Materials of Seminar 08381

Collector buttons:

Seminar 08381
Computational Complexity of Discrete Problems

Peter Bro Miltersen (Univ. of Aarhus, DK), Rüdiger Reischuk (Universität Lübeck, D), Georg Schnitger (Universität Frankfurt, D), Dieter van Melkebeek (University of Wisconsin - Madison, USA)

Seminar Wide Materials

Talk Schedule

Other:

Map of Hike

Slides:

	Upload or overwrite a document file and/or change title of talk


	Due to caching problems of microsofts internet explorer concerning dynamic webpages, sometimes newly uploaded files are not shown. By pressing [CTRL]+[F5], the page is completely reloaded.

Eric Allender , Rutgers Univ. - Piscataway

Eli Ben-Sasson , Technion - Haifa

Univariate solutions for low-degree multivariate problems

Abstracts:

Markus Bläser , Saarland University

Randomness efficient zero testing of blackbox polynomials

Abstracts:

Beate Bollig , Technische Universität Dortmund

On the OBDD complexity of the most significant bit of integer multiplication

Abstracts:

Slides:

Mark Braverman , Microsoft Research NE

The complexity of simulating Brownian Motion

Abstracts:

Harry Buhrman , CWI - Amsterdam

Martin Dietzfelbinger , TU Ilmenau

Tight bounds for blind search on the integers

Abstracts:

Slides:

Lance Fortnow , Northwestern - Evanston

Program Equilibria and Discounted Computation Time

Abstracts:

Slides:

Martin Grohe , HU Berlin

Descriptive Complexity and Graphs with Excluded Minors

Abstracts:

Slides:

Venkatesan Guruswami , University of Washington

Beating the random ordering is hard

Abstracts:

Anna Gál , Univ. of Texas at Austin

Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence

Abstracts:

Kristoffer Arnsfelt Hansen , Univ. of Aarhus

Depth Reduction for Circuits with a Single Layer of Modular Counting Gates

Abstracts:

DROPS-Submission:

Johan Hastad , KTH Stockholm

Some results on approximation resistance

Abstracts:

Thomas Holenstein , Microsoft - Mountain View

On Parallel Repetition

Abstracts:

Slides:

Stasys Jukna , Universität Frankfurt

Entropy of Operators or Nechiporuk for Depth-2 Circuits

Abstracts:

Slides:

Paper:

Valentine Kabanets , Simon Fraser University - Burnaby

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized

Abstracts:

Michal Koucký , Academy of Sciences - Prague

Amplifying Lower Bounds by Means of Self-Reducibility - Part 2

Abstracts:

Matthias Krause , Universität Mannheim

Miroslaw Kutylowski , Wroclaw University of Technology

Traffic Analysis and Complexity of Anonymous Communication

Abstracts:

Slides:

Hidden Subset Identifiers

Abstracts:

Slides:

Troy Lee , Rutgers Univ. - Piscataway

Approximation norms and duality for communication complexity lower bounds

Abstracts:

DROPS-Submission:

Approximation norms, duality, and communication complexity lower bounds

Slides:

Peter Bro Miltersen , Univ. of Aarhus

Jakob Nordström , MIT - Cambridge

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

Abstracts:

Slides:

DROPS-Submission:

Pavel Pudlák , Czech Academy of Sciences

Jaikumar Radhakrishnan , TIFR Bombay

Finding duplicates in a data stream

Abstracts:

Slides:

Oded Regev , Tel Aviv University

Rounding Parallel Repetitions of Unique Games

Abstracts:

Slides:

Rüdiger Reischuk , Universität Lübeck

Universal Steganography

Abstracts:

Georg Schnitger , Universität Frankfurt

Uwe Schöning , Universität Ulm

Ronen Shaltiel , Haifa University

Unconditional weak derandomization of weak algorithms: Explicit versions of Yao's Lemma.

Abstracts:

Alexander Sherstov , University of Texas - Austin

The Pattern Matrix Method for Lower Bounds on Bounded-Error Communication

Abstracts:

DROPS-Submission:

Amir Shpilka , Technion - Haifa

Explicit construction of a small epsilon-net for linear threshold function

Abstracts:

Reconstruction of Depth-3 Arithmetic Circuits

Abstracts:

Slides:

Hans Ulrich Simon , Ruhr-Universität Bochum

Amnon Ta-Shma , Tel Aviv University

A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product

Abstracts:

Slides:

Till Tantau , Universität Lübeck

Denis Therien , McGill University - Montreal

Thomas Thierauf , Hochschule Aalen

Jacobo Toran , Universität Ulm

Christopher Umans , CalTech - Pasadena

Fast polynomial factorization and modular composition

Abstracts:

DROPS-Submission:

Stephan Waack , Universität Göttingen

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

Abstracts:

Philipp Woelfel , University of Calgary

Separating Deterministic from Randomized Multiparty Communication Complexity

Abstracts:

Slides:

Dieter van Melkebeek , University of Wisconsin - Madison

Copyright

This webpage and the material that is made available on this webpage is licensed under a
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.

The CC by-nc-nd license allows you to copy, distribute and transmit the work under the following conditions:

Attribution: You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).
Noncommercial: You may not use this work for commercial purposes.
No Derivative Works: You may not alter, transform, or build upon this work.

Seminar 08381 Computational Complexity of Discrete Problems

Copyright

Seminar 08381
Computational Complexity of Discrete Problems