LZI - Schloss Dagstuhl - Talks + Materials of Seminar 11121

Seminar 11121
Computational Complexity of Discrete Problems

Martin Grohe (HU Berlin, DE), Michal Koucký (Academy of Sciences - Prague, CZ), Rüdiger Reischuk (Universität Lübeck, DE), Dieter van Melkebeek (University of Wisconsin - Madison, US)

Caveat: Due to caching problems of dynamic webpages, sometimes newly
uploaded files are not shown. Please reload the page accordingly.


Seminar Wide Materials

Eric Allender , Rutgers University - Piscataway
 Limits on the Computational Power of Random Strings
Abstracts: txt Paper: pdf


Matthew Anderson , University of Wisconsin - Madison

Paul Beame , University of Washington - Seattle
 How well do AC^0 Circuits Approximate Parity? Approximating AC^0 by 'smal
Abstracts: txt


Eli Ben-Sasson , Technion - Haifa
 From affine to two-source extractors via approximate duality
Abstracts: txt Slides: pdf


Markus Blaeser , Universität des Saarlandes
 Randomness efficient testing of sparse blackbox polynomial identities of unbounded degree over the reals
Abstracts: txt Slides: pdf


Andrej Bogdanov , Chinese University of Hong Kong

Beate Bollig , Technische Universität Dortmund
 Randomized OBDDs for the most significant bit of multiplication need exponential size
Abstracts: txt Slides: pdf


Holger Dell , HU Berlin

Martin Dietzfelbinger , TU Ilmenau

Andrew Drucker , MIT - Cambridge
 Probabilistically Checkable Debates of Nearly-Linear Size
Abstracts: txt


Michael Elberfeld , Universität Lübeck
 Algorithmic Meta Theorems Inside Logspace and Their Applications
Abstracts: txt Slides: pdf


Eldar Fischer , Technion - Haifa
 Testing assignments for satisfying a monotone formula
Abstracts: txt


Lance Fortnow , Northwestern University - Evanston

Anna Gal , University of Texas - Austin
 The Size and Depth of Layered Boolean Circuits
Abstracts: txt


Martin Grohe , HU Berlin

Kristoffer Arnsfelt Hansen , Aarhus University
 Learning Read-Constant Polynomials of Constant Degree Modulo Composites
Abstracts: txt


Prahladh Harsha , TIFR Mumbai
 A survey of recent advances in threshold functions
Abstracts: txt Slides: pptx

 Bounding the average and noise sensitivity of polynomial threshold functions
Abstracts: txt Slides: pdf


Johan Hastad , KTH Stockholm

Stasys Jukna , Universität Frankfurt am Main

Valentine Kabanets , Simon Fraser University - Burnaby

Michal Koucky , Academy of Sciences - Prague

Matthias Krause , Universität Mannheim
 On the Preimage Resistance of Blockcipher-Based Cryptographic Hash Functions
Abstracts: txt


Troy Lee , National University of Singapore

Xin Li , University of Texas - Austin
 Improved Constructons of Three Source Extractors
Abstracts: txt


Meena Mahajan , The Institute of Mathematical Sciences - Chennai
 Counting Classes and the Fine Structure between NC^1 and DLOG
Abstracts: txt Slides: pdf


Pierre McKenzie , Université de Montréal

Or Meir , Weizmann Institute - Rehovot
 IP = PSPACE using Error Correcting Codes
Abstracts: txt Slides: pdf Paper: pdf


Peter Bro Miltersen , Aarhus University

Robin Moser , ETH Zürich

Ilan Newman , University of Haifa
 Triangular rank and sampling with multiplicative errors
Abstracts: txt


Jakob Nordstroem , KTH Stockholm
 On the Semantics of Local Characterizations for Linear-Invariant Properties
Abstracts: txt Slides: pdf


Pavel Pudlak , Czech Academy of Sciences
 Pseudorandom generators for group products
Slides: pdf


Oded Regev , Tel Aviv University
 Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication
Abstracts: txt

 An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
Abstracts: txt


Ruediger Reischuk , Universität Lübeck

Rahul Santhanam , University of Edinburgh

Georg Schnitger , Universität Frankfurt am Main

Uwe Schoening , Universität Ulm

Nicole Schweikardt , Universität Frankfurt am Main
 Locality of AC^0-computable graph queries
Abstracts: txt


Srikanth Srinivasan , Institute for Advanced Study - Princeton

Amnon Ta-Shma , Tel Aviv University
 What binary codes can be obtained by concatenating AG codes with Hadamard?
Abstracts: txt Slides: pdf


Till Tantau , Universität Lübeck

Emanuele Viola , Northeastern Univ. - Boston
 Extractors for circuit sources
Abstracts: txt Slides: pdf


Heribert Vollmer , Leibniz Universität Hannover

Fabian Wagner , Universität Ulm
 Isomorphism and Canonization of Bounded Treewidth Graphs
Abstracts: txt


Thomas W. Watson , University of California - Berkeley
 Pseudorandom Generators for Combinatorial Checkerboards
Abstracts: txt


Philipp Woelfel , University of Calgary

Dieter van Melkebeek , University of Wisconsin - Madison


Creative Commons License
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: