We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding size of the system of equations and in log(1/epsilon), where epsilon > 0 is the desired additive error bound of the solution. (The model of computation is the standard Turing machine model.)
We use this result to resolve several open problems regarding the computational complexity of computing key quantities associated with some classic and heavily studied stochastic processes, including multi-type branching processes and stochastic context-free grammars.
(Joint work with Kousha Etessami and Alistair Stewart.)
Bio:
Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of Computer Science
at Columbia University. Prior to joining Columbia, he was Director of the Computing Principles Research Department at Bell Labs and at Avaya Labs, and Professor of Computer Science at Stanford University.
Dr. Yannakakis received his PhD from Princeton University. His research interests include algorithms, complexity, optimization, game theory, databases, testing and verification. He has served on the editorial boards of several journals, including as the past editor-in-chief of the SIAM Journal on Computing, and has chaired various conferences, including the IEEE Symposium on Foundations of Computer Science, the ACM Symposium on Theory of Computing and the ACM Symposium on Principles of Database Systems.
Dr. Yannakakis is a member of the National Academy of Engineering, a recipient of the Knuth Prize, a Fellow of the ACM, and a Bell Labs Fellow.
]]>
The resilience of networks to various types of failures is an undercurrent in many parts of graph theory and network algorithms. In this paper we study the resilience of networks in the presence of cascading failures — failures that spread from one node to another across the network structure. One finds such cascading processes at work in the kind of contagious failures that spread among financial institutions during a financial crisis, through nodes of a power grid or communication network during a widespread outage, or through a human population during the outbreak of an epidemic disease.
A widely studied model of cascades in networks assumes that each node of the network has an independent random threshold specifying the number of its neighbors that must fail in order for it to fail. It turns out that when selecting among a set of graphs to minimize the failure probability of the most vulnerable node, the optimum graph structure depends quite intricately on the distribution of thresholds. We develop several techniques for minimizing the maximum failure probability among d-regular graphs. For d=2 we are able to solve the problem completely: the optimal graph is always a clique (i.e. triangle) or tree (i.e. infinite path), although which graph is better exhibits a surprising non-monotonicity as the threshold parameters vary. When d is greater than 2 we present a technique based on power-series expansions of the failure probability that allows us to compare graphs in certain parts of the parameter space, deriving conclusions including the fact that as the threshold distribution varies, at least three different graphs are optimal among d-regular graphs. In particular, the set of optimal graphs here includes one which is neither a clique nor a tree.
This is joint work with Larry Blume, David Easley, Jon Kleinberg, and Eva Tardos.
]]>
In 1975, Eaves had given such an algorithm for the case of linear utilities and had asked for an extension to the piecewise-linear, concave case. Our result settles his problem as well as the problem of Vazirani and Yannakakis of obtaining a path following algorithm for SPLC markets, thereby giving a direct proof of membership of this case in PPAD.
We also prove that SPLC markets have an odd number of equilibria (up to scaling), hence matching the classical result of Shapley (1974), which was based on the Lemke-Howson algorithm and shows a similar fact about Nash equilibria of a 2-person bimatrix game.
(This is joint work with Jugal Garg, Milind Sohoni and Vijay V. Vazirani.)
]]>
Program
See Poster for schedule of talks.
See ARC Theory Day Videos here.
]]>Abstract:
Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I'll describe two main aspects of this research on randomness, demonstrating respectively its power and weakness for making algorithms faster. I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.
This is a joint ARC-SoM colloquium, and is in conjunction with the ARC Theory Day on November 11, 2011
4:30 pm - Klaus 1116 E & W
Title: Local correction of codes and Euclidean Incidence Geometry
Abstract:
A classical theorem in Euclidean geometry asserts that if a set of points has the property that every line through two of them contains a third point, then they must all be on the same line. We prove several approximate versions of this theorem, which are motivated from questions about locally correctable codes and matrix rigidity. The proofs use an interesting combination of algebraic and analytic tools.
Joint work with Boaz Barak, Zeev Dvir and Amir Yehudayoff
Avi Wigderson Lecture Video.
]]>
Statistical query (SQ) learning (Kearns, 1993) model is a restriction of Valiant's learning model (1984) that models learning from statistical properties of examples rather than from individual examples. Almost all known learning algorithms can be expressed using statistical queries making the SQ complexity of learning useful in understanding the complexity of learning in general. In addition, SQ learning is closely related to Valiant's (2006) model of evolvability where evolution is modeled as a learning process.
In this talk I will give an overview of the techniques for characterizing and evaluating the SQ complexity of learning and describe two recent applications of these techniques to evolvability. The first application resolves the question of whether Boolean conjunctions are evolvable distribution-independently. The second application gives a simple algorithm for evolving linear threshold functions.
]]>This is a talk in two parts, linked by probabilistic methods and linear algebra. In the first half, we look at the problem of finding all 2-edge cuts in a graph. For this we give a simple algorithm based on uniformly sampling the graph's cycle space (all Eulerian subgraphs). Its distributed implementation is time-optimal on every graph. In the second half, we talk about partitioning set systems into set covers. Mainly, as a function of the minimum degree and maximum set size, how many disjoint covers can be obtained? The tools used to answer this include discrepancy theory and iterated linear programming.
This is joint work with R. Thurimella; and with B. Bollobas, T. Rothvoss, & A. Scott.
]]>For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.
This is joint work with Tobias Momke.
]]>We describe an emerging paradigm, which we refer to as the Laplacian Paradigm, for the design of efficient algorithms for massive graphs. This paradigm is built on a recent collection of nearly-linear-time primitives in Spectral Graph Theory developed by Spielman and Teng. Their key primitive is a solver for a linear system, Ax = b, where A is the Laplacian matrix of a weighted, undirected n-vertex graph and b is an n-dimensional vector. Other primitives include nearly-linear-time algorithms for local clustering, spectral sparsification, and low stretch spanning trees. When applying the Laplacian Paradigm, we reduce the input problem to one or multiple problems that can be efficiently solved by these spectral primitives.
The Laplacian Paradigm has been used in a recent algorithm for computing an approximately maximum s-t flow in an undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows as well as the fastest known algorithm for approximating minimum s-t cut in a graph. The Laplacian paradigm has also been applied to obtain nearly-linear-time algorithms for applications in semi-supervised learning, image process, web-spam detection, eigenvalue approximation, and for solving elliptic finite element systems.
Recently, almost all original primitives in this collection including the Laplacian solver itself have been significantly improved. Practical implementation might become available in the near future. The goal of this presentation is to encourage more researchers to consider the use of the Laplacian Paradigm to develop faster algorithms for solving fundamental problems in combinatorial optimization, scientific computing, machine learning, network analysis, and other applications that involve massive graphs.
Joint work with Daniel Spielman (Yale) and Paul Christiano (MIT), Jonathan Kelner (MIT), and Aleksander Madry (MIT).
]]>