Location: Gates 4B lobby.
Mailing list: thseminar@cs.stanford.edu. Email Kevin to sign up.
Contact: Kevin Lewi (klewi at cs dot stanford dot edu)
Finding non-trivial lower bounds for well known problems (such as the all pairs shortest paths problem and the 3SUM problem) have been unsuccessful in unrestricted models of computation. I will be presenting some of the reductions from Ryan and Virginia Williams' paper in 2010 about equivalences established between some of these problems in P. One major goal is to establish relations between problems that are "subcubic"-hard and problems that are "subquadratic"-hard.
We consider two well-studied constants in Fourier analysis and high-dimensional geometry and make progress towards determining their exact values.
1. It has been known since 1994 (Gotsman and Linial) that every linear threshold function has squared Fourier mass at least $1/2$ on its degree-$0$ and degree-$1$ coefficients. Denote the minimum such Fourier mass by \lambda(LTF) where the minimum is taken over all $n$-variable linear threshold functions and all $n \ge 0$, O'Donnell has conjectured that the true value of $\lambda(LTF)$ is $2/\pi$.
We make progress on this conjecture by proving that $\lambda(LTF) \geq 1/2 + c$ for some absolute constant $c>0$. The key ingredient in our proof is a ``robust'' version of the well-known Khintchine-Kahane inequality in functional analysis, which we believe may be of independent interest.
2. We give an algorithm with the following property: given any $\eta > 0$, the algorithm runs in time $2^{\poly(1/\eta)}$ and determines the value of $\lambda(LTF)$ up to an additive error of $+- \eta$. We give a similar $2^{2^{\poly(1/\eta)}}$-time algorithm to determine Tomaszewski's constant to within an additive error of $+- \eta$; this is the minimum (over all origin-centered hyperplanes $H$) fraction of points in $\{-1,1\}^n$ that lie within Euclidean distance $1$ of $H$. Tomaszewski's constant is conjectured to be $1/2$; lower bounds on it have been given by Holzman and Kleitman and independently by Ben-Tal, Nemirovski and Roos. Our algorithms combine tools from anti-concentration of sums of independent random variables, Fourier analysis, and Hermite analysis of linear threshold functions.
Joint work with Ilias Diakonikolas and Rocco Servedio.
We describe a new pseudorandom generator for AC0. Our generator -fools circuits of depth d and size M and uses a seed of length O(logd+4M) . The previous best construction for d3 was due to Nisan, and had seed length O(log2d+6M). A seed length of O(log2d+(1)M) is best possible given Nisan-type generators and the current state of circuit lower bounds; Seed length (logdM) is a barrier for any pseudorandom generator construction given the current state of circuit lower bounds. For d=2, a pseudorandom generator of seed length O(log2M) was known.
Our generator is based on a ``pseudorandom restriction'' generator which outputs restrictions that satisfy the conclusions of the Hastad Switching Lemma and that uses a seed of polylogarithmic length.
In the Multicast problem, we are given graph G(V,E) which represents a telephone network, where there can be a phone call between two nodes if there is an edge between them. We are also given a source vertex and a set of terminals R. The source vertex has a message and it wants to inform all the terminals from the message. To do this, the vertices of the graph can communicate in rounds: In each round, we pick a matching of G and arrange a bidirected phone call between each vertex in the matching and its match. If any of the two vertices knows the message before the phone call, the other one will also know it afterwards. The goal is to deliver the message to all the terminals in the minimum number of rounds. We present approximation algorithms for the Multicast problem and its generalization.
In the oracle interrogation problem, we are allowed to make q queries to an unknown oracle H, and attempt to produce k input/output pairs of H. If only classical queries are allowed, then this problem is trivial when q is at most k, but impossible otherwise.
Once we allow queries on a quantum superposition of inputs, however, little was previously known. In our recent paper, we introduce a new quantum lower bound technique, called the Rank Method, and use it to prove exact lower bounds for the oracle interrogation problem in the quantum world. In this talk, I will give the intuition behind the Rank Method and some applications.
Lattice problems often arise in a number of applications, including cryptography. Thus, establishing complexity bounds on lattice problems is an important (and interesting) research area. In this talk we will review the current state of the complexity of one lattice problem, the approximate gap closest vector problem, and show how we can simplify current proofs of complexity using more recent Gaussian sampling techniques over lattices. We will also show how, if current Gaussian sampling algorithms could be improved, the overall result could be strengthened. This is joint work with Dan Boneh.
I describe a new technique that gives very simple proofs of new and known results concerning the eigenvalues of the Laplacian of finite graphs and the spectral measure of infinite graphs, such as Cayley graphs. These in turn immediately yield bounds on the return probabilities of random walks. One application is a sublinear time algorithm to approximate the number of spanning trees of large graphs. This is based on a joint work with Russell Lyons.