# Stanford CS Theory Lunch

## Logistics

Time: Thursdays, typically 12:30pm to 1:00pm (food starts at 12:15pm)

Location: Gates 4B lobby.

Contact: Kevin Lewi (klewi at cs dot stanford dot edu)

## Fall 2013--2014 Schedule

• (9/26) Organizational Meeting
• (10/3) Don Knuth (Stanford): Some Useful and Not-Too-Hard Asymptotic Estimates
• (10/10) Yash Deshpande (Stanford): Planted Cliques, Iterative Thresholding and Message Passing Algorithms

Consider an Erdos-Renyi random graph on $n$ vertices constructed as follows. Each edge exists with probability 1/2, except for within a set of vertices of size $k$, which forms a clique (or complete subgraph). A simple argument yields that the planted clique is identifiable by exhaustive search as long as $k \ge 2\log n$. However, no computationally efficient algorithm is known to succeed for $k=o(\sqrt n)$. Further, the best available guarantees are due to spectral methods, which do not exploit the fact that the size of the clique is sublinear. I will describe an iterative algorithm based on belief propagation that provably finds cliques of size $k =\sqrt{n/e}$, which is beyond simple spectral methods.

This is joint work with Andrea Montanari.

• (10/17) Ankit Sharma (CMU): Multiway Cut

Multiway cut is a generalization of the min-cut problem to one with more than two terminals. Theoretically, given a set of terminals in a graph, the objective is to assign each vertex to some terminal while minimizing the number of 'cut' edges -- edges whose end points are assigned to different terminals. The special case of this problem with two terminals is the "max-flow/min-cut problem". With three or more terminals, the problem is NP hard.

The problem has a rich history in approximation algorithms. Starting with a 2-approximation by Dahlhaus et al. in 1994, the problem received a major improvement in a paper by Calinescu et al., where they presented a relaxation of the problem, and a 1.5 approximation to it. It was subsequently shown that it is UGC hard to beat the integrality gap of this relaxation. The rounding schemes to the relaxation were also subsequently improved, and in a recent result, Buchbinder et al. in STOC 2013, introduced a new rounding scheme that gave a 1.32388 approximation. In a work with Jan Vondrak, we first present the best combination of rounding schemes used by Buchbinder et al., and show that it is limited to achieving a factor of 1.30902 (=(3+sqrt(5))/4). We then introduce a new rounding scheme and show that the new combination of rounding schemes achieves an approximation factor close to 1.297. Under UGC, it is NP hard to go below 1.14.

This is a joint work with Jan Vondrak.

• (10/24) Huacheng Yu (Stanford): Finding orthogonal vectors in discrete structures

Hopcroft's problem in d dimensions asks: given n points and n hyperplanes in R^d, does any point lie on any hyperplane? Equivalently, if we are given two sets of n vectors each in R^{d+1}, is there a pair of vectors (one from each set) that are orthogonal? This problem has a long history and a multitude of applications. It is widely believed that for large d, the problem is subject to the curse of dimensionality: all known algorithms need at least f(d)n^{2-1/O(d)} time for fast-growing functions f, and at the present time there is little hope that a n^{2-eps}poly(d) time algorithm will be found.

We consider Hopcroft's problem over finite fields and integers modulo composites, leading to both surprising algorithms and hardness reductions. The algorithms arise from studying the communication problem of determining whether two lists of vectors (one list held by Alice, one by Bob) contain an orthogonal pair of vectors over a discrete structure (one from each list). We show the randomized communication complexity of the problem is closely related to the sizes of matching vector families, which have been studied in the design of locally decodable codes. We give randomized algorithms and almost matching lower bounds (modulo a breakthrough in SAT algorithms) for Hopcroft's problem over a ring R, when R is the ring of integers modulo m or a finite field.

Building on the ideas developed here, we give a very simple and efficient output-sensitive algorithm for matrix multiplication that works over any field.

• (10/31) Eric Price (Simons Institute): Fourier Sampling and Beyond

