Algorithms, Randomness and Complexity Center (ARC)
Our mission
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 thinktank 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 [4]
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

Prices, Auctions, and Combinatorial Prophet Inequalities
(20161003)The most common way to sell resources, from apples to business licenses to concert tickets, is to post prices. A choice of prices can be viewed as an algorithm for an online stochastic optimization problem, which makes ... 
A Fast and Simple Unbiased Estimator for Network (Un)reliability
(20160926)The following procedure yields an unbiased estimator for the disconnection probability of an nvertex graph with minimum cut c if every edge fails independently with probability p: (i) contract every edge independently ... 
Strongly Rayleigh distributions and their Applications in Algorithm Design
(20160912)A multivariate polynomial p(z1,...,zn) is stable if p(z1,...,zn) <> 0 whenever Im(zi)>0 for all i. Strongly Rayleigh distributions are probability distributions on 01 random variables whose generating polynomial is stable. ... 
Algorithmic Pricing
(Georgia Institute of Technology, 20130408)Pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare or profit) is a central problem in Algorithmic Mechanism Design. In this talk I will discuss ... 
On Graphs, Arithmetic Progressions and Communication
(Georgia Institute of Technology, 20120828)Tools from extremal graph theory are helpful in the study of problems in additive number theory, theoretical computer science, and information theory. I will illustrate this fact by several closely related examples focusing ... 
Sums of Squares In Optimization
(Georgia Institute of Technology, 20120828) 
Robotics and Vision
(Georgia Institute of Technology, 20120828) 
Inverting Underdetermined Linear Systems Using Structure
(Georgia Institute of Technology, 20120828) 
An Introduction to Additive Combinatorics Via 'Carries'
(Georgia Institute of Technology, 20120828)When numbers are added in the usual way, "carries" occur. The chance of a carry is about .45 (base 10). There are other choices of digits that lead to fewer carries (balanced digits). These balanced systems turn out to be ... 
Online Matching and Adwords
(20120423) 
Submodularity and the Complexity of Constraint Satisfaction
(20120423) 
Optimization of Submodular Functions: Tutorial  lecture II
(20120423) 
Optimization of Submodular Functions: Tutorial  Lecture I
(20120423) 
Submodular minimization in combinatorial problems
(20120423) 
New and Improved Bounds for the Minimum Set Cover Problem
(20120423) 
Computing the Concave Closure of Discrete Concave Functions
(20120423)