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.

Walking Randomly, Massively, and Efficiently
Monday, November 4, 2019 - 4:00pm to 5:00pm

We introduce an approach that allows for efficiently generating many
independent random walks in big graph models, such as the Massive
Parallel Computation (MPC) model. We consider the case where the space per

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.


Subscribe to Algorithms and Complexity Seminars