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 [58]
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

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 ... 
Inapproximability of the Independent Set Polynomial in the Complex Plane
(20180517)Hardcore model (also known as independent set polynomial) is one of the simplest models in statistical physics. The complexity of approximating the value of the partition function of the model on maxdegreeDelta graphs ... 
Learning discrete Markov Random Fields with nearly optimal runtime and sample complexity
(20180517)We give an algorithm for learning the structure of an undirected graphical model that has essentially optimal sample complexity and running time. We make no assumptions on the structure of the graphical model. For Ising ... 
Markov Chain Algorithms for Programmable Active Matter
(20180516)We consider stochastic solutions to problems arising from programmable active matter based on emergent phenomena. We view active matter as a collection of simple computational elements (or particles) with limited memory ... 
An algorithmic version of Banaszczyk's discrepancy theorem
(20180516)In the 90's Banaszczyk developed a very powerful method for discrepancy problems, that goes beyond the partial coloring method. His result was based on deep results from convex geometry and was nonconstructive. In this ... 
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
(20180516)Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much research has been devoted ... 
A polynomialtime approximation algorithm for allterminal network reliability
(20180516)Let G be an undirected graph in which each edge is assigned a failure probability. Suppose the edges fail independently with the given probabilities. We are interested in computing the probability that the resulting graph ... 
Maximum Cut problem on sparse random hypergraphs: structural results using the interpolation method and the algorithmic implications.
(20180515)We consider a particular version of the Maximum Cut problem (to be defined in the talk) on a sparse random Kuniform hypergraph, when K is even. The goal is to compute the maximum cut value w.h.p., and ideally to find ... 
Relative Error Tensor Low Rank Approximation
(20180515)We consider relative error low rank approximation of tensors with respect to the Frobenius norm: given an orderq tensor A, output a rankk tensor B for which AB_F <= (1+eps)OPT, where OPT =inf_{rankk A'} AA'_F. ... 
Random walks on the chambers of a hyperplane arrangement
(20180515)The BidigareHanlonRockmore random walk on the chambers of a real hyperplane arrangement is a Markov chain that generalizes famous examples, such as the Tsetlin library and riffle shuffles. We will introduce lower bounds ... 
Mixing in groups: From Ramanujan graphs to the product replacement algorithm
(20180515)I will survey several recent works involving mixing for random walks on groups and regular graphs. In joint work with Eyal Lubetzky, we determined precisely the mixing time of random walk on optimal dregular expanders ...