![]() |
Rounding Dynamic Matchings Against an Adaptive Adversary Wednesday, February 24, 2021 - 4:00pm to 5:00pm Abstract: Dynamic algorithms address dynamically-evolving datasets, and show how to maintain solutions to problems of interest subject to small updates to the input, much faster than re-computing these solutions from scratch after each update. |
![]() |
Walking Randomly, Massively, and Efficiently Monday, November 4, 2019 - 4:00pm to 5:00pm We introduce an approach that allows for efficiently generating many |
![]() |
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 key-value pairs. |
![]() |
Learning-Driven 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 Strongly-Connected Components and Single-Source Reachability in Near-Linear Time Wednesday, March 6, 2019 - 4:00pm to 5:00pm Abstract: Computing the Strongly-Connected 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 gradient-like systems Wednesday, February 27, 2019 - 4:00pm to 5:00pm We study opinion dynamics on networks with two communities. Each |
![]() |
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas Wednesday, December 12, 2018 - 4:00pm to 5:00pm We give an explicit nearly-optimal pseudorandom generator (PRG) for constant-depth read-once formulas. Previously, PRGs with near-optimal seed length were known only for the depth-2 case by Gopalan et al.. |
![]() |
Nima Anari:Log-Concave 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 log-concavity, and its surprising uses to attack problems in combinatorics, and algorithmic tasks such as sampling, counting, and inference on discrete distributions. |