Events for 20232024.

Nov 6
Michael Mitzenmacher (Klaus 1116, 11am)
Klaus 1116
ARC Colloquium: Algorithms with Predictions
Michael Mitzenmacher (Harvard), Algorithms with Predictions
Abstract: We survey the recent introduction of and advances in algorithms that use predictions applied to the input, such as from machine learning, to circumvent worstcase analysis. We aim for algorithms that have near optimal performance when these predictions are good, but still maintain provable bounds (such as for worstcase performance) even when the predictions have large errors. We look at several examples showing how predictions can be used effectively while still allowing for theoretical guarantees, covering our own work in scheduling and Bloom filter data structures, as well as several other recent results.
Bio: Michael Mitzenmacher is a Professor of Computer Science in the School of Engineering and Applied Sciences at Harvard University. Michael has authored or coauthored over 250 conference and journal publications on a variety of topics, including algorithms for the Internet, efficient hashbased data structures, erasure and errorcorrecting codes, power laws, and compression. He is an ACM and IEEE Fellow. He has coauthored a widely used textbook on randomized algorithms and probabilistic techniques in computer science published by Cambridge University Press. 
Oct 1820
Thomas Rothvoss Lectures on Integer Programming
Special ARC Lecture Series
Part 1  Introduction to Lattices
Part 2  The Reverse Minkowski Theorem
Part 3  The Subspace Flatness Conjecture and Faster Integer Programming 
Nov 27
Jakob Moosbauer (Klaus 1116, 11am)
Klaus 1116
ARC Colloquium
talk title TBA

Nov 13
Ruoqi Shen (Klaus 1116, 11am)
Klaus 1116
ARC Colloquium
talk title TBA

Oct 30
Mitali Bafna (Klaus 1116, 11am)
Klaus 1116
ARC Colloquium
talk title TBA

Oct 23
Shyam Narayanan (Klaus 1116, 11am)
Klaus 1116
ARC Colloquium
talk title TBA

Oct 16
Rahul Ilango (Klaus 1116, 11am)
Klaus 1116
ARC Colloquium
talk title TBA

Oct 2
ARC Colloquium: June Vuong (Klaus 1116, 11am)
Klaus 1116
Tight Markov chain analysis using discrete logconcavity
Title: Tight Markov chain analysis using discrete logconcavity
Abstract:
Sampling is a fundamental task with many applications in algorithm design and in machine learning. Sampling from highdimensional discrete distributions, such as Ising models, has long been studied for its applications in statistical physics, image modeling, and neural networks, as well as its connection to complexity theory. While Markov chain Monte Carlo (MCMC) is a widely used method for sampling, many gaps remain in understanding its performance.
In this talk, I will show tight analysis for Markov chains to sample from various discrete distributions using entropic and spectral independence, which are recently developed notions of discrete logconcavity. In particular l will show the optimal mixing time of the Glauber dynamics to sample weighted independent sets of graphs, also known as the hardcore model.

Sep 25
ARC Colloquium: Lijie Chen (Berkeley); Pettit 102 at 11am
Pettit 102
Polynomial Time Pseudodeterministic Construction of Primes
Title: Polynomial Time Pseudodeterministic Construction of Primes
Abstract: A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time. We provide a positive solution to this question in the infinitelyoften regime. In more detail, we give an unconditional polynomialtime randomized algorithm B such that, for infinitely many values of n, B(1^n) outputs a canonical nbit prime p_n with high probability. More generally, we prove that for every dense property Q of strings that can be decided in polynomial time, there is an infinitelyoften pseudodeterministic polynomialtime construction of strings satisfying Q. This improves upon a subexponentialtime construction of Oliveira and Santhanam. Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardnessrandomness framework of Chen and Tell, using a variant of the ShaltielUmans generator. This talk is based on joint work with Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam.

Sep 18
ARC Colloquium: ARC Fellowship Presentations (Klaus 1116, 11am)
Klaus 1116
ARC Fellowship presentations
A special ARC colloquium featuring some of last spring's ARC Student Fellowship awardees presenting on work they did while supported by the fellowships.

