LZI - Schloss Dagstuhl - Talks + Materials of Seminar 11121
 Functions: 

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
 



License

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: