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.

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: 

Karim Adiprasito (Hebrew University of Jerusalem), Nima Anari (Stanford University), Federico Ardila (San Francisco State University), Octavio Arizmendi (CIMAT), Nikhil Bansal (Eindhoven University of Technology), Benoit Collins (Kyoto University), Olga Holtz (UC Berkeley and Technische Universität Berlin), June Huh (IAS), Stefanie Jegelka (Massachusetts Institute of Technology), Tali Kaufman (Bar-Ilan University), Rasmus Kyng (Harvard University), Jonathan Leake (UC Berkeley), Kuikui Liu (University of Washington), Rafael Mendes de Oliveira (University of Toronto), Marcus Michelen (University of Pennsylvania), Ryan O'Donnell (Carnegie Mellon University), Izhar Oppenheim (Ben-Gurion University), Shayan Oveis Gharan (University of Washington), Yuval Peled (Hebrew University), Nick Ryder (UC Berkeley), Amin Saberi (Stanford University), Peter Sarnak (IAS), Mohit Singh (Georgia Institute of Technology), Cynthia Vinzant (North Carolina State University)


The workshops in the "Geometry of Polynomials" program are supported in part by the National Science Foundation under Award No. 1835986.

We are required by the NSF Proposal & Award Policies & Procedures Guide (Chapter II.E.7), effective January 28, 2019, to provide all event participants with information on the University’s policy on sexual and other forms of harassment or sexual assault as well as directions on how to report any violations of this policy. For purposes of this requirement, “other forms of harassment” is defined as “non-gender or non-sex-based harassment of individuals protected under federal civil rights laws, as set forth in organizational policies or codes of conduct, statutes, regulations, or executive orders.” This information is available here.