Sep 14
ARC Colloquium: Zongchen Chen (Buffalo), 11am Klaus 2447
Klaus 2447
Sampling from Graphical Models via Spectral Independence
Title:
Sampling from Graphical Models via Spectral Independence
Abstract:In many scientific settings we use a statistical model to describe a highdimensional distribution over many variables. Such models are often represented as a weighted graph encoding the dependencies between different variables and are known as graphical models. Graphical models arise in a wide variety of scientific fields throughout science and engineering.
One fundamental task for graphical models is to generate random samples from the associated distribution. The Markov chain Monte Carlo (MCMC) method is one of the simplest and most popular approaches to tackle such problems. Despite the popularity of graphical models and MCMC algorithms, theoretical guarantees of their performance are not known even for some simple models. I will describe a new tool called "spectral independence" to analyze MCMC algorithms and more importantly to reveal the underlying structure behind such models. I will also discuss how these structural properties can be applied to sampling when MCMC fails and to other statistical problems like parameter learning or model fitting. 
Sep 5
ARC Colloquium: Mark Jerrum (Queen Mary)
Petit 102A
Counting vertices of integral polytopes defined by facets
ARC Colloquium 9/5/2023
11am, Petit 102
Mark Jerrum (Queen Mary)

Apr 17
ACO Alumni Lecture featuring Daniel Dadush (Centrum Wiskunde and Informatica)
Klaus 1116
Title : Interior point methods are not worse than Simplex Klaus 1116 at 11am
Interior point methods are not worse than Simplex

Apr 3
ARC Colloquium: Viswanath Nagarajan (University of Michigan)
Klaus 1116
Title: Stochastic Score Classification and Halfspace Intersection: Klaus 1116 at 11:00 AM
Title: Stochastic Score Classification and Halfspace Intersection

Mar 13
ARC Colloquium: Guy Bresler (MIT)
Title Title: Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: Klaus 1116 at 11:00 AM

Feb 24
ACO Student Seminar: Gregory Kehne (Harvard)
Online Covering: Prophets, Secretaries, and Samples  Skiles 005 at 1:00 PM

Feb 13
ARC Colloquium: Rohan Ghuge (University of Michigan)
The Power of Adaptivity for DecisionMaking under Uncertainty  Pettit 102 A&B at 2:00 PM

Jan 30
ARC Colloquium: Dylan Altschuler (NYU)
The critical window of the symmetric perceptron  Klaus 1116 at 11:00 AM

Jan 23
ARC/Neuroscience Joint Seminar: Christos Papadimitriou, Columbia University
Towards Biologically Plausible Intelligence

Jan 23
ARC Colloquium: Elizabeth Yang (Berkeley)
Testing thresholds for highdimensional random geometric graphs  Pettit Microelectronics Building 102 A&B at 3:30pm

Mar 27
ARC Colloquium: Thodoris Lykouris (MIT)
Title TBA: Klaus 1116 at 11:00 AM

Dec 5
ARC Colloquium: Brice Huang (MIT)
Algorithmic Thresholds for MultiSpecies Spin Glasses  Klaus 1116 at 11am

Oct 27
AI4OPT/ARC Joint Seminar: Dylan Foster, Microsoft Research
The Statistical Complexity of Interactive Decision Making

Oct 24
ARC Colloquium: David Wajc (Stanford)
Title TBA: Klaus 1116 at 11am

Sep 19
ARC Colloquium: Sanjeev Khanna (University of Pennsylvania)
On Regularity Lemma and Barriers in Streaming and Dynamic Matching  Klaus 1116 at 11am

Nov 10
ARCACO Lecture Series: featuring Robert E. Tarjan (Princeton)
Title: TBA

Sep 12
ARC Colloquium: Yuansi Chen (Duke University)
Localization schemes: A framework for proving mixing bounds for Markov chains  Klaus 1116 at 11am

Aug 29
ARC Colloquium: Jan van den Brand (Georgia Tech)
Fully Dynamic stDistances  Klaus 1116 at 11am

Oct 3
ARC Colloquium: Sinho Chewi (MIT)
Title TBA: Klaus 1116 at 11am

Oct 10
ARC Colloquium: Debmalya Panigrahi (Duke University)
Title TBA: Klaus 1116 at 11am

Sep 26
ARC Colloquium: Rekha R. Thomas (University of Washington)
Graphical Designs  Klaus 1116 at 11am

Apr 11
ARC Colloquium: Chandra Chekuri (Univ. of Illinois)
Densest Subgraph: Supermodularity, Iterative Peeling, and Flow  Klaus 1116 East at 11am

Mar 14
ARC Colloquium: Yang Liu (Stanford)
Maximum Flow and MinimumCost Flow in AlmostLinear Time  Klaus 1116 East at 11am

Feb 28
ARC Colloquium: Alex Wein (Georgia Tech)
Statistical and Computational Phase Transitions in Group Testing  Klaus 1116 at 11am

Feb 21
ARC Colloquium: Nikhil Bansal (Univ. of Michigan)
More on the power of two choices in balls and bins  Klaus 1116 at 11am

Feb 7
ARC Colloquium: Manolis Vlatakis (Columbia)
Building Optimization beyond Minimization: A Journey in Game Dynamics  Virtual via BlueJeans at 11am

Feb 15
ARCACO Lecture Series: featuring Pravesh Kothari (CMU)
HighDimensional Statistical Estimation via SumofSquares  Groseclose 402 11:00AM

Feb 11
ARC Colloquium: Kiran Shiragur (Stanford)
Efficient universal estimators for symmetric property estimation Virtual via Bluejeans

Feb 14
ARC Colloquium:David Gamarnik (MIT)
Overlap gap property: A topological barrier to optimizing over random structures  Klaus 1116 at 11am

Jan 28
ARC Colloquium: Bento Natura (LSE)
Fast Exact Solvers for Linear Programs via Interior Point Methods  Virtual via BlueJeans at 11:00am

Feb 4
ARC Colloquium/ACO Student Seminar: Ziv Scully (CMU)
A New Toolbox for Scheduling Theory  Virtual via BlueJeans at 1:00pm

Jan 31
ARC Colloquium: Ainesh Bakshi (CMU)
Analytic Techniques for Robust Algorithm Design  Virtual via BlueJeans at 11am

Jan 10
CANCELLED: ARC Colloquium: Divyarthi Mohan (Tel Aviv University)
Simplicity and Optimality in MultiItem Auctions  Klaus 1116 at 11am

Nov 15
ThinkTankTalk: Nick Sahinidis (Georgia Tech)
Open problems in protein folding and other molecular challenges  Klaus 1116 at 11am

Nov 8
ARC Colloquium: Kamesh Munagala (Duke University)
Group Fairness in Network Design and Combinatorial Optimization  Groseclose 402 at 11am

Oct 25
ARC Colloquium: Vidya Muthukumar (Georgia Tech)
Surprises in highdimensional linear classification  Groseclose 402 at 11am

Oct 4
ARC Colloquium: Aaron Sidford (Stanford)
Recent Advances on the Maximum Flow Problem  Klaus 1116 East at 11am

Oct 18
ARC Colloquium: Anupam Gupta (CMU)
Finding and Counting kcuts in Graphs  Klaus 1116 East at 11am

Sep 22
ARC Seminar: Jan van den Brand (SimonsBerkeley)
From Interior Point Methods to Data Structures and Back  Klaus 1116 East at 3:00pm

Sep 20
ARC Colloquium: Ilias Diakonikolas (UW Madison)
Learning with Massart Noise  Klaus 1116 East at 11am

Mar 89
ThinkTankTalk: Arijit Raychowdhury (Georgia Tech)
Title Computing with Hardware Accelerated Dynamical SystemsVirtual via Bluejeans at 11:00am

