Organizing Committee Co-Chairs
Henry Cohn, Microsoft Research New England, USA
Dana Randall, Georgia Institute of Technology, USA

Martin Farach-Colton - Rutgers University

Monday, February 8, 20116

Klaus 1116 West - 1:00 pm

(Refreshments will be served in Klaus 2222 at 2 pm)

Title:
A Field Guide to Write Optimization

Abstract:
Dictionaries are probably the most widely studied and deployed data structures.  For large data, write-optimization techniques allow one to insert records much faster than they can be searched.  These new techniques are changing the way such dictionaries are used, which leads to new analytical questions.  In this talk, I will survey some of the recent work on write-optimized dictionaries and discuss the impact the new algorithmic work is having in the implementation of storage systems.

Bio:
Martin Farach-Colton received his MD from Johns Hopkins and his PhD in Computer Science from the University of Maryland.  He is a Professor Computer Science at Rutgers University.  He is CTO and Co-founder of Tokutek, a database company that was founded to commercialize his research.  This company was acquired by Percona in 2015.  During 2000-2002, he was a Senior Research Scientist at Google.  He works on external memory algorithms as well as their application to storage systems.

Ian Munro – University of Waterloo

Monday, February 1, 20116

Klaus 1116 West - 1:00 pm

(Refreshments will be served in Klaus 2222 at 2 pm)

Title:
Optimal Search Trees with 2-way Comparisons

Abstract:
This talk is about finding a polynomial time algorithm that you probably thought was known almost a half century ago, but it wasn’t. The polynomial time algorithm is still rather slow and requires a lot of space to solve, so we also look at extremely good and fast approximate solutions. More specifically …
In 1971, Knuth gave an O(n²)-time algorithm for the now classic problem of finding an optimal binary search tree. Knuth’s algorithm works only for search trees based on 3-way comparisons, but most modern programming languages and computers support only 2-way comparisons (<, = and >). Until this work, the problem of finding an optimal search tree using 2-way comparisons remained open — polynomial time algorithms were known only for restricted variants. We solve the general case, giving

(i)  an O(n⁴)-time algorithm and

(ii) a linear time algorithm that gives a tree with expected search cost within 2 comparisons of the optimal.

This is joint work with Marek Chrobak, Mordecai Golin, and Neal E. Young.

William Gasarch – University of Maryland

Wednesday, February 17, 20116

Klaus 1116 East - 1:00 pm

(Refreshments will be served in Klaus 2222 at 2 pm)

Title:
Advanced Results in the Theory of Languages and Computation which have Simple Proofs

Abstract:
Automata theory is about the following: Given a language (a set of strings) how hard is it? Is it regular, context free, or decidable? We give three results that COULD be put in a course on such but are not!

1. Regular, Context free, and Decidable languages are closed under many operations. Note the following: if L is regular (CFL) then SUBSEQ(L) is regular (CFL).  This is an easy exercise. But what if L is decidable? Is SUBSEQ(L) decidable? The answer may surprise you!
2. There are languages L that are regular but the DFA for them is much smaller than the CFG for them. How much smaller? The answer may surprise you!
3. It is easy to show that COL3 \le COL4 (three-colorability \le 4-colorablity). Is COL4 \le COL3? You probably know that it is by going through the Cook-Levin Theorem. Is there an easier proof? The answer would surprise you if I didn't ask the question so I'll just say YES- I will show COL4 \le COL3 with a simple proof.

The answers may surprise you!

John Wilmes – University of Chicago

Monday, January 25, 20116

MiRC 102 A & B - 1:00 pm

(Refreshments will be served in Klaus 2222 at 2 pm)

Title:
The Isomorphism Problem for Highly Regular Structures

Abstract:

The Graph Isomorphism (GI) problem has been notorious in computational complexity theory for its unresolved complexity status. Until Babai's recently announced quasipolynomial-time algorithm for GI, the worst-case time-complexity bound of $\exp(\tilde{O}(n^{1/2}))$ where $n$ is the number of vertices (Babai--Luks, 1983), had stood for over 30 years.

Among the obstacles Babai confronts in his recent breakthrough are primitive coherent configurations (PCCs), a class of highly-regular structures generalizing strongly regular graphs. In this talk, we will describe recent progress characterizing the structure and automorphism groups of PCCs and other highly-regular structures, with applications to GI, and we will describe the connections between these results and Babai's breakthrough.

In particular, in joint work with Sun, we classify the PCCs with the most automorphisms. In joint work with Babai, Chen, Sun, and Teng, we give the first quasipolynomial-time algorithm for strongly regular GI over an entire interval of the exponent of the degree parameter. And in joint work with Babai, we give a $n^{O(\log n)}$-time algorithm for the important special case of Steiner Design Isomorphism.  In all cases, our progress relies on new structural results we prove, especially on new bounds for the rate of expansion of small sets.

Algorithms & Randomness Center (ARC)

Antonio Blanca - UC Berkeley

Friday, February 5, 2016

Klaus 1116 East (not West) - 2:00 pm

(Refreshments will be served in Klaus 2222 at 3 pm)

Title:
Dynamics for the random-cluster model

