- October 5, 2015:
**Dana Randall**, Georgia Institute of Technology

**Phase Transitions in Random Structures and Sampling Algorithms**

*Abstract:*

Sampling algorithms based on Markov chains arise in many areas of computation, engineering and science. The idea is to perform a random walk among the elements in a large state space so that samples chosen from the stationary distribution are useful for the application. In order to get reliable results efficiently, we require the chain to be rapidly mixing, or quickly converging to equilibrium. Often there is a parameter of the system (typically related to temperature or fugacity) so that at low values many natural chains converge rapidly while at high values they converge slowly, requiring exponential time. This dichotomy is often related to phase transitions in the underlying models. In this talk we will explain this phenomenon, giving examples form the natural and social sciences including magnetization, lattice gasses, colloids, and discrete models of segregation.

- November 2, 2015:
**Jeremy Kun**, University of Illinois at Chicago

**Resilience and new approaches to approximate graph coloring**

*Abstract:*

An interesting class of combinatorial objects are those which are "resilient" to adversarial manipulations of some kind. For example, a Hamiltonian graph can be "resilient" if it still has a Hamiltonian path even after an adversary is allowed to remove any edge. One can then ask: are there efficient algorithms to actually find Hamiltonian paths in sufficiently resilient graphs? I will discuss the notion of resilience as a general theme in theoretical computer science, and then describe some of my work giving algorithms and lower bounds for resilient versions of boolean satisfiability and graph coloring.

- November 23, 2015:
**Claire Monteleoni**, George Washington University

**Climate Informatics: Algorithms, Advances, and Open Problems**

*Abstract:*

Despite the scientific consensus on climate change, drastic uncertainties remain. Crucial questions about changes in regional climate, trends of extreme events such as heat waves, heavy precipitation, and mega-storms, and understanding how climate varied in the distant past, must be answered in order to improve predictions, assess impacts and vulnerability, and aid mitigation and adaptation efforts. Machine learning can help answer such questions and shed light on climate change. Similar to the case of bioinformatics, the study of climate change provides a data-rich scientific domain in which cutting-edge tools from machine learning can make a major impact. Further, such questions give rise to new challenges for the design of machine learning algorithms. I will give an overview of challenge problems in climate informatics, and present recent work from my research group in this nascent field, with a particular focus on algorithms for improving predictions of climate change trends from ensembles of climate simulations, and algorithms for improving predictions of extreme events.

- January 11, 2016:
**Liz Munch**, University at Albany, SUNY

**The Reeb graph interleaving distance**

*Abstract:*

In order to understand the properties of a real-valued function on a topological space, we can study the Reeb graph of that function. Since it is efficient to compute and is a useful descriptor for the function, it has found its place in many applications. However, as with many other constructions in computational topology, we are interested in how to deal with this construction in the context of noise. In particular, we would like a method to "smooth out" the topology to get rid of, for example, small loops in the Reeb graph. In this talk, we will define a generalization of a Reeb graph as a functor. Using the added structure given by category theory, we can define interleavings on Reeb graphs. This also gives an immediate method for topological smoothing and we will discuss an algorithm for computing this smoothed Reeb graph. In addition, the categorical viewpoint gives other insights such as providing convergence and approximation results for Mapper, a commonly used tool in TDA, as well as providing an understanding of these structures in higher dimensional settings. This work is joint with Vin de Silva, Amit Patel, Anastasios Stefanou, and Bei Wang.

- February 22, 2016:
**Aaron Clauset**, University of Colorado, Boulder

**Gender, Productivity, and Prestige in Computer Science Faculty Hiring Networks**

*Abstract:*

Women are dramatically underrepresented in computer science at all levels in academia, and account for just 15% of tenure-track faculty. Understanding the causes of this gender imbalance would inform both policies intended to rectify it and employment decisions by departments and individuals. Progress in this direction, however, is complicated by the complexity and decentralized nature of faculty hiring, and the non-independence of hires. In this talk, I'll describe an investigation of the multi-dimensional nature of gender inequality in computer science faculty hiring, using comprehensive data on both hiring outcomes and scholarly productivity for 2659 tenure-track faculty across 205 Ph.D.-granting departments in North America. Using a network model of the hiring process, we characterize the role of gender alone on observed hiring outcomes, and we investigate gender differences in scholarly productivity, postdoctoral training rates, career movements up the rankings of universities, and the ability of departments to independently improve their gender balance. Our model additionally allows us to calculate an effective "gender penalty" in terms of the number of additional papers a female candidate would need to have written in order to place similarly to a male candidate, and to make a long-term estimate as to when gender parity in faculty hiring will be reached. I'll close with some discussion of the subtle nature of gender inequality in faculty hiring networks, and how our results compare to past work on diversity in academia. This is joint work with Samuel F. Way and Daniel B. Larremore.

- March 28, 2016:
**David Gleich**, Purdue University

**Sparsity and localization in evaluating functions of matrices on modern information networks**

*Abstract:*

The largest information networks studied display a number of characteristic properties including a highly-skewed and possibly power-law degree distribution as well as local clustering. We'll describe a few recent results on how these properties imply localization results for various graph diffusion operations when expressed as a function of a matrix. One of the best known examples is the heat kernel, where we'll show conditions when the heat-kernel of a graph remains localized, or effectively sparse, as the graph size grows.

- April 13, 2016:
**Irene Muzi**, Sapienza University of Rome

**The 1/p-IntegralLinkage Problem in Directed Acyclic Graphs**

*Abstract:*

Given a graph G and distinct ordered pairs of vertices (s_1,t_1),...,(s_k,t_k), the k-VertexDisjointPaths (k-VDP) problem asks for pairwise vertex disjoint paths P_1,...,P_k such that P_i is a path from s_i to t_i. k-VDP is a classical problem in graph theory both in its undirected and directed version. For undirected graphs, Robertson and Seymour showed that k-VDP is solvable in polynomial time when k is fixed. The directed case is considerably harder and it was shown to be NP-hard even when k equals 2 (a result of Fortune, Hopcroft and Wyllie). In this talk we will focus on the 1/p-IntegralLinkage problem, a relaxation of k-VDP that allows for a vertex of G to belong to at most p of the k paths and we will show that a fixed parameter time algorithm exists on directed acyclic graphs when p equals k-1. This is joint work with K. Edwards and P. Wollan.

- Fall 2016:
**Cris Moore**, Santa Fe Institute

**TBA**

*Abstract:*

Return to main CS Theory Seminar page