Rounding Dynamic Matchings Against an Adaptive Adversary Wednesday, February 24, 2021  4:00pm to 5:00pm Abstract: Dynamic algorithms address dynamicallyevolving datasets, and show how to maintain solutions to problems of interest subject to small updates to the input, much faster than recomputing these solutions from scratch after each update. 

Sampling Sketches for Concave Sublinear Functions of Frequencies Wednesday, May 15, 2019  4:00pm to 5:00pm We consider massive distributed datasets that consist of elements that are keyvalue pairs. 

LearningDriven Algorithms for Discrete Optimization Tuesday, April 30, 2019  4:00pm to 5:00pm This talk focuses on a novel fruitful synergy between machine learning and optimization  in particular, how ML techniques can improve the design of algorithms for Discrete Optimization, both complete algorithms such as branch and bound as well as incomplete ones such 

Greg Yang: Batch Normalization Causes Gradient Explosion in Deep Randomly Initialized Networks Wednesday, May 1, 2019  4:00pm to 5:00pm


Static Data Structure Lower Bounds Imply Rigidity Wednesday, April 17, 2019  4:00pm to 5:00pm We show that static data structure lower bounds in the group (linear) model imply semiexplicit lower bounds on matrix rigidity. 

Decremental StronglyConnected Components and SingleSource Reachability in NearLinear Time Wednesday, March 6, 2019  4:00pm to 5:00pm Abstract: Computing the StronglyConnected Components (SCCs) in a graph G=(V,E) is known to take only O(m + n) time using an algorithm by Tarjan from 1972[SICOMP 72] where m = E, n=V. 

Opinion formation, stochastic gradient descent, and gradientlike systems Wednesday, February 27, 2019  4:00pm to 5:00pm We study opinion dynamics on networks with two communities. Each 

NearOptimal Pseudorandom Generators for ConstantDepth ReadOnce Formulas Wednesday, December 12, 2018  4:00pm to 5:00pm We give an explicit nearlyoptimal pseudorandom generator (PRG) for constantdepth readonce formulas. Previously, PRGs with nearoptimal seed length were known only for the depth2 case by Gopalan et al.. 

Nima Anari:LogConcave Polynomials and Matroids: Algorithms and Combinatorics Wednesday, October 24, 2018  4:00pm to 5:00pm Abstract: I will discuss an analytic property of multivariate polynomials, which we call complete logconcavity, and its surprising uses to attack problems in combinatorics, and algorithmic tasks such as sampling, counting, and inference on discrete distributions. 

Dylan Foster:Online Learning, Probabilistic Inequalities, and the Burkholder Method Wednesday, October 17, 2018  3:00pm to 4:00pm 