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

Registration is required to attend this workshop. Space may be limited, and you are advised to register early. The link to the registration form will appear on this page approximately 10 weeks before the workshop. To submit your name for consideration, please register and await confirmation of your acceptance before booking your travel.