Abstract:
The random-cluster model has been widely studied as a unifying framework for random graphs, spin systems and electrical networks, but its dynamics have so far largely resisted analysis. In this talk we present recent results concerning the mixing behavior of natural Markov chains for the random-cluster model in two canonical cases: the mean-field model and the two dimensional lattice graph Z^2. In the mean-field case, we identify a critical regime of the model parameter p in which several natural dynamics undergo an exponential slowdown. In Z^2, we provide tight mixing time bounds for the heat-bath dynamics for all non-critical values of p. These results hold for all values of the second model parameter q > 1.

Based on joint works with Alistair Sinclair.

Short Bio: Antonio Blanca is a 5th year PhD student at UC Berkeley advised by Alistair Sinclair. He is interested in algorithms, Markov chain mixing, phase transitions and random structures. He graduated with a BS in Computer Science/Discrete Math from Georgia Tech.

ARC Theory Day

Monday, April 11, 2016

Klaus 1116 - 9:00 am - 4:00 pm

Objective:  
Algorithms and Randomness Center (ARC) Theory Day is an annual event to showcase lectures on exciting new developments in theoretical computer science. This year's event features four young speakers who are dedicated to investigating some of the most complex questions in theoretical computer science. These guests will discuss a wide range of topics from interior point methods to circuit lower bounds by random projections. The lectures promise to be engaging and discuss techniques to help solve these emerging problems and understand related phenomena.

Organizers: Santosh Vempala, Richard Peng and Dana Randall

Schedule:

Monday, April 11, 2016:

9:30 am        Breakfast
9:50 am        Opening Remarks
10:00 am      Virginia Vassilevska-Williams (Stanford): Fine-Grained Algorithms and Complexity
11:00 am      Break
11:15 am      Rocco Servedio (Columbia): Circuit Lower Bounds via Random Projections
12:15 pm      Lunch Break
1:30 pm        Aaron Sidford (Microsoft Research): Recent Advances in the Theory of Interior Point Methods
2:30 pm        Break
2:45 pm        Luca Trevisan (UC Berkeley): Ramanujan Graphs

Abstracts:

Virginia Vassilevska-Williams (Stanford):

Title:
Fine-Grained Algorithms and Complexity
Abstract:
A central goal of algorithmic research is to determine how fast computational problems can be solved in the worst case. Theorems from complexity theory state that there are problems that, on inputs of size n, can be solved in t(n) time but not in t(n)^{1-eps} time for eps>0. The main challenge is to determine where in this hierarchy various natural and important problems lie. Throughout the years, many ingenious algorithmic techniques have been developed and applied to obtain blazingly fast algorithms for many problems. Nevertheless, for many other central problems, the best known running times are essentially those of the classical algorithms devised for them in the 1950s and 1960s.

Unconditional lower bounds seem very difficult to obtain, and so practically all known time lower bounds are conditional. For years, the main tool for proving hardness of computational problems have been NP-hardness reductions, basing hardness on P\neq NP. However, when we care about the exact running time (as opposed to merely polynomial vs non-polynomial), NP-hardness is not applicable, especially if the running time is already polynomial. In recent years, a new theory has been developed, based on “fine-grained reductions” that focus on exact running times. The goal of these reductions is as follows. Suppose problem A is solvable in a(n) time and problem B in b(n) time, and no a(n)^{1-eps} and b(n)^{1-eps} algorithms are known for A and B respectively. Then, if A is fine-grained reducible to problem B (for a(n) and b(n)), a b(n)^{1-eps} time algorithm for B (for any eps>0) implies an a(n)^{1-eps'} algorithm for A (for some eps'>0). Now, mimicking NP-hardness, the approach is to (1) select a key problem X that is conjectured to require t(n)^{1-o(1)} time for some t, and (2) reduce X in a fine-grained way to many important problems. This approach has led to the discovery of many meaningful relationships between problems, and even sometimes to equivalence classes.

In this talk I will give an overview or the current progress in this area of study, and will highlight some new exciting developments.
Bio:
Virginia V. Williams is an assistant professor of computer science at Stanford University. She obtained her Ph.D. in 2008 from Carnegie Mellon where she was advised by Guy Blelloch. Before joining Stanford, she spent time at the Institute for Advanced Study and UC Berkeley. Her main area of interest is broadly in computational complexity, the design and analysis of algorithms, and more specifically in graph and matrix algorithms.

Rocco Servedio (Columbia University)

Title:  
Circuit Lower Bounds via Random Projections
Abstract:
Random restrictions are a classical and important technique for proving circuit lower bounds.  This talk will discuss random projections, a generalization of random restrictions.  While conceptually simple, random projections have led to recent advances on several well-studied lower bound problems involving small-depth circuits.  We will see how random projections play a key role in the following results:

