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
node has one of two opinions and updates its opinion as a ``majority-like"
function of the frequency of opinions among its neighbors. The networks we

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


Subscribe to Algorithms and Complexity Seminars