Events for 2023-2024

Events for 2023-2024.

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 worst-case analysis. We aim for algorithms that have near optimal performance when these predictions are good, but still maintain provable bounds (such as for worst-case 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 co-authored over 250 conference and journal publications on a variety of topics, including algorithms for the Internet, efficient hash-based data structures, erasure and error-correcting codes, power laws, and compression. He is an ACM and IEEE Fellow. He has co-authored a widely used textbook on randomized algorithms and probabilistic techniques in computer science published by Cambridge University Press.
Oct 18-20

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 log-concavity

Title: Tight Markov chain analysis using discrete log-concavity
Abstract:
Sampling is a fundamental task with many applications in algorithm design and in machine learning. Sampling from high-dimensional 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 log-concavity. 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 infinitely-often regime. In more detail, we give an unconditional polynomial-time randomized algorithm B such that, for infinitely many values of n, B(1^n) outputs a canonical n-bit 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 infinitely-often pseudodeterministic polynomial-time construction of strings satisfying Q. This improves upon a subexponential-time 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 hardness-randomness framework of Chen and Tell, using a variant of the Shaltiel-Umans 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 high-dimensional 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 Decision-Making 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

https://neuro.gatech.edu/georgia-tech-neuro-seminar-series-10
Jan 23

ARC Colloquium: Elizabeth Yang (Berkeley)

Testing thresholds for high-dimensional 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 Multi-Species 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

ARC-ACO 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 st-Distances - 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 Minimum-Cost Flow in Almost-Linear 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

ARC-ACO Lecture Series: featuring Pravesh Kothari (CMU)

High-Dimensional Statistical Estimation via Sum-of-Squares - 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 Multi-Item 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 high-dimensional 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 k-cuts in Graphs - Klaus 1116 East at 11am
Sep 22

ARC Seminar: Jan van den Brand (Simons-Berkeley)

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 8-9

ThinkTankTalk: Arijit Raychowdhury (Georgia Tech)

Title Computing with Hardware Accelerated Dynamical Systems-Virtual via Bluejeans at 11:00am
Apr 26

ARC Colloquium: Ashwin Pananjady (Georgia Tech)

Toward instance-optimal policy evaluation: From lower bounds to algorithms - Virtual via Bluejeans at 11:00am
Apr 19

ARC Colloquium: Shalev Ben-David (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 Coja-Oghlan (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 Indo-US Virtual Center Seminar: Zongchen Chen (Georgia Tech)

Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional 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)

Edge-Weighted 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)

Extractor-based Approach to Proving Memory-Sample 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 Min-cut in Poly-logarithmic Max-flows: Virtual via Bluejeans at 11:00am
Aug 17

ARC and Indo-US 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 Indo-US 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 Indo-US 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 Indo-US Virtual Center Seminar: Pravesh Kothari (CMU)

Outlier-robust Clustering of Gaussian Mixtures - Virtual via Bluejeans at 11:30am
Apr 27

ARC and Indo-US Virtual Center Seminar: Prasad Raghavendra (UC Berkeley)

List-Decodable 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)

Budget-Constrained Learning and Optimization with Bandit Feedback - Groseclose 402 at 11:00am
Jan 27

ARC Colloquium: Kuikui Liu(Univ. of Washington)

Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model - Groseclose 402 at 11:00am
Dec 2

ARC Colloquium: Samuel Hopkins(Berkeley)

Robust Mean Estimation in Nearly-Linear 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 Lasso-type 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 28-29

ARC Colloquium: Rong Ge (Duke)

What 2-layer 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 23-25

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

ARC-IISP 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 28-29

ARC Colloquium: Rong Ge (Duke)

What 2-layer 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 Lasso-type 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 Nearly-Linear Time - Klaus 1116 East at 11am