Spring 2019

Beyond Randomized Rounding and the Probabilistic Method

Feb. 11Feb. 15, 2019

Add to Calendar


Shayan Oveis Gharan (University of Washington; chair), Nikhil Srivastava (UC Berkeley)

Several results in algorithms and combinatorics are obtained by the probabilistic method: one analyzes a random structure and shows that it has the desired properties with nonzero probability. This workshop will focus on recently developed techniques based on the geometry of polynomials (for instance, the method of interlacing families of polynomials), which are sometimes able to beat traditional probabilistic analyses and establish the existence of rare objects that were previously out of reach. We will also have talks on nearby topics, such as discrepancy theory, approximation algorithms and high dimensional combinatorics, with the goal of finding new applications of these techniques.

Further details about this workshop will be posted in due course. Enquiries may be sent to the organizers workshop-geometry1 [at] lists [dot] simons [dot] berkeley [dot] edu (at this address).

All events take place in the Calvin Lab auditorium.

Registration is required to attend this workshop. To submit your name for consideration, please register and await confirmation of your acceptance to the workshop before booking your travel. Space may be limited, and you are advised to register early.

Invited Participants: 

Nima Anari (Stanford University), Federico Ardila (San Francisco State University), Nikhil Bansal (Eindhoven University of Technology), Benoit Collins (Kyoto University), June Huh (IAS), Rasmus Kyng (Harvard University), Kuikui Liu (University of Washington), Ryan O'Donnell (Carnegie Mellon University), Izhar Oppenheim (Ben-Gurion University), Yuval Peled (Hebrew University), Peter Sarnak (IAS)