**Algorithms & Randomness Center (ARC) **

**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.