• An average-case depth hierarchy theorem for Boolean circuits. This gives an average-case extension of the classical (worst-case) depth hierarchy theorem of Sipser, Yao, and Hastad, and resolves a main open problem in Hastad’s 1986 PhD thesis.  Via a classical connection between Boolean circuits and structural complexity, this hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, resolving a longstanding conjecture of Hastad, Cai and Babai from the 1980s.  (Joint work with Ben Rossman and Li-Yang Tan.)
• The first super-polynomial lower bounds against the “depth d Frege” proof system for some polylogarithmic depth d.  Previous super-polynomial lower bounds (Pitassi et al. 1993, Krajicek et al. 1995) were only known against depth-d Frege for d=Theta(log log n).  (Joint work with Toni Pitassi, Ben Rossman, and Li-Yang Tan.)
• A nearly optimal size lower bound on small-depth circuits that determine whether a graph has a short s-to-t path.  We show that depth-d circuits for distance-k connectivity on n-node graphs must have size n^{\Omega(k^{1/d}/d)}; the previous best size lower bounds for this problem were n^{k^{\exp(-O(d))}} (due to Beame et al. 1998) and n^{\Omega((\log k)/d)} (due to Rossman 2014).  (Joint work with Xi Chen, Igor Oliveira and Li-Yang Tan.)

Bio:  
Rocco Servedio is an Associate Professor of Computer Science at Columbia University. His research interests center around computational learning theory, property testing, and computational complexity.  Rocco is the recipient of an NSF Career Award and a Sloan Foundation Fellowship; his research has received Best Paper / Best Student Paper awards from the CCC, COLT, FOCS, and STOC conferences.  His teaching at Columbia has been recognized with the Department of Computer Science Distinguished Teaching Award, the Columbia Engineering Alumni Association Distinguished Faculty Teaching Award, and the Columbia Presidential Teaching Award.

Aaron Sidford (Microsoft Research)

Title:
Recent Advances in the Theory of Interior Point Methods 
Abstract: 
In this talk I will survey recent results on using interior point techniques to design provably efficient algorithms. I will give a brief overview of this powerful convex optimization technique and discuss how it has been used to improve the running time of fundamental optimization problems such as maximum flow, linear programming, and most recently the geometric median problem. In particular, I will highlight recent joint work with Michael Cohen, Yin Tat Lee, Jakub Pachocki, and Gary Miller building on these techniques to obtain the first nearly linear time algorithm for computing the geometric median. No previous experience with interior point methods required. 

Bio: 
Aaron Sidford is a postdoctoral researcher at Microsoft Research New England and will be joining the department of Management Science and Engineering at Stanford University in Fall 2016. Aaron received his PhD from the EECS department at MIT where he was advised by Professor Jonathan Kelner. 

Aaron’s research interests lie broadly in the theory of computation and the design and analysis of algorithms. He is particularly interested in work at the intersection of continuous optimization, graph theory, numerical linear algebra, and data structures.

Luca Trevisan (UC Berkeley)

Title:
Ramanujan Graphs
Abstract:
We will review what is known about existence and constructions of Ramanujan graphs, which are the best possible expander graphs from the point of view of spectral expansion.
We will talk about Friedman's result that random graphs are nearly Ramanujan, and recent simplifications of his proof, about a characterization of Ramanujan graphs in terms of the Ihara zeta function, about number-theoretic efficient constructions, and about the recent non-constructive existence results of Marcus, Spielman, and Srivastava.
Bio:
Luca Trevisan is a professor of Electrical Engineering and Computer Sciences and of Mathematics at U.C. Berkeley, and a senior scientist at the Simons Institute for the Theory of Computing. In the past, he has also taught at Columbia University and at Stanford. He is interested in several aspects of computational complexity theory and, in the last few years, he has been working on spectral graph theory.

Marco-Dick Yun Kuen Cheung  - University of Vienna

Monday, February 29, 20116

Klaus 1116 West - 1:00 pm

(Refreshments will be served in Klaus 2222 at 2 pm)

Title:
Graph Minors for Preserving Terminal Distances Approximately

Abstract:
Given a graph where vertices are partitioned into k terminals and non-terminals, the goal is to compress the graph (i.e., reduce the number of non-terminals) using minor operations while preserving terminal distances approximately. The distortion of a compressed graph is the maximum multiplicative blow-up of distances between all pairs of terminals. We study the trade-off between the number of non-terminals and the distortion.  This problem generalizes the Steiner Point Removal (SPR) problem, in which all non-terminals must be removed.

We introduce a novel black-box reduction to convert any lower bound on distortion for the SPR problem into a super-linear lower bound on the number of non-terminals, with the same distortion, for our problem. This allows us to show that there exist graphs such that every minor with distortion less than 2 / 2.5/ 3  must have \Omega(k^2) / \Omega(k^{5/4}) / \Omega(k^{6/5}) non-terminals, plus more trade-offs in between. The black-box reduction has an interesting consequence: if the tight lower bound on distortion for the SPR problem is super-constant, then allowing any linear (in k) non-terminals will not help improving the lower bound to a constant.

We also build on the existing results on spanners, distance oracles and connected 0-extensions to show a number of upper bounds for general graphs, planar graphs, graphs that exclude a fixed minor and bounded treewidth graphs. Among others, we show that any graph admits a minor with O(log k) distortion and O(k^2) non-terminals, and any planar graph admits a minor with $1+epsilon$ distortion and O(k^2 log^2 k / epsilon^2) non-terminals.

Alon Orlitsky - University of CA, San Diego

Monday, April 18, 20116

Klaus 1116 West - 1:00 pm

(Refreshments will be served in Klaus 2222 at 2 pm)

Title: 
Learning and Forecasting over Large Domains: The Art of the Doable

