Program Committee


Anna Adamaszek (Copenhagen)
Shiri Chechik (Tel Aviv)
Anne Driemel (TUE)
Lee-Ad Gottlieb (Ariel)
Varun Kanade (Oxford)
Nitish Korula (Google)
Stefano Leonardi (Sapienza)
Daniel Lokshtanov (Bergen)
Claire Mathieu (ENS Paris, chair)
Nicole Megow (TUM)
Tobias Moemke (Saarland)
Shayan Oveis Gharan (Washington)
Debmalya Panigrahi (Duke)
Richard Peng (Georgia Tech)
Ely Porat (Bar-Ilan)
Adi Rosén (CNRS & Paris 7)
Adrian Vetta (McGill)
Rico Zenklusen (ETH Zurich)


Mahdi Cheraghchi (Imperial College, London)
Elena Grigorescu (Purdue)
Neeraj Kayal (MSR Bangalore)
Adam Klivans (Austin)
Swastik Kopparty (Rutgers)
Ravi Kumar (Google)
Dana Moshkovitz (MIT)
Ashwin Nayak (Waterloo)
Ryan O'Donnell (CMU)
Asaf Shapira (Tel Aviv)
Ronen Shaltiel (Haifa)
Alexander Sherstov (UCLA)
Thomas Thierauf (Aalen)
Chris Umans (Caltech, chair)
Eric Vigoda (Georgia Tech)

Program Chairs

Claire Mathieu
CNRS and École Normale Supérieure Paris

Chris Umans

Workshop Chairs

José Rolim,
U. of Geneva
Klaus Jansen,
U. of Kiel

Local Organisation

Sophie Laplante
Frédéric Magniez
Marc Renault
Adi Rosén, chair                                            

Important dates
Submission deadline
Tues, April 19, 2016
15:00 PDT

Notification to authors
By June 22, 2016

Camera ready
July 1, 2016

Sept 7-9, 2016
Call for papers


Université Paris Diderot - Paris 7



Invited Talks

RANDOM Invited Speaker: Antoine Joux, UPMC

Technical History of Discrete Logarithms in Small Characteristic Finite Fields

Due to its use in cryptographic protocols such as the Diffie-Hellman key exchange, the discrete logarithm problem attracted a considerable amount of attention in the past 40 years. In this talk, we summarize the key technical ideas and their evolution for the case of discrete logarithms in small characteristic finite fields. This road leads from the original belief that this problem was hard enough for cryptographic purpose to the current state of the art where the algorithms are so efficient and practical that the problem can no longer be considered for cryptographic use.

APPROX Invited Speaker: Valerie King, University of Victoria

Tossing a Collective Coin and Coming to Agreement

Over 35 years ago, Leslie Lamport formulated a fundamental problem of coordination in a distributed network. He asked us to imagine an army led by generals, who send messages to each other with the goal of coming to agreement on a strategy. Planted among those generals are spies who seek to thwart this goal. Not long after this Byzantine agreement problem was presented, there were a few developments: an impossibility result for any deterministic scheme, a randomized exponential time algorithm, and a demonstration that one globally known coin toss could solve the problem in constant expected time.

Some researchers turned to the use of committed secret coinflips via cryptography, while others turned to the study of collective coin flipping with full information. Recently, interest in efficient Byzantine agreement has arisen in the context of decentralized digital currency systems.

I will describe joint work with Jared Said and others on efficient algorithms for Byzantine agreement, including the first polynomial expected time algorithm for this problem in a fully asynchronous model where the adversary has full information, which is obtained by solving a new collective coin flipping problem.

Valid XHTML 1.0 Transitional Valid CSS!

Created by Marios Karagiannis - Maintained by Marc Renault and Orestis Evangelatos