Spring 2016

Random Instances and Phase Transitions

May 2May 6, 2016

Add to Calendar


Andrei Bulatov (Simon Fraser University; chair), Amin Coja-Oghlan (Goethe University Frankfurt am Main), Alan Frieze (Carnegie Mellon University), Mike Molloy (University of Toronto), Andrea Montanari (Stanford University)

Randomly generated problems have been studied since Erdős and Rényi. They originally attracted interest in computational complexity as a way to study the "average case" complexity of hard combinatorial problems. More recently, however, research has centered on the combinatorial "phase transitions" exhibited by such models. These strongly resemble phase transitions in statistical physics, and have proved to be a useful tool for determining thresholds in computational complexity. A particular area of application has been random constraint satisfaction problems, where physical intuition has led to a deeper understanding and, in some cases, rigorous proofs.

All talks will be recorded. Enquiries may be sent to the organizers workshop_counting3 [at] lists [dot] simons [dot] berkeley [dot] edu (at this address.)

Invited Participants: 

Dimitris Achlioptas (UC Santa Cruz), David Aldous (UC Berkeley), Nayantara Bhatnagar (University of Delaware), Michele Borassi (IMT Institute for Advanced Studies), Cornelius Brand (Saarland University), Raimundo Briceño (University of British Columbia), Andrei Bulatov (Simon Fraser Universeity), Peter Bürgisser (Technische Universität Berlin), Jin-Yi Cai (University of Wisconsin-Madison), Sourav Chatterjee (Stanford University), Xi Chen (Columbia University), Amin Coja-Oghlan (Goethe University Frankfurt am Main),  Radu Curticapean (Universität des Saarlandes), Artur Czumaj (University of Warwick),  Victor Dalmau (Universitat Pompeu Fabra), Varsha Dani (University of New Mexico), Holger Dell (Universität des Saarlandes), Amir Dembo (Stanford University), Persi Diaconis (Stanford University), Martin Dyer (University of Leeds), Charis Efthymiou (Georgia Tech), Funda Ergun (Indiana University), Laura Florescu (NYU), Fedor Fomin (University of Bergen), Peter Fulla (University of Oxford), Marylou Gabrié (École Normale Supérieure Paris), Andreas Galanis (University of Oxford), David Gamarnik (Massachusetts Institute of Technology), Leslie Ann Goldberg (University of Oxford), Catherine Greenhill (University of New South Wales), Heng Guo (Queen Mary, University of London), Mor Harchol-Balter (Carnegie Mellon University), Tom Hayes (University of New Mexico), Pavol Hell (Simon Fraser University), Tyler Helmuth (UC Berkeley), Miki Hermann (Ecole Polytechnique), Steve Homer (Boston University), Mark Jerrum (Queen Mary, University of London), Mihyun Kang (TU Graz), Ravi Kannan (Microsoft Research India), Florent Krzakala (École Normale Supérieure Paris), John Lapinskas (University of Oxford), Marc LeLarge (INRIA), Pinyan Lu (Shanghai University of Finance and Economics), Nicolas Macris (EPFL), Janos Makowsky (Technion-Israel Institute of Technology), Ankur Moitra (MIT), Brian Marcus (University of British Columbia), Mike Molloy (University of Toronto), Andrea Montanari (Stanford University), Cris Moore (Santa Fe Institute), Elchanan Mossel (University of Pennsylvania and UC Berkeley), Emanuele Natale (Sapienza University of Rome), Dmitriy Panchenko (University of Toronto), Prasad Raghavendra (UC Berkeley), Dana Randall (Georgia Institute of Technology), Federico Ricci-Tersenghi (Sapienza University of Rome), David Richerby (University of Oxford), Marc Roth (Universität des Saarlandes), Guilhem Semerjian (Ecole Normale Superieure), Alistair Sinclair (UC Berkeley), Allan Sly (UC Berkeley), Daniel Stefankovic (University of Rochester), David Steurer (Cornell University), Nike Sun (Massachusetts Institute of Technology), Prasad Tetali (Georgia Institute of Technology), Rudi Urbanke (EPFL), Eric Vigoda (Georgia Institute of Technology), Lutz Warnke (University of Cambridge), Mingji Xia (Institute of Software, Chinese Academy of Sciences), Jiaming Xu (University of Pennsylvania), Yitong Yin (Nanjing University), Lenka Zdeborova (Institut de Physique Théorique), Riccardo Zecchina (Politecnico di Torino), Chihao Zhang (Shanghai Jiao Tong University), Stanislav Zivny (University of Oxford)