Loading Events

Upcoming Events › Seminar Events

Events Search and Views Navigation

Event Views Navigation

September 2019

Vijay Vazirani – Matching is as Easy as the Decision Problem, in the NC Model

September 23 @ 3:30 pm - 4:30 pm
George B. Dantzig Auditorium – 1174 Etcheverry Hall, Etcheverry Hall
Berkeley, CA 94720 United States
+ Google Map

Abstract: Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching algorithms. Over the last five years, the TCS community has launched a relentless attack on this question, leading to the discovery of numerous powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a…

Find out more »

October 2019

Shane Henderson – Under the Hood of Bike Sharing

October 7 @ 3:30 pm - 4:30 pm
George B. Dantzig Auditorium – 1174 Etcheverry Hall, Etcheverry Hall
Berkeley, CA 94720 United States
+ Google Map

Joint work with Daniel Freund, Nanjing Jian, Eoin O’Mahony, David Shmoys Cornell’s work on bike sharing with Citi Bike and its parent company Motivate relies on a combination of data analysis, stochastic modeling and optimization to help inform both the design and operation of the largest bike-sharing operations in North America. I’ll discuss our work and its impact, but focus on some of the inner workings of the stochastic modeling. This includes the use of (one of) the Poisson equation(s)…

Find out more »

Ziv Scully – SOAP: One Clean Analysis of All Age-Based Scheduling Policies

October 14 @ 3:30 pm - 4:30 pm
George B. Dantzig Auditorium – 1174 Etcheverry Hall, Etcheverry Hall
Berkeley, CA 94720 United States
+ Google Map

Abstract: Scheduling policies are at the heart of computer systems. The right scheduling policy can dramatically reduce response times, ensure fairness, provide class-based priority, etc., without requiring additional resources. While stochastic response time analysis (e.g. in the M/G/1 queueing model) of different scheduling policies has been the focus of many theoretical papers, results are limited to analyzing a relatively small number of simple scheduling policies, such as first-come, first served (FCFS) and shortest remaining processing time (SRPT), with each requiring…

Find out more »

Karthik Natarajan — Exploiting Partial Correlations in Distributionally Robust Optimization

October 16 @ 3:00 pm - 4:00 pm
3108 Etcheverry Hall

Abstract: In this work, we identify partial correlation information structures that allow for simpler reformulations in evaluating the maximum expected value of mixed integer linear programs with random objective coefficients. To this end, assuming only the knowledge of the mean and the covariance matrix entries restricted to block-diagonal patterns, we develop a reduced semidefinite programming formulation, the complexity of solving which is related to characterizing a suitable projection of the convex hull of the set {(x, xx' ) : x ∈…

Find out more »
+ Export Events