Algorithms and Complexity Seminars
 |
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. |
|
|
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. |
|
|
Dylan Foster:Online Learning, Probabilistic Inequalities, and the Burkholder Method Wednesday, October 17, 2018 - 3:00pm to 4:00pm |
Pages
