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.

Pages