Apr 26
ARC Colloquium: Ashwin Pananjady (Georgia Tech)
Toward instanceoptimal policy evaluation: From lower bounds to algorithms  Virtual via Bluejeans at 11:00am

Apr 19
ARC Colloquium: Shalev BenDavid (Univ. of Waterloo)
Forecasting Algorithms, Minimax Theorems, and Randomized Lower Bounds  Virtual via Bluejeans at 11:00am

Apr 6
ARC Seminar: Timothy Chu (CMU)
Manhattan Distances, Kernels, and Metric Transforms  Virtual via Bluejeans at 11:00am

Mar 31
ARC Seminar: Quanquan C. Liu (MIT)
Parallel Algorithms for Graph Computations  Virtual via Bluejeans at 11:00am

Apr 2
ARC/ACO Student Seminar: Jingyan Wang (CMU)
Towards Understanding and Mitigating Biases Virtual via Bluejeans at 12:00pm

Apr 5
ARC Colloquium: Ankur Moitra (MIT)
Algorithmic Foundations for the Diffraction Limit  Virtual via Bluejeans at 11:00am

Apr 12
ARC Colloquium: Amin CojaOghlan (Goethe University, Frankfurt)
Group Testing  Virtual via Bluejeans at 11:00am

Mar 29
ARC Colloquium: Jan Vondrak (Stanford)
Combinatorial allocation, submodular functions, and Nash social welfare  Virtual via Bluejeans at 11:00am

Mar 22
ARC Colloquium: Avrim Blum (TTIC)
On learning in the presence of biased data and strategic behavior  Virtual via Bluejeans at 11:00am

Mar 1
ARC Colloquium: Rico Zenklusen (ETH Zurich)
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches Virtual via Bluejeans at 11:00am

Feb 8
ARC Day with keynote by Uriel Feige (Weizmann Institute)
Faithful rounding of linear programs Virtual via Bluejeans at 10:00am
The Algorithms & Randomness Center presents ARC DAY with keynote speaker Uriel Feige of the Weizmann Institute, along with talks by Swati Gupta and Anton Bernshteyn of Georgia Tech.

Dec 14
ARC Colloquium: Zhao Song (Princeton & Institute for Advanced Study)
Faster Optimization : From Linear Programming to Deep Learning  Virtual via Bluejeans at 11:00am

Nov 30
ARC and IndoUS Virtual Center Seminar: Zongchen Chen (Georgia Tech)
Optimal Mixing of Glauber Dynamics: Entropy Factorization via HighDimensional Expansion: Virtual via Bluejeans @ 11:00am

Nov 9
ARC Colloquium: Surbhi Goel (Univ. of Texas at Austin)
Computational Complexity of Learning Neural Networks over Gaussian Marginals: Virtual via Bluejeans at 11:00am

Nov 16
ThinkTankTalk: B. Aditya Prakash (Georgia Tech)
Networks and Propagation for Fun, Profit and Social Good: Virtual via Bluejeans at 11:00am

Nov 2
ARC Colloquium: Matthew Fahrbach (Google Research)
EdgeWeighted Online Bipartite Matching: Virtual via Bluejeans at 11:00am

Oct 26
ARC Colloquium: Nick Harvey (Univ. of British Columbia, Vancouver)
Optimal anytime regret with two experts: Virtual via Bluejeans at 11:00am

Oct 12
ARC Colloquium: Sumegha Garg (Princeton)
Extractorbased Approach to Proving MemorySample Lower Bounds for Learning: Virtual via Bluejeans at 11:00am

Oct 5
ThinkTankTalk: Daniel Molzahn (Georgia Tech)
Applications of Polynomial Optimization in Electric Power Systems: Virtual via Bluejeans at 11:00am

Oct 19
ARC Colloquium: Alberto Del Pia (WISC)
Short simplex paths in lattice polytopes: Virtual via Bluejeans at 11:00am

Aug 31
ARC Colloquium: Richard Peng (Georgia Tech)
Solving Sparse Linear Systems Faster than Matrix Multiplication: Virtual via Bluejeans at 11:00am

