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)
The recent explosion in the size of stored data, partially due to advances in storage technology, and partially due to the growing popularity of cloud-computing and the vast quantities of data generated, motivates the need for streaming algorithms that can compute approximate solutions without full random access to all of the data. We address the problem of computing a balanced k-partitioning of a graph with only one pass over the data, modeling how data is loaded onto a distributed system. I will first discuss some experimental results on a variety of simple algorithms. I will then provide a randomized analysis for two of the best performing algorithms on a random graph model with a good embedded k-cut, giving clear intuition for the difference in the performance between these algorithms.
In this talk, we consider some fundamental maximum throughput routing problems in directed graphs. In this setting, we are given a capacitated directed graph. We are also given source-destination pairs of nodes (s_1, t_1), (s_2, t_2), …, (s_k, t_k). The goal is to select a largest subset of the pairs that are simultaneously routable subject to the capacities; a set of pairs is routable if there is a multicommodity flow for the pairs satisfying certain constraints that vary from problem to problem (e.g., integrality, unsplittability, edge or node capacities). Two well-studied optimization problems in this context are the Maximum Edge Disjoint Paths (MEDP) and the All-or-Nothing Flow (ANF) problem. In MEDP, a set of pairs is routable if the pairs can be connected using edge-disjoint paths. In ANF, a set of pairs is routable if there is a feasible multicommodity flow that fractionally routes one unit of flow from s_i to t_i for each routed pair (s_i, t_i).
MEDP and ANF are both NP-hard and their approximability has attracted substantial attention over the years. Over the last decade, several breakthrough results on both upper bounds and lower bounds have led to a much better understanding of these problems. At a high level, one can summarize this progress as follows. MEDP and ANF admit poly-logarithmic approximations in undirected graphs if one allows constant congestion, i.e., the routing violates the capacities by a constant factor. Moreover, these problems are hard to approximate within a poly-logarithmic factor in undirected graphs even if one allows constant congestion. In sharp contrast, both problems are hard to approximate to within a polynomial factor in directed graphs even if a constant congestion is allowed and the graph is acyclic.
In this talk, we focus on routing problems in directed graphs in the setting in which the demand pairs are symmetric: the input pairs are unordered and a pair s_i t_i is routed only if both the ordered pairs (s_i,t_i) and (t_i,s_i) are routed. Perhaps surprisingly, the symmetric setting can be much more tractable than the asymmetric setting. As we will see in this talk, when the demand pairs are symmetric, ANF admits a poly-logarithmic approximation with constant congestion. We will also touch upon some open questions related to MEDP in directed graphs with symmetric pairs.
This talk is based on joint work with Chandra Chekuri.
Cryptographic bilinear maps have been used to solve many interesting problems in cryptography. It has also been known for some time that hypothetical multilinear maps could be used to solve an even wider range of problems. However, until very recently, no such construction of multilinear maps was known. In this talk, I will discuss some of the many uses of multilinear maps, and present a construction due to Coron, Lepoint, and Tibouchi.
Delaunay triangulations are a classical data structure in computational geometry. From a theoretical perspective algorithms covering all major construction paradigms have been proposed and in practice they are used in Computer Graphics for mesh refinement and interpolation and in Scientific Computing for the Finite Element Method. However, deletions in Delaunay triangulations lack the same extensive treatment. While in 2D fast algorithms (both in theory and in practice) exist, there is notable room for improvement in 3D deletions. We explain why the 3D case is harder to solve than 2D and present an algorithm for deleting vertices from a 3D that runs in O(|P| + C*(P)) time, where P is the set of incident vertices to the deleted vertex and C*(P) is an upper bound on the expected number of tetrahedra whose circumspheres enclose the deleted vertex that are created during the randomized incremental reconstruction of the triangulation. Both terms are an improvement over existing methods. We have implemented several variations of the algorithm and show that we decrease the wall clock time in practice too.
The phenomenon of correlation decay, inspired from the statistical physics notion of uniqueness of Gibbs measure, has recently enjoyed much popularity in the design of approximation algorithms for problems such as counting independent sets; part of which is due to the fact that deterministic algorithms based on correlation decay are known to provably work in several regimes in which randomized MCMC algorithms cannot (yet) be proved to work. The impetus for this technique came initially from the work of Weitz (STOC 06) who showed that for the so-called hard core model (a distribution on independent sets in which each independent set I has weight lambda^|I| for some fixed positive parameter lambda called the "fugacity"), decay of correlations on the infinite d-regular tree implies decay of correlations and an FPTAS for the partition function on all graphs of degree at most d. This connection between decay of correlations and the complexity of approximate counting was further strengthened in the work of Sly (FOCS 2010) who showed that when decay of correlations does not hold on the d-regular tree, the problem becomes NP-hard on graphs of degree at most d. Several subsequent results strengthened this relationship between correlation decay and the complexity of counting for various "repulsive" models such as the hard core model and the anti-ferromagnetic Ising model; however, all of the algorithmic results dealt with the case of bounded degree graphs, often relating the complexity of approximate counting on graphs of degree at most d to the regime of correlation decay.
In our work, we go beyond the maximum degree by showing an intimate connection between the connective constant of a graph and the phenomenon of decay of correlations for the hard core model. The connective constant is a well studied notion of the average degree of a graph, and is roughly related to the rate of growth of the number of self-avoiding walks in the graph, as a function of the length of such walks. In particular, we show that decay of correlations on the (d+1)-regular tree implies decay of correlations on any graph of connective constant at most d, irrespective of its maximum degree, and hence derive an FPTAS for the partition function of the hard core model on such graphs. As an application, we show that the partition function can be efficiently approximated with high probability on graphs drawn from the random graph model G(n,d/n) for all \lambda < e/d (which was conjectured to be optimal), even though the maximum degree of such graphs is unbounded with high probability.
We also improve upon Weitz's bounds for decay of correlations on bounded degree graphs (Weitz, STOC 06). In particular, we provide a computationally simple method which uses known estimates of the connective constant of a lattice to obtain bounds on the vertex activities lambda for which the hard core model on the lattice exhibits decay of correlations. Using this framework, we improve upon these bounds for several lattices including the Cartesian lattice in dimensions 3 and higher. In contrast to similar results of Restrepo, Shin, Tetali, Vigoda and Yang (FOCS 2011) for the 2-dimensional Cartesian lattice, our methods do not depend upon intensive computer assisted calculations.
Joint work with Alistair Sinclair and Yitong Yin.
We consider the design of consensus processes for finding "the wisdom of the crowd". Specifically, given a set of proposals, we would like to find the (generalized) median when relationships between proposals cannot be calculated by a centralized algorithm. In such a scenario, a mechanism must be designed that induces the participants to "find" the desired proposal themselves.
We propose an urn-based mechanism, which reduces this problem to consensus processes among groups of three. In each of these triads, participants take part in a mechanism which returns an intermediate consensus proposal. When participants form a median graph (e.g. trees, grids, squaregraphs), we show that the urn process converges to a (1+O(\sqrt{\frac{\log n}{n}}))-approximation of the true median with high probability, while only requiring an average of O(\log n) triadic interactions per participant. Moreover, the strategy that implements the desired result in each triad is a Nash equilibrium.
Finally, we prove an impossibility result which highlights the importance of triads. Namely, if our urn-based reduction is modified to use groups of two, then there is no two person consensus mechanism satisfying certain intuitive properties which can find a good approximation of the median for a simple example.