Abstract:
Learning a distribution and forecasting its outcomes are important tasks whose complexity increases with the distribution's support size. We consider useful and natural formulations of these two tasks that allow them to be performed with a sample whose size is fixed and independent of the distribution or its support size.

Learning a distribution to a given KL divergence requires a sample size that increases linearly with the support size. We show that with n samples, the distribution can be learned to a KL divergence that is at most 1/sqrt(n) higher than that achievable by any estimator, even one that knows the distribution up to permutation.

Estimating a distribution's support size may require an unbounded number samples. Yet we show that with n samples, we can estimate the number of hitherto unseen elements that will be observed in up to n*log(n) new samples, thereby estimating the effective support of a much larger sample. 

Joint work with Ananda Theertha Suresh and Yihong Wu. 

Bio:
Alon Orlitsky received B.Sc. degrees in Mathematics and Electrical Engineering from Ben Gurion University in 1980 and 1981, and M.Sc. and Ph.D. degrees in Electrical Engineering from Stanford University in 1982 and 1986.

From 1986 to 1996 he was with the Communications Analysis Research Department of Bell Laboratories. He spent the following year as a quantitative analyst at D.E. Shaw and Company, an investment firm in New York City. In 1997 he joined the University of California San Diego, where he is currently a professor of Electrical and Computer Engineering and of Computer Science and Engineering.  His research concerns information theory, statistical modeling, and machine learning.

From 2011 to 2014 Alon directed UCSD's Center for Wireless Communications, and since 2006 he has directed the Information Theory and Applications Center. He is currently the president of the Information Theory Society. He has co-organized numerous programs on information theory, machine learning, and statistics, including the Information Theory and Applications Workshop that he started in 2006 and has helped organize since.

Alon is a recipient of the 1981 ITT International Fellowship and the 1992 IEEE W.R.G. Baker Paper Award, and co-recipient of the 2006 Information Theory Society Paper Award and the 2016 NIPS Paper Award. He is a fellow of the IEEE, and holds the Qualcomm Chair for Information Theory and its Applications at UCSD.

URL: http://alon.ucsd.edu/

Host: Vijay Vazirani (vazirani@cc.gatech.edu)

Ilya Safro - Clemson University

Monday, March 7, 20116
Klaus 1116 West - 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)

Title:
Multiscale Methods for Discrete Optimization on Graphs
Abstract:
In many real-world problems, a big scale gap can be observed between micro- and macroscopic scales of the problem because of the difference in mathematical (engineering, social, biological, physical, etc.) models and/or laws at different scales. The main objective of multigrid-inspired multiscale algorithms is to create a hierarchy of problems, each representing the original problem at different coarse scales with fewer degrees of freedom. We will discuss different strategies of creating these hierarchies for discrete optimization problems on large-scale graphs. These strategies are inspired by the classical multigrid frameworks such as geometric multigrid, algebraic multigrid and full approximation scheme. We will present in details a multiscale framework for linear arrangement, network compression, k-partitioning and clustering, network generation, sparsification, and epidemics response problems. Time permits, a multigrid-inspired algorithm for the support vector machines will be presented.

Url: http://people.cs.clemson.edu/~isafro/

Host: Richard Peng (rpeng@cc.gatech.edu)

Amit Sahai

Friday, April 15, 20116

Klaus 1116 West - 2:00 pm

(Refreshments will be served in Klaus Atrium at 3 pm)

Title:
Hiding Secrets in Software

Abstract:
The goal of general-purpose program obfuscation is to make an arbitrary computer program “unintelligible” while preserving its functionality. Obfuscation allows us to achieve a powerful capability: software that can keep a secret. This talk will cover recent advances in obfuscation research, yielding constructions of general-purpose obfuscation mechanisms based on new mathematical structures.
Bio:

Professor Amit Sahai received his Ph.D. in Computer Science from MIT in 2000. From 2000 to 2004, he was on the faculty at Princeton University; in 2004 he joined UCLA, where he currently holds the position of Professor of Computer Science. His research interests are in security and cryptography, and theoretical computer science more broadly. He is the co-inventor of Attribute-Based Encryption, Functional Encryption, and Indistinguishability Obfuscation. He has published more than 100 original technical research papers at venues such as the ACM Symposium on Theory of Computing (STOC), CRYPTO, and the Journal of the ACM. He has given a number of invited talks at institutions such as MIT, Stanford, and Berkeley, including the 2004 Distinguished Cryptographer Lecture Series at NTT Labs, Japan. Professor Sahai is the recipient of numerous honors; he was named an Alfred P. Sloan Foundation Research Fellow in 2002, received an Okawa Research Grant Award in 2007, a Xerox Foundation Faculty Award in 2010, a Google Faculty Research Award in 2010, and a 2012 Pazy Memorial Award. He was awarded the 2016 Lockheed Martin Excellence in Teaching Award. His research has been covered by several news agencies including the BBC World Service, Quanta Magazine, Wired, and IEEE Spectrum.

Url: http://web.cs.ucla.edu/~sahai/

Host: Lance Fortnow (fortnow@cc.gatech.edu)

David Woodruff - IBM
Tuesday, June 7, 2016
Klaus Conference Room 2100 - 2:00 pm 

Title:
An Optimal Algorithm for Finding L2 Heavy Hitters