Sep 28
ARC Colloquium: Vera Traub (ETH Zurich)
Reducing Path TSP to TSP: Virtual via Bluejeans at 11:00am

Aug 24
ARC Colloquium: Debmalya Panigrahy (Duke University)
Deterministic Mincut in Polylogarithmic Maxflows: Virtual via Bluejeans at 11:00am

Aug 17
ARC and IndoUS Virtual Center Seminar: Tselil Schramm (Stanford)
Reconciling Statistical Queries and the Low Degree Likelihood Ratio  Virtual via Bluejeans at 11:30am

Jul 27
ARC and IndoUS Virtual Center Seminar: Shayan Oveis Gharan (Univ. of Washington)
A (slightly) Improved Approximation algorithm for Metric TSP  Virtual via Bluejeans at 11:30am

Jul 20
ARC and IndoUS Virtual Center Seminar: Lap Chi Lau (University of Waterloo)
A Spectral Approach to Network Design  Virtual via Bluejeans at 11:30am

Jun 29
ARC Colloquium: Yuanzhi Li (CMU)
Backward Feature Correction: How can Deep Learning perform Deep Learning  Virtual via Bluejeans at 11:00 am

Jun 8
ARC and IndoUS Virtual Center Seminar: Pravesh Kothari (CMU)
Outlierrobust Clustering of Gaussian Mixtures  Virtual via Bluejeans at 11:30am

Apr 27
ARC and IndoUS Virtual Center Seminar: Prasad Raghavendra (UC Berkeley)
ListDecodable Learning via Sum of Squares  Virtual via Bluejeans at 11:30am

Mar 30
"POSTPONED" ARC Colloquium: Mark A. Davenport (Georgia Tech)
Title TBA  Klaus 1116 East at 11am

Mar 2
ARC Colloquium: Maryam Aliakbarpour
Distribution testing: Classical and new paradigms  Klaus 1116 East at 10am

Feb 10
ARC Colloquium: Vedat Levi Alev (Waterloo)
Improved Analysis of Higher Order Random Walks and Applications  Klaus 1116 East at 11am

Feb 3
ARC Colloquium: Semih Cayci (Ohio State University)
BudgetConstrained Learning and Optimization with Bandit Feedback  Groseclose 402 at 11:00am

Jan 27
ARC Colloquium: Kuikui Liu(Univ. of Washington)
Spectral Independence in HighDimensional Expanders and Applications to the Hardcore Model  Groseclose 402 at 11:00am

Dec 2
ARC Colloquium: Samuel Hopkins(Berkeley)
Robust Mean Estimation in NearlyLinear Time  Klaus 1116 East at 11am

Nov 18
ARC Colloquium: Yuhao Yi(RPI)
Fast Approximation Algorithms and Complexity Analysis for Design of Networked Systems  Klaus 1116 East at 11am

Nov 11
ARC Colloquium: Xiaoming Huo (Georgia Tech)
Homotopic methods can significantly speed up the Computation of the Lassotype of estimators  Klaus 1116 East at 11am

Nov 4
ARC Colloquium: Ravi Kumar (Google)
Algorithmic Discrete Choice  Klaus 1116 East at 11am

Sep 30
ARC/ACO Alumni Colloquium: Nikhil Devanur (Amazon)
Lagrangian Duality in Mechanism Design  Klaus 1116 East at 11am

Oct 2829
ARC Colloquium: Rong Ge (Duke)
What 2layer neural nets can we optimize?  Klaus 1116 East at 11 am

Oct 18
ARC Colloquium: Umang Bhaskar(TIFR)
Partial Function Extension with Applications to Learning and Property Testing  Groseclose 402 at 11am

Oct 7
ARC Colloquium: Thomas Rothvoss (UW)
Linear Size Sparsifier and the Geometry of the Operator Norm Ball  Klaus 1116 East at 11am