The Fast Fourier Transform (FFT) is a fundamental algorithm that computes the Discrete Fourier Transform of an n-dimensional signal in O(n log n) time. It is unknown whether the running time can be improved in general. However, in applications such as image, audio, and video compression where the output is "sparse" (i.e., k << n coordinates are "large" and contain most of the energy), it is possible to estimate the large coordinates in less than O(n log n) time. This talk will describe two related algorithms, one achieving the best known time complexity and the other achieving the best known sample complexity.

Based on http://arxiv.org/abs/1201.2501 (STOC 2012) and http://www.mit.edu/~ecprice/papers/fouriermeasurements.pdf (SODA 2014).

• (11/7) Vasilis Gkatzelis (Stanford): Decentralized Utilitarian Mechanisms for Scheduling Games

Game Theory and Mechanism Design are by now standard tools for studying and designing massive decentralized systems. Unfortunately, designing mechanisms that induce socially efficient outcomes often requires full information and prohibitively large computational resources. In this work we study simple mechanisms that require only local information. Specifically, in the setting of a classical scheduling problem, we demonstrate local mechanisms that induce outcomes with social cost a small constant times that of the socially optimal solution. Somewhat counter-intuitively, we find that mechanisms yielding Pareto dominated outcomes may in fact enhance the overall performance of the system, and we provide a justification of these results by interpreting these inefficiencies as externalities being internalized. We also show how to employ randomization to obtain yet further improvements. Lastly, we use the game-theoretic insights gained to obtain a new combinatorial approximation algorithm for the underlying optimization problem.

Joint work with R. Cole, J. Correa, V. Mirrokni, and N. Olver. Appeared at STOC '11 and Games and Economic Behavior.

• (11/14) Ryan Williams (Stanford): Faster all-pairs shortest paths via circuit complexity

The good old all-pairs shortest path problem in dense n-node directed graphs with arbitrary edge weights (APSP) has been known for 50 years (by Floyd and Warshall) to be solvable in O(n^3) time on the real RAM, where additions and comparisons of reals are unit cost (but all other operations have typical logarithmic cost). Faster algorithms (starting with Fredman in 1975) take n^3/(log^c n) time for various c <= 2. It's a longstanding open problem if APSP can be solved in n^{3-eps} time for some eps > 0. A first step is to determine if even n^3/(log^c n) time can be achieved, for *every* c.

I will outline a new method for computing the min-plus product (a.k.a., tropical product) of two n by n matrices, yielding a faster algorithm for APSP. On the real RAM, the algorithm runs in time O(n^3/2^{(log n)^{delta}}) for any delta > 1/2. The algorithm applies tools from low-level circuit complexity

• (11/21) Jaehyun Park (Stanford): Proximal minimization algorithm for the least squares problem

Solving a linear system of equations is of great interest in many applications, including machine learning. Typically, the number of data points is larger than the dimension of the data. In general, such a system does not have an exact solution, so one often wants to find the "least squares" solution, that minimizes |Xb-y|, with data X, y, and variable b.

Sometimes, the given data may be ill-conditioned, and attempting to directly solve such a system may introduce huge numerical error. A popular solution to get around this issue is to add a regularizer to the objective function. While this can improve the robustness of the solution, it can hurt the quality of it.

We discuss an iterative method for solving a regularized system, and how it can be extended to solve the original system without the regularizer.

This is a joint work with Sham Kakade, Rong Ge (MSR-NE).

• (12/5) Amir Abboud (Stanford): Popular conjectures imply strong lower bounds for dynamic problems.

We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough algorithm for one of five fundamental (static) problems in the theory of algorithms: CNF-SAT, 3SUM, all pairs shortest paths, triangle detection and boolean matrix multiplication.

The problems we consider include dynamic versions of bipartite perfect matching, single source reachability, strong connectivity, subgraph connectivity and diameter approximation.

Joint work with Virginia Vassilevska Williams.

Also check here for the Google calendar.

For previous quarter talks see theory lunch archives.