DIMACS Theory of Computing Seminar - Spring 2013
|
 |
Organizer(s) | , Eric Allender, Yixin Xu | Archive | |
Website | http://paul.rutgers.edu/~yixinxu/theory-spring13.html |
Past Talks
Wednesday, May 1st |
Ali Kemal Sinop, Princeton University |
"Towards a better approximation for Sparsest Cut?" |
| Time: 11:00 AM |
| Location: Core 431 |
| Abstract: We give a new $(1+eps)$-approximation for sparsest cut problem
on graphs where small sets expand significantly more than the sparsest
cut (sets of size $n=r$ expand by a factor $sqrt{log n log r}$ bigger,
for some small $r$; this condition holds for many natural graph families).
We give two different algorithms. One involves Guruswami-Sinop rounding
on the level-r Lasserre relaxation. The other is combinatorial and involves
a new notion called Small Set Expander Flows (inspired by the expander
flows of [ARV09]) which we show exists in the input graph. Both algorithms
run in time $2^{O(r)} poly(n)$.
We also show similar approximation algorithms in graphs with genus $g$ with an analogous local expansion condition. This is the first algorithm we know of that achieves $(1+eps)$-approximation on such general family of graphs. Joint work with Sanjeev Arora and Rong Ge. |
Wednesday, April 24th |
Shi Li, Princeton University |
"Approximating $k$-Median via Pseudo-Approximation" |
| Time: 11:00 AM |
| Location: Core 431 |
| Abstract: We present a novel approximation algorithm for $k$-median that achieves an approximation guarantee of
$1+sqrt{3}+epsilon$, improving upon the decade-old ratio of $3+epsilon$. Our approach is based on
two components, each of which, we believe, is of independent interest.
First, we show that in order to give an $alpha$-approximation algorithm for $k$-median, it is sufficient to give a emph{pseudo-approximation algorithm} that finds an $alpha$-approximate solution by opening $k+O(1)$ facilities. This is a rather surprising result as there exist instances for which opening $k+1$ facilities may lead to a significant smaller cost than if only $k$ facilities were opened. Second, we give such a pseudo-approximation algorithm with $alpha=1+sqrt{3}+epsilon$. Prior to our work, it was not even known whether opening $k + o(k)$ facilities would help improve the approximation ratio. |
Wednesday, April 17th |
Oded Regev, Courant Institute, NYU |
"Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication" |
| Time: 11:00 AM |
| Location: Core 431 |
| Abstract: In STOC 1999, Raz presented a (partial) function for which there is a
quantum protocol communicating only $O(log n)$ qubits, but for which
any classical (randomized, bounded-error) protocol requires $n^eps$
bits of communication. That quantum protocol requires two rounds of
communication. Ever since Raz's paper it was open whether the same
exponential separation can be achieved with a quantum protocol that
uses only one round of communication. In other words, can quantum
one-way communication be exponentially stronger than classical two-way
communication? Here we settle this question in the affirmative.
The talk is entirely self-contained. In particular, there is no need to be familiar with quantum communication (since it barely shows up in our proof). Based on joint work with Bo'az Klartag. |
Wednesday, April 3rd |
Bahman Kalantari, Rutgers University |
"An Algorithmic Separating Hyperplane Theorem and Its Applications" |
| Time: 11:00 AM |
| Location: Core 431 |
| Abstract: We first prove a new separating hyperplane theorem for compact convex subsets of the Euclidean space, distinct from classical theorems which are essentially existential rather than algorithmic. Next, utilizing this theorem, we develop a substantially generalized version of the Triangle Algorithm to perform either one of the following tasks: (i) To approximate the Euclidean distance between given compact convex subsets K, K’ by computing a pair (p, p’) in K x K’, where d(p, p’) is within prescribed tolerance of d(K, K’); (ii) When K and K’ are disjoint, to compute a separating hyperplane; (iii) When K and K’ are disjoint, to compute a pair of parallel supporting hyperplanes whose distance is within prescribed error of the largest possible margin. The main work in each iteration is the optimization of a linear function over K or K’. The resulting algorithm is a fully polynomial-time approximation scheme for such special cases as when each set is the convex hull of a finite point set or the intersection of a finite number of halfspaces. The results find many applications such as in machine learning, statistics, linear, quadratic, and convex programming. The Triangle Algorithm is more general than the existing algorithms, developed only for special cases of the problem, e.g. Gilbert's algorithm (equivalently, Frank-Wolfe, sparse greedy approximation) and distinct from them. Our results can also be used to provide a certain approximation to NP-complete problems when appropriately formulated. |
Wednesday, March 27th |
Jing Chen, IAS |
" Leveraging Higher-Order Beliefs in Mechanism Design" |
| Time: 11:00 AM |
| Location: Core 431 |
| Abstract: In a setting of incomplete information, we model the hierarchy of the
players' beliefs about each other's payoff types in a set-theoretic way. A
player's beliefs can be totally arbitrary, and the beliefs of different
players can be inconsistent with each other.
In single-good auctions, for k=0, 1, ... , we define a revenue benchmark $G^k$ on the players' belief hierarchy. Intuitively, $G^k$ is greater than or equal to v if and only if there exist at least two players "believing that there exists a player ..." (k times) valuing the good at least v. We construct an interim individually rational mechanism M that, without any clue about the players' beliefs and their rationality level, virtually guarantees revenue $G^k$ whenever the players happen to be level-(k+1) rational. We also separate the revenue achievable with level-k and level-(k+1) rational players. For every non-negative k, we show that no interim individually rational mechanism can virtually guarantee revenue $G^k$ when the players' rationality level is k instead of k+1. |
Wednesday, March 13th |
Sushant Sachdeva, Princeton University |
"Near-linear time algorithms for Balanced Separator by simulating random walks" |
| Time: 11:00 AM |
| Location: Core 431 |
| Abstract: The goal of the Balanced Separator problem is to cut a graph into two
roughly equal parts, while minimizing the number of edges cut. It is a
fundamental problem, both in theory and practice. Given the massive
size of several graphs of interest today (e.g. the web graph), we
would like near-linear time algorithms for this problem. In this talk,
we present the first such algorithm with an approximation guarantee
that's optimal for spectral algorithms.
We first show how to reduce the question of finding a good balanced cut to simulating poly-logarithmic number of continuous-time random walks, using techniques from semi-definite programming, and matrix exponential updates. Next, we give a near-linear time algorithm to approximately simulate the required random walks (equivalent to approximating the matrix exponential e^(-tL), where L is the graph Laplacian). We show how to achieve such an approximation using rational functions, techniques from numerical linear algebra, and the near-linear time Laplacian system solver by Spielman and Teng. This is joint work with Lorenzo Orecchia and Nisheeth K. Vishnoi. |
Wednesday, March 6th |
Mikkel Thorup, AT&T |
"The Power of Tabulation Hashing" |
| Time: 11:00 AM |
| Location: CoRe 431 |
| Abstract: Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to Carter and Wegman (STOC '77).Keys are viewed as consisting of c characters. We initialize c tables T1,�^��,Tc mapping characters to random hash codes. A key x=(x1,�^��,xc) is hashed to T1[x1] xor �^�� xor Tc[xc]. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., min-wise hashing for estimating set intersection, and cuckoo hashing. We shall also discuss a twist to simple tabulation that leads to reliable statistics with Chernoff-type concentration and extremely robust performance for linear probing with small buffers. |
Wednesday, February 20th |
Or Meir, IAS |
"IP = PSPACE via error correcting codes" |
| Time: 11:00 AM |
| Location: CoRE 301-A |
| Abstract: The IP theorem, which asserts that IP = PSPACE (Lund et. al., and
Shamir, in J. ACM 39(4)), is one of the major achievements of
complexity theory. The known proofs of the theorem are based on the
arithmetization technique, which transforms a quantified Boolean
formula into a related polynomial. The intuition that underlies the
use of polynomials is commonly explained by the fact that polynomials
constitute good error correcting codes. However, the known proofs seem
tailored to the use of polynomials, and do not generalize to arbitrary
error correcting codes.
In this work, we show that the IP theorem can be proved by using general error correcting codes. We believe that this establishes a rigorous basis for the aforementioned intuition, and sheds further light on the IP theorem. |
Wednesday, February 13th |
Ilya Volkovich, Technion-Israel Institute of Technology |
"Black-Box Identity Testing Of Depth-4 Multilinear Circuits" |
| Time: 11:00 AM |
| Location: CoRe 431 |
| Abstract: A central problem in algebraic complexity theory and algorithms design
is the problem of Polynomial Identity Testing (PIT): given an arithmetic
circuit $C$ over a field $F$, with input variables $x_1, x_2, ... , x_n$,
determine whether $C$ computes the identically zero polynomial. Numerous
applications and connections to other algorithmic and number theoretic problems
further emphasize the significance of PIT. Among the examples are algorithms
for finding perfect matchings in graphs cite{Lovasz79,MVV87}, primality
testing cite{AKS04}, and many more. We study the problem of PIT for multilinear
$Sigma Pi Sigma Pi (k) $ circuits, i.e. multilinear depth-4 circuits with
fan-in k at the top + gate. We give the first polynomial-time deterministic
PIT algorithm for such circuits. Our results also hold in the black-box setting.
The importance of this model arises from cite{AgrawalVinay08}, where it was
shown that derandomizing black-box polynomial identity testing for general depth-4
circuits implies a derandomization of polynomial identity testing (PIT) for
general arithmetic circuits. We obtain our results by showing a strong structural
result for multilinear $Sigma Pi Sigma Pi (k) $ circuits that compute
the zero polynomial.
This is joint work with Shubhangi Saraf. |
Wednesday, February 6th |
Krzysztof Onak , IBM Research |
"Superlinear lower bounds for multipass graph processing" |
| Time: 11:00 AM |
| Location: Core 431 |
| Abstract: I will present n^(1+Omega(1/p)) lower bounds for the space complexity of p-pass
streaming algorithms for the following problems on n-vertex graphs:
* computing maximum matching size, * testing if two specific vertices are at distance at most 2(p+1), * testing if there is a directed path between two specific vertices. Before our result, it was known that these problems require Omega(n^2) space in one pass, but no n^(1+Omega(1)) lower bound was known for any p >= 2. Our result follows from a communication complexity lower bound for a communication game in which the players hold two graphs on the same set of vertices. The task of the players is to find out whether the sets of vertices reachable from a specific vertex in exactly p+1 steps intersect. The game requires a significant amount of communication only if the players are forced to speak in a specific difficult order. Joint work with Venkat Guruswami. http://arxiv.org/abs/1212.6925 |
Wednesday, January 30th |
Stefan Langerman, Universite Libre de Bruxelles |
"From Irreducible Representations to Locally Decodable Codes" |
| Time: 11:00 AM |
| Location: Core 431 |
| Abstract: A q-query Locally Decodable Code (LDC) is an error-correcting code that allows reading any
particular symbol of the message by reading only q symbols of the codeword.
In this talk we present a new approach for the construction of LDCs from representation theory. We show that if there exists an irreducible representation (rho, V) of the group G and q elements g_1,g_2,..., g_q in G such that there exists a linear combination of matrices rho(g_i) that is of rank one, then we can construct a q-query Locally Decodable Code C:V -> F^G. We will show that both matching vector codes and Reed-Muller codes fall in this framework. No prior knowledge in representation theory will be assumed. |
Wednesday, January 23rd |
Raghu Meka, DIMACS, Rutgers University |
"A PTAS for Computing the Supremum of Gaussian Processes" |
| Time: 11:00 AM |
| Location: Core 431 |
| Abstract: We give a polynomial time approximation scheme (PTAS) for computing the supremum of a Gaussian process. Previously, only a constant factor deterministic polynomial time approximation algorithm was known due to the work of Ding, Lee and Peres. This answers an open question of Lee and Ding. The study of supremum of Gaussian processes is of considerable importance in probability with applications in functional analysis, convex geometry, and in light of the recent work of Ding, Lee and Peres, to random walks on finite graphs. As such our result could be of use elsewhere. In particular, combining with the recent work of Ding, our result yields a PTAS for computing the cover time of bounded degree graphs. Previously, such algorithms were known only for trees. Along the way, we also give an explicit oblivious linear estimator for semi-norms in Gaussian space with optimal query complexity. |