Navigation

Program Committee




APPROX

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

RANDOM

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


APPROX
Maria Serna,
Universitat Politècnica de Catalunya
email:
mjserna@lsi.upc.edu

RANDOM
Ronen Shaltiel,
University of Haifa
email:
ronen@cs.haifa.ac.il

Workshop Chairs


Klaus Jansen,
U. of Kiel
e-mail: kj@informatik.uni-kiel.de

José Rolim,
U. of Geneva
e-mail: jose.rolim@unige.ch

Local Chairs


Maria Blesa,
Universitat Politècnica de Catalunya
email:
mjblesa@lsi.upc.edu
Maria Serna,
Universitat Politècnica de Catalunya
email:
mjserna@lsi.upc.edu
Important dates
Submission deadline
April 18 , 2010

Notification to authors
June 12 , 2010

Camera ready
June 23 , 2010

Conference
1-3 September 2010
Call for papers
PDF Format

Plain Text

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'').