Sep 9
ARC Colloquium: Moses Charikar (Stanford)
Approximating Profile Maximum Likelihood Efficiently  Klaus 1116 East at 11am

Sep 23
ARC Colloquium: Shipra Agrawal (Columbia)
Thompson Sampling for learning in online decision making  Groseclose 402 at 11am

Sep 16
ARC Colloquium: Jelani Nelson (UC Berkeley)
Some new approaches to the heavy hitters problem  Groseclose 402 at 11am

Aug 19
ARC Colloquium: Aleksandar Nikolov (Univ. of Toronto)
The Power of Factorization Mechanisms in Differential Privacy  Klaus 1116 East at 11am

Feb 11
ARC Distinguished Lecture: Éva Tardos (Cornell)
Learning and Efficiency of Outcomes in Games  Klaus 1116 E & W at 10 am

Mar 4
ARC Colloquium: Konstantin Tikhomirov (Georgia Tech)
Singularity of Bernoulli random matrices  Klaus 1116E at 11 am

Mar 25
ARC Colloquium: Ravi Kannan (MSR)
A General Algorithm for Unsupervised Learning problems  Klaus 1116 East at 11 am

Apr 1
ARC Colloquium: Kunal Talwar (Google)
Amplification Theorems for Differentially Private Machine Learning  Klaus 1116 East at 11 am

Apr 2325
ARC Lecture Series: Ola Svensson (EPFL)
Breakthroughs in Approximation Algorithms for Traveling Salesman Problems (TSP)  Groseclose 402

May 6
ARC Colloquium: Will Perkins (UIC)
Abstract polymer models, the cluster expansion, and applications  Klaus 1116 East at 11 am

May 20
ARC Colloquium: Yin Tat Lee(UW)
Solving Linear Programs in the Current Matrix Multiplication Time  Klaus 1116 East at 11 am

May 13
ARCIISP Colloquium: Richard DeMillo (Georgia Tech)
The Difficult Problem of Simply Voting  MiRC Pettit 102 at 11am

Aug 19
ARC Colloquium: Aleksandar Nikolov (Univ. of Toronto)
The Power of Factorization Mechanisms in Differential Privacy  Klaus 1116 East at 11am

Sep 16
ARC Colloquium: Jelani Nelson (UC Berkeley)
Some new approaches to the heavy hitters problem  Groseclose 402 at 11am

Sep 23
ARC Colloquium: Shipra Agrawal (Columbia)
Thompson Sampling for learning in online decision making  Groseclose 402 at 11am

Sep 9
ARC Colloquium: Moses Charikar (Stanford)
Approximating Profile Maximum Likelihood Efficiently  Klaus 1116 East at 11am

Oct 7
ARC Colloquium: Thomas Rothvoss (UW)
Linear Size Sparsifier and the Geometry of the Operator Norm Ball  Klaus 1116 East at 11am

Oct 18
ARC Colloquium: Umang Bhaskar(TIFR)
Partial Function Extension with Applications to Learning and Property Testing  Groseclose 402 at 11am

Oct 2829
ARC Colloquium: Rong Ge (Duke)
What 2layer neural nets can we optimize?  Klaus 1116 East at 11 am

Sep 30
ARC/ACO Alumni Colloquium: Nikhil Devanur (Amazon)
Lagrangian Duality in Mechanism Design  Klaus 1116 East at 11am

Nov 4
ARC Colloquium: Ravi Kumar (Google)
Algorithmic Discrete Choice  Klaus 1116 East at 11am

Nov 11
ARC Colloquium: Xiaoming Huo (Georgia Tech)
Homotopic methods can significantly speed up the Computation of the Lassotype of estimators  Klaus 1116 East at 11am

Nov 18
ARC Colloquium: Yuhao Yi(RPI)
Fast Approximation Algorithms and Complexity Analysis for Design of Networked Systems  Klaus 1116 East at 11am

Dec 2
ARC Colloquium: Samuel Hopkins(Berkeley)
Robust Mean Estimation in NearlyLinear Time  Klaus 1116 East at 11am