Abstract:
We consider the problem of finding the most frequent items in a stream of items from a universe of size n. Namely, we consider returning all l_2-heavy hitters, i.e., those items j for which f_j >= eps sqrt{F_2}, where f_j is the number of occurrences of item j, and F_2 = sum_i f_i^2 is the second moment of the stream. In 2002, Charikar, Chen, and Farach-Colton suggested the CountSketch data structure, which solves this using log^2 n bits of space (for constant eps). The only known lower bound is log n bits. Using Gaussian processes, we show it is possible to achieve an optimal log n bits of space. Our technique resolves a number of other questions in data streams.

Based on work with Vladimir Braverman, Stephen Chestnut, and Nikita Ivkin (STOC '16) and work with Vladimir Braverman, Stephen Chestnut, Nikita Ivkin, Jelani Nelson, and Zhengyu Wang.

Host: Santosh Vempala

Algorithms & Randomness Center (ARC)

Shayan Oveis Gharan – University of Washington

Monday, September 12, 2016

Klaus 1116 East - 11am

Title:  Strongly Rayleigh distributions and their Applications in Algorithm Design

Abstract:

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 0-1 random variables whose generating polynomial is stable. They can be seen as a natural generalization of product distributions. Borcea, Branden and Liggett used the geometry of stable polynomials to prove numerous properties of strongly Rayleigh distributions, including negative association, and closure under conditioning and truncation.
In this talk I will go over basic properties of these distributions, and then I will describe several algorithmic applications.
Based on joint works with Nima Anari, Alireza Rezaei, Mohit Singh, Amin Saberi.

Bio:

Shayan Oveis Gharan is an assistant professor in the computer science and engineering department at University of Washington.  He received his PhD from the MS&E department at Stanford University in 2013 advised by Amin Saberi and Luca Trevisan.  Before joining UW he spent one and a half years as a postdoctoral Miller Fellow at UC Berkeley where his host was Umesh Vazirani. He did his undergraduate studies at the Computer Engineering department at Sharif University.
Shayan's research includes Algorithm design, Graph Theory and Applied Probability.  He received ACM doctoral dissertation award honorable mention for his PhD thesis "New Rounding Techniques for the Design and Analysis of Approximation Algorithms" in 2013. He and his coauthors received best paper awards at SODA 2010 and FOCS 2011 for their works on the Traveling Salesman Problem.

URL: http://homes.cs.washington.edu/~shayan/

Algorithms & Randomness Center (ARC)

Brendan Lucier – Microsoft Research

Monday, October 3, 2016

Klaus 1116 East - 11:00 am

Title:
Prices, Auctions, and Combinatorial Prophet Inequalities

Abstract:
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 decisions using value thresholds. This connection provides an opportunity to use the famous prophet inequality -- which describes the power of threshold rules -- to study pricing problems, and vice-versa. In this talk I'll present a general framework for deriving new prophet inequalities using economic insights from pricing, with algorithmic applications. Along the way, I'll describe an unexpected connection between posted prices and equilibria of non-truthful auctions.

Based on joint works with Paul Duetting, Michal Feldman, Nick Gravin, and Thomas Kesselheim.

Bio:
Brendan Lucier is a Researcher at Microsoft Research, New England. Prior to joining Microsoft, he received his Ph.D. in Computer Science from the University of Toronto. His research interests lie in the intersection of theoretical Computer Science and Economics, and include algorithmic market design, algorithmic pricing, and social processes on networks. He is especially interested in the tradeoffs between simplicity, robustness, and optimality in markets for complex goods and services.

Speaker's webpage

Seminar webpage

Fall 2016 ARC Seminar Schedule

Algorithms & Randomness Center (ARC)

David Karger - MIT

Monday, September 26, 2016
Klaus 1116 East - 11:00 am

Title:
A Fast and Simple Unbiased Estimator for Network (Un)reliability

Abstract:
The following procedure yields an unbiased estimator for the disconnection probability of an n-vertex graph with minimum cut c if every edge fails independently with probability p: (i) contract every edge independently with probability 1-n^{-2/c}, then (ii) recursively compute the disconnection probability of the resulting tiny graph if each edge fails with probability n^{2/c}p.  We give a short, simple, self-contained proof that this estimator can be computed in linear time and has relative variance O(n^2).  Combining these two facts with a relatively standard sparsification argument yields an O(n^3\log n)-time algorithm for estimating the (un)reliability of a network.  We also show how the technique can be used to create unbiased samples of disconnected networks.

Speaker's webpage: http://people.csail.mit.edu/karger/
Fall 2016 ARC Seminar Schedule:  http://arc.gatech.edu/node/114

Algorithms & Randomness Center (ARC)

Ankur Moitra - MIT

Monday, October 31, 2016

Klaus 1116 West – 11:00 am

Title:
Robust Statistics, Revisited

Abstract:
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 are also hard to compute in high-dimensions.

Here, we study a basic problem in robust statistics, posed in various forms in the above works. Given corrupted samples from a high-dimensional Gaussian, are there efficient algorithms to accurately estimate its parameters? We give the first algorithms that are able to tolerate a constant fraction of corruptions that is independent of the dimension. Additionally, we give several more applications of our techniques to product distributions and various mixture models.

This is based on joint work with Ilias Diakonikolas, Jerry Li, Gautam Kamath, Daniel Kane and Alistair Stewart.

Bio:
Ankur Moitra is the Rockwell International Assistant Professor in the Department of Mathematics at MIT and a Principal Investigator in the Computer Science and Artificial Intelligence Lab (CSAIL). The aim of his work is to bridge the gap between theoretical computer science and machine learning by developing algorithms with provable guarantees and foundations for reasoning about their behavior. He is a recipient of a Packard Fellowship, a Sloan Fellowship, an NSF CAREER Award, an NSF Computing and Innovation Fellowship and a Hertz Fellowship.

Algorithms & Randomness Center (ARC)

David Zuckerman – UT Austin

Monday, November 14, 2016

Klaus 1116 East - 11am

Title: 
Explicit Two-Source Extractors and Resilient Functions

Abstract: 
We explicitly construct an extractor for two independent sources on n bits, each with min-entropy 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 extractor, by Bourgain, required each source to have min-entropy .499n.
A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently, and the remaining q=n^{1-\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1/2 - \delta}.
Our explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.
Joint work with Eshan Chattopadhyay.

Bio:   
David Zuckerman holds an Endowed Professorship in the Computer Science Department at the University of Texas at Austin. He received an A.B. in Mathematics from Harvard University in 1987 and a Ph.D. in Computer Science from U.C. Berkeley in 1991. He was a postdoctoral fellow at MIT from 1991-1993, and at Hebrew University in the Fall of 1993. He has been with the University of Texas since then, visiting U.C. Berkeley from 1999-2000, Harvard University from 2004-2005, and the Institute for Advanced Study from 2011-12.
His research focuses primarily on pseudorandomness and the role of randomness in computing. He is best known for his work on randomness extractors and their applications. His other research interests include coding theory, distributed computing, cryptography, inapproximability, and other areas of complexity theory. His research awards include a Simons Investigator Award, a Best Paper Award at STOC 2016, ACM Fellow, a Guggenheim Fellowship, a Packard Fellowship for Science and Engineering, a Sloan Research Fellowship, and an NSF Young Investigator Award.

URL: http://www.cs.utexas.edu/~diz/

Algorithms & Randomness Center (ARC)

Rasmus Kyng - Yale

Monday, November 28, 2016

Klaus 1116 East - 11am

Title:  
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

Abstract:
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 version of Gaussian elimination for positive semi-definite matrices. We compute this factorization by subsampling standard Gaussian elimination. This is the first nearly linear time solver for Laplacian systems that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders. The crux of our proof is the use of matrix martingales to analyze the algorithm.

Bio:
Rasmus Kyng is a PhD student in Computer Science at Yale University, advised by Dan Spielman. Before attending Yale, he received a BA in Computer Science from the University of Cambridge in 2011. His research interests include graph algorithms, applied and theoretical machine learning, and linear systems.

URL: http://www.cs.yale.edu/homes/rjkyng/

Seminar webpage

Fall 2016 ARC Seminar Schedule

Algorithms & Randomness Center (ARC) and

Institute for Data Engineering and Science (IDEaS) present

ARC-IDEaS Distinguished Lecture

Jon Kleinberg - Cornell University

Monday, October 24, 2016

Klaus 1116 at 10 am 

Human Decisions and Machine Predictions

Abstract:
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 machine-learning prediction algorithms to ask several families of questions --- not only about the extent to which algorithms can outperform expert-level human decision-making in specific domains, but also whether we can use algorithms to analyze the nature of the errors made by human experts, to predict which instances will be hardest for these experts, and to explore some of the ways in which prediction algorithms can serve as supplements to human decision-making in different applications.  In this talk, I'll explore this theme by drawing on a line of recent projects; all are joint with Sendhil Mullainathan, and include collaborations with Ashton Anderson, Himabindu Lakkaraju, Jure Leskovec, Annie Liang, and Jens Ludwig. 

Bio:
Jon Kleinberg is the Tisch University Professor in the Departments of Computer Science and Information Science at Cornell University. His research focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other on-line media. He is a member of the National Academy of Sciences, the National Academy of Engineering, and the American Academy of Arts and Science; and he is the recipient of research fellowships from the MacArthur, Packard, Simons, and Sloan Foundations, as well as awards including the Nevanlinna Prize, the Harvey Prize, the Newell Award, and the ACM-Infosys Foundation Award in the Computing Sciences.

Algorithms & Randomness Center (ARC)

Sofya Raskhodnikova - Penn State

Monday, November 7, 2016

Klaus 1116 East - 11am

Title:
Differentially Private Analysis of Graphs

Abstract:
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 transactions, email communication, doctor-patient relationships, and romantic ties. On one hand, such datasets contain sensitive information about individuals. On the other hand, global information that can be gleaned from their analysis can provide significant benefits to society. Several naive attempts at anonymizing sensitive data by stripping obvious identifying information resulted in spectacular failures. In this talk, we discuss algorithms for analyzing network data that satisfy a rigourous notion of privacy called node differential privacy. We present several techniques for designing node differentially private algorithms, based on combinatorial analysis, network flow, and linear and convex programming. 

Based on joint work with A. Smith (FOCS 2016) and with S. Kasiwisvanathan, K. Nissim, A. Smith (TCC 2013) 

Bio:
Sofya Raskhodnikova is an associate professor of Computer Science and Engineering at Penn State. Her research interests include sublinear-time algorithms, private data analysis, approximation algorithms, and randomized algorithms. She got her PhD from MIT in 2003. She has held visiting positions at the Hebrew University of Jerusalem, the Weizmann Institute of Science, the Institute for Pure and Applied Mathematics, Boston University and Harvard University. 
Speaker's webpage: Sofya Raskhodnikova

Algorithms & Randomness Center (ARC)

Alina Ene - Boston University

Monday, October 17, 2016

Klaus 1116 East - 11am

Title:
From Minimum Cut to Submodular Minimization: Leveraging the Decomposable Structure

Abstract:
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 algorithms have high running times and are unsuitable for large-scale problems. Recent work aims to obtain very practical algorithms for minimizing functions that are sums of "simple" functions. This class of functions provides an important bridge between functions with a rich combinatorial structure – notably, the cut function of a graph – and general submodular functions, and it brings along powerful combinatorial structure reminiscent of graphs as well as a fair bit of modeling power that greatly expands its applications. In this talk, we describe recent progress on designing very efficient algorithms for minimizing decomposable functions and understanding their combinatorial structure.

URL: http://cs-people.bu.edu/aene/

Seminar webpage

Fall 2016 ARC Seminar Schedule

A Special Event Celebrating the 10^th Anniversary of Georgia Tech's

Algorithms and Randomness Center

 Monday, October 24 in Klaus 1116

Program Schedule:

9:30     Refreshments

10:00am:   ARC-IDEaS Distinguished Lecture by Jon Kleinberg – Cornell University
                        Title: Human Decisions and Machine Predictions

11:00am:   Break 

11:15am:   Josephine Yu - GT Math 
                         Title: Tropical Geometry in Economics

11:50am:   Mohit Singh - Microsoft/GT ISyE 
                         Title: New Approaches for Constrained Subset Selection Problem

 12:30   Lunch in the Klaus Atrium

(Sponsored by Georgia Tech Colleges of Computing, Engineering, and Sciences, and by Microsoft Research.)

* * * * *

Speaker Abstracts:

Jon Kleinberg – Cornell University

Title:  
Human Decisions and Machine Predictions

Abstract:
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 machine-learning prediction algorithms to ask several families of questions --- not only about the extent to which algorithms can outperform expert-level human decision-making in specific domains, but also whether we can use algorithms to analyze the nature of the errors made by human experts, to predict which instances will be hardest for these experts, and to explore some of the ways in which prediction algorithms can serve as supplements to human decision-making in different applications.  In this talk, I'll explore this theme by drawing on a line of recent projects; all are joint with Sendhil Mullainathan, and include collaborations with Ashton Anderson, Himabindu Lakkaraju, Jure Leskovec, Annie Liang, and Jens Ludwig.

Bio:
Jon Kleinberg is the Tisch University Professor in the Departments of Computer Science and Information Science at Cornell University. His research focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other on-line media. He is a member of the National Academy of Sciences, the National Academy of Engineering, and the American Academy of Arts and Science; and he is the recipient of research fellowships from the MacArthur, Packard, Simons, and Sloan Foundations, as well as awards including the Nevanlinna Prize, the Harvey Prize, the Newell Award, and the ACM-Infosys Foundation Award in the Computing Sciences.

* * * * *

Josephine Yu – Georgia Tech Math

Title:
Tropical Geometry in Economics

Abstract:
In a recent and ongoing work, Baldwin and Klemperer explored a connection between tropical geometry and economics. They gave a sufficient condition for the existence of competitive equilibrium in product-mix auctions of indivisible goods. This result, which we call the Unimodularity Theorem, can also be traced back to the work of Danilov, Koshevoy, and Murota. We will introduce product-mix auctions, prove the Unimodularity Theorem, and discuss integer programming formulations of this problem.  This is based on a joint work with Ngoc Mai Tran.

Bio:
Josephine Yu completed her Ph.D. in mathematics at UC Berkeley in 2007.  After postdoctoral positions at MIT and the Mathematical Sciences Research Institute in Berkeley, she joined the School of Mathematics at Georgia Tech in 2010.  Her research spans combinatorics, computational algebra, and polyhedral and algebraic geometry.

* * * * *

 Mohit Singh – Microsoft / Georgia Tech ISyE

Title:   
New Approaches for Constrained Subset Selection Problem

Abstract:
Selecting a diverse subset of items from a collection occurs as a fundamental problem in various applications including selecting representative documents from a corpus, selecting diverse geographical locations for sensor placement and designing most informative experiments. The problem is modeled by maximizing the entropy of the joint distribution of the selected items and, typically, has additional side constraints. We design approximation algorithms for the subset selection problem with additional partition constraints. Our algorithm relies on efficient polynomial optimization and reveals surprising connections to the problem of counting matchings via the theory of hyperbolic polynomials.

Bio:
Mohit Singh is a researcher in the theory group at Microsoft Research, Redmond and will be joining ISyE, Georgia Tech in January 2017. His research interests include discrete optimization, approximation algorithms and convex optimization. Previously, he was an Assistant Professor at McGill University from 2010-2011 and a post-doctoral researcher at Microsoft Research, New England from 2008-2009. He obtained his Ph.D. from Tepper School of Business, Carnegie Mellon University and his doctoral thesis received the Tucker prize in 2009 given by the Mathematical Optimization Society. He has also received the best paper award for his work on the traveling salesman problem at the Annual Symposium on Foundations of Computer Science (FOCS) 2011.

Lenore Blum

Thursday, October 27, 2016

Howey Physics Building Room L4 at 5pm

Alan Turing and the Other Theory of Computing

Speaker:   Lenore Blum
                  Distinguished Career Professor of Computer Science
                  Carnegie Mellon University (CMU)

Abstract: 

Most logicians and theoretical computer scientists are familiar with Alan Turing’s 1936 seminal paper setting the stage for the foundational (discrete) theory of computation. Most however remain unaware of Turing’s 1948 seminal paper which introduces the notion of condition, setting the stage for a natural theory of complexity for the “other theory of computation.”

Computational mathematics, the “other theory of computation,” emanates from the classical tradition of numerical analysis, equation solving and the continuous mathematics of calculus. 

This talk will recognize Alan Turing’s work in the foundations of numerical computation (in particular, his 1948 paper “Rounding-Off Errors in Matrix Processes”), its influence in complexity theory today, and how it provides a unifying concept for the two major traditions of the Theory of Computation.

Algorithms & Randomness Center (ARC) and

Institute for Information Security & Privacy (IISP) present

ARC-IISP Distinguished Lecture

Manuel Blum

Thursday, October 27, 11am at Klaus 1443

Human Computation with an Application to Passwords

Abstract:
Human computation: This talk presents a simple model of human computation based on well-known features of long and short term human memory. The intention of the model is to bring CS ideas and understanding to bear on the kinds of computations that humans can (and cannot) consciously perform in their heads.

This work has applications to the study of problems that humans might want to solve in their heads, like how to solve crossword puzzles, play speed chess, and various cryptographic problems.

The running example in this talk will be password generation wherein humans - working entirely in their heads - transform website names into random-looking passwords that are provably hard to forge.

——————————

Application to passwords: Nowadays, the best password advice suggests, for each website, to either select and memorize four random picturable words (XKCD), or choose a memorable sentence and use the first letter of every word for the password.

One problem with all such proposals is that they don't indicate how to link website names to passwords. In effect, they would have you generate and memorize a special purpose password for every website. Little wonder that few people do this.

We recommend instead to use a humanly computable algorithm (schema) to transform website names into passwords on the fly. Schemas enable a human to have a (completely) different password for every website, to never have to write passwords down, and to be able to test password quality without giving any passwords away. They also enable us to analyze the Quality of Password Schemas mathematically.

Joint work with Santosh Vempala.
 

David Witmer - CMU

Monday, December 5, 2016

Klaus 1116 East - 11:00 am

Title:
Using the sum of squares hierarchy to refute random CSPs

Abstract:
Consider a random constraint satisfaction problem (CSP) over $n$ variables with $m = Δ n$ constraints, each being a predicate $P$ applied to $k$ random literals. When Δ >> 1$, the instance will be unsatisfiable with high probability, and the natural associated algorithmic task is to find a refutation --- i.e., a certificate of unsatisfiability.  Understanding the density required for average-case refutation is important in various areas of complexity including cryptography, proof complexity, and learning theory.

In this talk, we discuss refutation of random CSPs using the sum of squares (SOS) hierarchy.  The SOS hierarchy is a sequence of semidefinite relaxations parameterized by a value called the degree.  As the degree increases, the relaxation becomes tighter, but the size of its description increases.  We give an overview of recent work proving that the SOS degree required to refute a random instance of CSP$(P)$ is essentially determined by the smallest $t$ for which $P$ does not support a $t$-wise uniform distribution over satisfying assignments.  Specifically, if $P$ fails to support a $t$-wise uniform distribution, our work together with recent work of Raghavendra, Rao, and Schramm shows that degree-$\frac{n}{\Delta^{2/(t-2)}}$ SOS can refute random instances of CSP$(P)$.  Furthermore, this result is tight up to polylogarithmic factors.

This talk is based on joint work with Sarah R. Allen, Pravesh Kothari, Ryuhei Mori, and Ryan O’Donnell.

URL: http://www.cs.cmu.edu/~dwitmer/

Seminar webpage: http://arc.gatech.edu/hg/item/582448

Fall 2016 ARC Seminar Schedule

                         Algorithms & Randomness Center (ARC) and

                                 Machine Learning Group present

                                          ARC - ML Colloquium

               Yin-Tat Lee – University of Washington

                                     Wednesday, November 9

                                     Klaus 1116 East – Noon

Title:    Geodesic Walks

Abstract:
We introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from polytopes in R^n specified by m inequalities. The walk is a discrete-time simulation of a stochastic differential equation (SDE) on the Riemannian manifold. The resulting sampling algorithm for polytopes mixes in O*(mn^{3/4}) steps. This is the first walk that breaks the quadratic barrier for mixing in high dimension, improving on the previous best bound of O*(mn) by Kannan and Narayanan for the Dikin walk. We also show that each step of the geodesic walk (solving an ODE) can be implemented efficiently, thus improving the time complexity for sampling polytopes.