-
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 9-10
TetFest60: Probabilistic Trajectories in Algorithms and Combinatorics
Klaus 1116 • https://sites.gatech.edu/tetfest60/
A workshop on probability, algorithms, and combinatorics
Georgia Tech will host a 2-day workshop (September 9-10) on the rich interplay between randomness, algorithms, and discrete mathematics with a view towards both the history of how these topics came together and flourished and exciting future directions and challenges. The workshop will take place just before the RANDOM-APPROX conference (September 11-13, hosted by Georgia Tech), and we expect many participants to attend both events.
For a full schedule see here
-
Sep 11-13
RANDOM-APPROX 2023
Bill Moore Student Success Center • https://sites.gatech.edu/randomapprox2023/
Georgia Tech will host the yearly computer science conferences
Georgia Tech hosts the RANDOM and APPROX conferences in 2023.
-
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
-
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 25
ARC Colloquium: Jerry Li (MSR)
TBA
-
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
-
May 13
ARC-IISP Colloquium: Richard DeMillo (Georgia Tech)
The Difficult Problem of Simply Voting - MiRC Pettit 102 at 11am
-
May 20
ARC Colloquium: Yin Tat Lee(UW)
Solving Linear Programs in the Current Matrix Multiplication Time - Klaus 1116 East at 11 am
-
May 6
ARC Colloquium: Will Perkins (UIC)
Abstract polymer models, the cluster expansion, and applications - 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
-
Apr 1
ARC Colloquium: Kunal Talwar (Google)
Amplification Theorems for Differentially Private Machine Learning - Klaus 1116 East at 11 am
-
Mar 25
ARC Colloquium: Ravi Kannan (MSR)
A General Algorithm for Unsupervised Learning problems - Klaus 1116 East at 11 am
-
Mar 4
ARC Colloquium: Konstantin Tikhomirov (Georgia Tech)
Singularity of Bernoulli random matrices - Klaus 1116E at 11 am
-
Feb 11
ARC Distinguished Lecture: Éva Tardos (Cornell)
Learning and Efficiency of Outcomes in Games - Klaus 1116 E & W at 10 am
-
Dec 3
ARC Colloquium: Venkat Guruswami (CMU)
The polymorphic gateway between structure and algorithms: Beyond CSPs - Klaus 1116E at 11 am
-
Nov 26
ARC-TRIAD Colloquium: Michael Mitzenmacher (Harvard)
Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters - Klaus 1116E at 11 am
-
Oct 29
ARC Colloquium: Sampath Kannan (UPenn)
Fairness in Algorithmic Decision Making - Klaus 1116 East at 11 am
-
Oct 1
ARC-TRIAD Colloquium: Mary Wootters (Stanford)
Improved Decoding of Folded Reed-Solomon and Multiplicity Codes - MiRC Pettit 102 A&B at 11 am
-
Oct 22
ARC-TRIAD Colloquium: Leslie Valiant (Harvard)
Where Computer Science Meets Neuroscience - Klaus 1116 E & W at 11 am
-
Nov 5
ARC Colloquium: Will Perkins (UIC)
Algorithmic Pirogov-Sinai theory - Klaus 1116 East at 11 am
-
Sep 24
ARC Colloquium: Tselil Schramm (Harvard/MIT)
(Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs - MiRC Pettit 102 A&B at 11 am
-
Oct 15
ARC Colloquium: Lap Chi Lau (Waterloo)
The Paulsen problem, continuous operator scaling, and smoothed analysis - Klaus 1116E at 11 am
-
Sep 10
ARC Colloquium: Anand Louis (Indian Inst. of Science)
On the complexity of clustering problems - Klaus 1116E at 11 am
-
Apr 30
ARC Colloquium: Nima Anari (Stanford)
Entropy, Log-Concavity, and a Deterministic Approximation Algorithm for Counting Bases of Matroids - Klaus 1116E at 11 am
-
Apr 23
ARC Colloquium: Alexandre Stauffer (Bath)
Competition in randomly growing processes - Klaus 1116E at 11am
-
Mar 16
ARC Colloquium: Yin Tat Lee (UW)
l_p regression beyond self-concordance - MiRC Pettit Rm 102A&B at 11:00am
-
Mar 5
ARC-TRIAD Colloquium: Piotr Indyk (MIT)
"Below P vs. NP: Conditional Quadratic-Time Hardness for Big Data Problems" - Klaus 1116E at 11am
-
Feb 23
ARC Colloquium: Sanjeev Arora (Princeton/IAS)
Toward theoretical understanding of deep learning - Klaus 2447 (classroom) at 11am
-
Mar 12
ARC Colloquium: Xiaorui Sun (Microsoft)
The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds- Klaus 1116E at 11am
-
Feb 19
ARC Colloquium: Vivek Madan (UIUC)
Approximating Multicut and the Demand Graph - Klaus 1116 East at 11:00am
-
Feb 9
ARC Colloquium: Greg Bodwin (MIT)
The Distance Oracle Hierarchy - Skiles 005 at 1pm
-
Feb 12
ARC Colloquium: Aaron Schild (Berkeley)
An almost-linear time algorithm for uniform random spanning tree generation - Klaus 1116 East at 11am
-
Feb 5
ARC Colloquium: Di Wang (Berkeley/GaTech)
Capacity Releasing Diffusion for Speed and Locality - Klaus 1116E at 11am
-
Jan 22
ARC-TRIAD Seminar - Yan Shuo Tan (Michigan)
Efficient algorithms for phase retrieval in high dimensions
-
Jan 17
ARC-TRIAD Seminar - Cong Han Lim (Wisconsin)
Towards Large-Scale Nonconvex/Stochastic Discrete Optimization
-
Dec 4
ARC Colloquium: Scott Aaronson (UT Austin)
Black Holes, Firewalls, and the Limits of Quantum Computers Scott Aaronson (UT Austin) - Klaus 1116 East & West at 11am
-
Nov 16
ACO-ARC Seminar: Vijay Vazirani (UC Irvine)
Planar Graph Maximum Matching is in NC (Skiles 005 at 1:30pm)
-
Nov 27
ARC Colloquium: Jonathan Hermon (Cambridge)
A characterization of $L_p$ mixing, cutoff and hypercontractivity via maximal inequalities and hitting times (Klaus 1116 East at 11am)
-
Nov 6
ARC Colloquium: Aviad Rubinstein (UC Berkeley)
Distributed PCP Theorems for Hardness of Approximation in P (Klaus 1116 East at 11am)
-
Oct 30
ARC 11 with Keynote by Robert Schapire
The Contextual Bandits Problem: Techniques for Learning to Make High-Reward Decisions (Klaus 1116 E&W at 11:00am)
The Algorithms & Randomness Center presents ARC11 with Keynote speaker Robert Schapire of Microsoft Research (NYC), along with talks by John Wilmes(CS) and Antonio Blanca (CS)
-
Oct 20
ARC Colloquium: Mike Molloy (Univ. of Toronto)
The list chromatic number of graphs with small clique number (Skiles 005 at 11:00 am)
-
Oct 23
ARC Colloquium: Barna Saha (UMass Amherst)
Language Edit Distance, (min,+)-Matrix Multiplication & Beyond (Klaus 1116 East at 11am)
-
Oct 2
ARC Colloquium: Reza Gheissari (NYU)
Mixing Times of Critical 2D Potts Models (Klaus 1116 East at 11am)
-
Sep 25
ARC Colloquium: Stefanie Jegelka (MIT)
Variations of Submodularity and Diversity: from Robust Optimization to Markov Chains (Caddell Flex Space Rm 122-126 at 11:00 am)
-
Sep 18
ARC Colloquium: Ilias Diakonikolas (USC)
Statistical Query Lower Bounds for High-Dimensional Unsupervised Learning (Klaus 1116 East at 11am)
-
Sep 21
ARC Seminar: Andreas Galanis (Oxford)
Random Walks on Small World Networks (Klaus 1116 East at 11am)
-
Aug 4
ARC Colloquium: Deeparnab Chakrabarty (Dartmouth)
Submodular Function Minimization via Continuous Optimization (Klaus 1116E at 11am)
-
Apr 10
ARC Colloquium: Emmanuel Abbe (Princeton)
Old and new on the stochastic block model (Klaus 1116 E at 11am)
-
Mar 27
ARC Colloquium: Philip Klein (Brown)
Approximation Schemes for Planar Graphs: A Survey of Methods (Klaus 1116 E at 11am)
-
May 1
ARC Colloquium: Michael Cohen (MIT)
New Algorithms for Matrix Scaling Problems via Second-order Methods and Generalized Laplacian System Solvers (Klaus 1116E at 11am)
-
Feb 13
ARC Colloquium: Ramamohan Paturi (UCSD)
Genesis of ETH and SETH (Klaus 1116 E at 11 am)
-
Mar 6
ARC Colloquium: Constantinos Daskalakis (MIT)
Ten Steps of EM Suffice for Mixtures of Two Gaussians (Klaus 1116 E at 11am)
-
Mar 13
Alberto Apostolico Memorial Lecture: Richard M. Karp (UC Berkeley/Simons Institute)
Turing award winner speaking on March 13, 11am (Klaus 1116)
-
Mar 15
Distinguished Lecture: Bruno Olshausen (Berkeley)
Neural computations for active perception (Marcus Nano 1117 at 2pm)
-
Mar 15
Theoretical Neuroscience Day
Wednesday, March 15, 2017 at 2pm in Marcus 1117