Fall 2011

ABSTRACT: In Computer Science and Applied Mathematics, we often represent a graph by its adjacency matrix. This linear algebraic view of graphs can be very useful. For example, it has facilitated the design of the fast algorithm for the shortest path problem and the introduction of PageRank.

In this talk, I focus on the Laplacian matrix, a simple modification of the adjacency matrix. The Laplacian matrix had been extensively used for partitioning graphs that arise in VLSI design and high-performance computing. As the starting point of our discussion, I will show that every Laplacian matrix can be inverted efficiently, that is, the linear system Ax = b, where A is the Laplacian matrix, can be solved in nearly linear time. I then 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 the nearly-linear time Laplacian solver as well as a few other algorithms (such as for local clustering and high quality spanning trees) developed for supporting this solver.

I will discuss some recent progress in applying the Laplacian paradigm. Our first example will be the nearly linear time solution to a problem that we all learned in high school, that is, to determine the electrical flows in a circuit of resistors. We then show by solving a sequence of electrical flow problems we obtain the fastest algorithm for computing an approximate maximum s-t flow in an undirected graph. Recently, significant improvements have been made to the Laplacian solver and 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).

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 limits 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.

ABSTRACT: We argue that a general theory of trust in networks of humans and computers must be build on both a theory of behavioral trust and a theory of computational trust. This argument is motivated by increased participation of people in social networking, crowdsourcing, human computation, and socio-economic protocols, e.g., protocols modeled by trust and gift-exchange games, norms-establishing contracts, and scams/deception. User participation in these protocols relies primarily on trust, since on-line verification of protocol compliance is often impractical; e.g., verification can lead to undecidable problems, co-NP complete test procedures, and user inconvenience. Trust is captured by participant preferences (i.e., risk and betrayal aversion) and beliefs in the trustworthiness of other protocol participants. Both preferences and beliefs can be enhanced whenever protocol non-compliance leads to punishment of untrustworthy participants; i.e., it seems natural that betrayal aversion can be decreased and belief in trustworthiness increased by properly defined punishment. We argue that a general theory of trust should focus on the establishment of new trust relations where none were possible before. This focus would help create new economic opportunities by increasing the pool of usable services, removing cooperation barriers among users, and at the very least, taking advantage of “network effects.” Hence a new theory of trust would also help focus security research in areas that promote trust-enhancement infrastructures in human and computer networks. Finally, we argue that a general theory of trust should mirror, to the largest possible extent, human expectations and mental models of trust without relying on false metaphors and analogies with the physical world.