Algorithms and Randomness Center (ARC)
Our mission is to identify problems with natural connections to algorithms and randomness. To help solve these problems and understand related phenomena by suggesting provable algorithms and algorithmic explanations. To formulate general tools based on the solutions and the insights behind them and thereby extend and solidify the theory of algorithms. To represent an algorithms and randomness think tank that scientists across campus can use as a resource.
All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved. Such materials may be used, quoted or reproduced for educational purposes only with prior permission, provided proper attribution is given. Any redistribution, reproduction or use of the materials, in whole or in part, is prohibited without prior permission of the author.
Collections in this community

ARC5 Distinguished Lecture [5]
Klaus Advanced Computing Building  August 28, 2012 
ARC Talks and Events [68]
Distinguished lectures, colloquia, seminars and speakers of interest to the ARC community 
ARC Theory Day [5]
Thursday, November 10, 2011 and Friday, November 11, 2011 
Modern Aspects of Submodularity [27]
March 1922, 2012 at Georgia Tech
Recent Submissions

Solving Linear Programs in the Current Matrix Multiplication Time
(20190520)We show how to solve linear programs with accuracy epsilon in time n^{omega+o(1)} log(1/epsilon) where omega~2.3728639 is the current matrix multiplication constant. This hits a natural barrier of solving linear programs ... 
Abstract polymer models, the cluster expansion, and applications
(20190506)Will introduces abstract polymer models and the cluster expansion from statistical physics. He describes some of the original applications of these tools in statistical physics to understand phase transitions in lattice ... 
A constantfactor approximation algorithm for asymmetric TSP [Lecture 3]
(20190425)The traveling salesman problem is one of the most fundamental optimization problems. Given cities and pairwise distances, it is the problem of finding a tour of minimum distance that visits each city once. In spite of ... 
Different approaches for asymmetric TSP [Lecture 2]
(20190424)The traveling salesman problem is one of the most fundamental optimization problems. Given cities and pairwise distances, it is the problem of finding a tour of minimum distance that visits each city once. In spite of ... 
Amplification Theorems for Differentially Private Machine Learning
(20190401)A rigorous foundational approach to private data analysis has emerged in theoretical computer science in the last decade, with differential privacy and its close variants playing a central role. We have recently been able ... 
A Tight Net with Respect to a Random Matrix Norm and Applications to Estimating Singular Values
(20190211)In this talk we construct a net around the unit sphere with good properties. We show that with exponentially high probability, the value of Ax on the sphere can be approximated well using this net, where A is any random ... 
Towards Understanding First Order Algorithms for Nonconvex Optimization in Machine Learning
(20190211)Stochastic Gradient Descenttype (SGD) algorithms have been widely applied to many nonconvex optimization problems in machine learning, e.g., training deep neural networks, variational Bayesian inference and collaborative ... 
Learning and Efficiency of Outcomes in Games
(20190211)Selfish behavior can often lead to suboptimal outcome for all participants, a phenomenon illustrated by many classical examples in game theory. Over the last decade we have studied Nash equilibria of games, and developed ... 
The polymorphic gateway between structure and algorithms: Beyond CSPs
(20181203)What underlying mathematical structure (or lack thereof) in a computational problem governs its efficient solvability (or dictates its hardness)? In the realm of constraint satisfaction problems (CSPs), the algebraic ... 
Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters
(20181126)I will go over some of my past and present work on hashingbased data structures. After presenting some background on Bloom filters and cuckoo hashing, we will describe cuckoo filters, an efficient data structure for ... 
Algorithmic PirogovSinai theory
(20181105)We develop efficient algorithms to approximate the partition function and sample from the hardcore and Potts models on lattices at sufficiently low temperatures in the phase coexistence regime. In contrast, the Glauber ... 
Fairness in Algorithmic Decision Making
(20181029)In this talk we survey some formulations of fairness requirements for decision making under uncertainty. We then discuss results from 3 recent papers: 1) Treating individuals fairly is not in conflict with longterm ... 
The Paulsen problem, continuous operator scaling, and smoothed analysis
(20181015)The Paulsen problem is a basic open problem in operator theory. We define a continuous version of the operator scaling algorithm to solve this problem. A key step is to show that the continuous operator scaling algorithm ... 
Improved Decoding of Folded ReedSolomon and Multiplicity Codes
(20181001)Listdecoding is an important primitive in the theory of error correcting codes, and it has long been a goal to obtain explicit constructions of capacityachieving, efficiently listdecodable codes. Folded ReedSolomon ... 
(Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs
(20180924)The Graph Matching problem is a robust version of the Graph Isomorphism problem: given two notnecessarilyisomorphic graphs, the goal is to find a permutation of the vertices which maximizes the number of common edges. ... 
On the Complexity of Clustering Problems
(20180910)Euclidean kmeans clustering, a problem having numerous applications, is NPhard in the worst case but often solved efficiently in practice using simple heuristics. A quest for understanding the properties of realworld ... 
Cutoff with window for the random to random shuffle
(20180517)Cutoff is a remarkable property of many Markov chains in which they after number of steps abruptly transition in a smaller order window from an unmixed to a mixed distribution. Most random walks on the symmetric group, ... 
A Friendly Smoothed Analysis of the Simplex Method
(20180517)Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful frameworks for understanding the simplex method ... 
On the infection time of the Duarte model: the role of energy barriers
(20180515)In the Duarte model each vertex of Z<sup>2</sup> can be either infected or healthy. In the bootstrap percolation model version, infected vertices stay infected while a healthy vertex becomes infected if at least two of its ... 
Sphere packings, codes, and kissing numbers via hard core models
(20180517)We prove a lower bound on the expected size of a spherical code drawn from a "hard cap" model and the expected density of a packing drawn from the hard sphere model in high dimensions. These results allows us to improve ...