ARC Talks and Events
Distinguished lectures, colloquia, seminars and speakers of interest to the Algorithms, Randomness and Complexity Center
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.
Recent Submissions

Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
(20161128)We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix with a sparse Cholesky factorization – the ... 
Explicit TwoSource Extractors and Resilient Functions
(20161114)We explicitly construct an extractor for two independent sources on n bits, each with minentropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{\Omega(1)}. The best previous ... 
Differentially Private Analysis of Graphs
(20161107)Many types of data can be represented as graphs, where nodes correspond to individuals and edges capture relationships between them. Examples include datasets capturing “friendships” in an online social network, financial ... 
Robust Statistics, Revisited
(20161031)Starting from the seminal works of Tukey (1960) and Huber (1962), the field of robust statistics asks: Are there estimators that provable work in the presence of noise? The trouble is that all known provably robust estimators ... 
Human Decisions and Machine Predictions
(20161024)An increasing number of domains are providing us with detailed trace data on human decisions, often made by experts with deep experience in the subject matter. This provides an opportunity to use machinelearning prediction ... 
From Minimum Cut to Submodular Minimization: Leveraging the Decomposable Structure
(20161017)Submodular function minimization is a fundamental optimization problem that arises in several applications in machine learning and computer vision. The problem is known to be solvable in polynomial time, but general purpose ... 
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 ...