Program Committee


Chandra Chekuri
Uriel Feige
Pierre Fraigniaud
Magnús M. Halldórsson
Christos Kaklamanis
Anna Karlin
Samir Khuller
Guy Kortsarz
Monaldo Mastrolilli
Claire Mathieu
Zeev Nutov
Giuseppe Persiano
Maria Serna (chair)
Martin Skutella
Maxim Sviridenko
David P. Williamson


Dimitris Achlioptas
Alexandr Andoni
Anna Gal
Valentine Kabanets
Swastik Kopparty
Michael Krivelevich
Sofya Raskhodnikova
Ran Raz
Atri Rudra
Rocco Servedio
Ronen Shaltiel (chair)
Angelika Steger
Christopher Umans
Eric Vigoda
Sergey Yekhanin

Program Chairs

Maria Serna,
Universitat Politècnica de Catalunya

Ronen Shaltiel,
University of Haifa

Workshop Chairs

Klaus Jansen,
U. of Kiel

José Rolim,
U. of Geneva

Local Chairs

Maria Blesa,
Universitat Politècnica de Catalunya
Maria Serna,
Universitat Politècnica de Catalunya
Important dates
Submission deadline
April 18 , 2010

Notification to authors
June 12 , 2010

Camera ready
June 23 , 2010

1-3 September 2010
Call for papers

Leslie Ann Goldberg, University of Liverpool

Approximating the Tutte polynomial of a graph

Download the talk abstract here.


Oded Goldreich

Some Thoughts regarding Unconditional Derandomization

ABSTRACT: Asked to replace Luca Trevisan at the last moment, I will focus the talk on the little that I know, and will end by offering some wild speculations (rather than open problems).

The pivot of my talk will be a recent result [ECCC, TR10-135] that asserts that proving derandomization results such as BPP=P essentially necessitate the construction of suitable pseudorandom generators (i.e., generators that suffice for such derandomization results). In particular, the main incarnation of this equivalence refers to the standard notion of uniform derandomization and to the corresponding notion of pseudorandom generators (i.e., the standard uniform notion of ``canonical derandomizers'').