- October 20, 2014:
**Travis Humble**, Oak Ridge National Laboratory

**Quantum Computing Systems and Software**

*Abstract:*

The past twenty years has seen the rapid development of quantum computing from a theoretical construct into a diversity of integrated physical systems. The availability of working hardware has forced the question of how to use quantum computers systems efficiently and how to integrate them with conventional computing paradigms. In this talk, we track recent progress toward realizing large-scale quantum computers with an emphasis on the types of quantum computer software needed for near-term efforts. We present our recent results on an integrated programming environment for adiabatic quantum computation and the promise of using quantum-assisted computing in large-scale computations. We also describe recent experiments using software-defined quantum networks to support future distributed quantum computing systems.

- November 3, 2014:
**Felix Reidl and Fernando Sànchez Villaamil**, RWTH Aachen University

**Fun with Parameterized Algorithms**

*Abstract:*

In the last twenty-five years, parameterized complexity and algorithmics has matured from its humble inception into a rich, booming field of theoretical research. In this talk we highlight our favorite results and techniques to demonstrate how multivariate algorithms (and thus parameterized complexity) catalyzed progress in both theory and practice. We will touch on the topics of kernelization, graph width measures, model checking and intractability results. Whether you're curious, skeptical or already converted: come learn why parameterized complexity is a philosophically satisfying and immensely useful framework.

- November 12, 2014:
**Mason Porter**, Mathematical Institute, University of Oxford

**There's Something About Networks**

*Abstract:*

Networks arise pervasively in biology, physics, technology, social science, and myriad other areas. Traditionally, a network consists of a static collection of entities (called nodes) that interact via a single type of edges. However, most networks included multiple types of connections --- which could represent, for example, Facebook friendships and Twitter following --- and the nodes and/or edges can also change in time. To incorporate such structure into investigations of networks, my collaborators and I have developed a tensorial formalism to study so-called "multilayer networks". In this talk, I will give an introduction to multilayer networks and discuss some applications of our work. The main reference for this talk is our new review article, which is available at http://comnet.oxfordjournals.org/content/2/3/203.

- January 21, 2015:
**Peter Winkler**, Dartmouth College

**New Directions for Random walk on a Graph**

*Abstract:*

Random walk on a graph is a beautiful and (viewed from today) classical subject with elegant theorems, multiple applications in the theory of computing, and a close connection to the theory of electrical networks. The subject seems to be livelier now than ever, with a surprising number of new results. We will discuss recent progress in some new directions. In particular, how long can it take to visit every edge of a graph, or to visit every vertex a representative number of times? Can random walks be coupled so that they don't collide? Can moving targets be harder to hit than fixed targets? How long does it take to capture a random walker? Can random walk help a pursued rabbit? Mentioned will be work by or with Omer Angel, Yakov Babichenko, Jian Ding, Oded Feldheim, Agelos Georgakopoulos, Ander Holroyd, Natasha Komarov, James Lee, James Martin, Yuval Peres, Ron Peretz, Perla Sousi, and David Wilson.

- February 20, 2015:
**Henry Cohn**, Microsoft Research New England

**Sparse graph limits and scale-free networks**

*Abstract:*

How can we understand the structure of an enormous network? For dense graphs, Szemeredi regularity is a fundamental tool that has led to a rich theory of graph limits. However, many real-world networks are sparse, and all sparse graphs converge to zero in the dense theory. To distinguish between them, we need a more refined theory. Bollobas and Riordan took an important step in this direction by analyzing sparse graphs without dense spots, but this hypothesis rules out many important cases such as power-law distributions. In this talk, I'll review the theory of graph limits and discuss a broad extension to sparse graphs (which is joint work with Christian Borgs, Jennifer Chayes, and Yufei Zhao).

- March 18, 2015:
**Johan Ugander**, Microsoft Research Redmond/Stanford University

**Graph cluster randomization: design and analysis for experiments in networks**

*Abstract:*

A/B testing is a standard approach for evaluating the effect of online experiments; the goal is to estimate the Average Treatment Effect (ATE) of a new feature or condition by exposing a sample of the overall population to it. A drawback with A/B testing is that it is poorly suited for experiments involving social interference, when the treatment of individuals spills over to neighboring individuals along an underlying social network. In this work, we propose a novel methodology for using graph clustering to analyze average treatment effects under social interference. To begin, we characterize graph-theoretic conditions under which individuals can be considered to be 'network exposed' to an experiment. We then show how graph clustered randomization admits an efficient exact algorithm to compute the probabilities for each vertex being network exposed under several of these exposure conditions, allowing for a straightforward effect estimator using inverse probability weights. This estimator is also unbiased assuming that the exposure model has been properly specified. Given this framework for graph cluster randomization, we analyze the variance of the estimator as a property of cluster design, and the bias/variance trade-offs of the estimator under simulated exposure model misspecifications. Our analysis of the variance includes a novel clustering algorithm for which the variance is at most linear in the degrees of the graph, an important challenge. Our analysis of misspecifications highlights when clustering appears to be strongly favorable: when the network has a sufficiently clustered structure, and when social interference is sufficiently strong.

- April 20, 2015:
**Michael Langston**, University of Tennessee, Knoxville

**Uncovering Latent Relationships in High Dimensional Data: Parameterized Graph Algorithms and Applications**

*Abstract:*

We will focus mainly on algorithmic applications, and discuss the use of fixed-parameter tractable techniques in the analysis of highly complex data. We will address important issues with noise, and the role model organisms often play in the study of human health. Critical resources include enormous repositories of emergent data, suites of novel statistical and graph theoretical methods, deep domain knowledge and high performance computing platforms. We will describe how the potential of these resources can be harnessed to help realize the promise of new algorithmic methods in the elucidation and interpretation of previously unknown relationships. Effective load balancing and efficient combinatorial search are important concerns. Examples will be drawn from numerous types of high-throughput and/or highly heterogeneous biological and health sciences data, as well as data drawn from a variety of other research domains.

Return to main CS Theory Seminar page