Random Structures Spring 2015

Friday, 2PM - 3PM, or Friday 3PM - 4PM, RLM 8.136

Organizers: Francois Baccelli and Ngoc Tran

This is a weekly working group at the Department of Mathematics at UT Austin. It is opened to anybody who is interested in topics around the theme of random structures, such as networks, spatial processes, random graphs, random combinatorial objects, with applications in operations research, machine learning and computer science.

To be added to the mailing list, please email: ntran at math.utexas.edu


DATE SPEAKER TITLE (click for abstract below)
January 27, 11am-12pm, UTA 7.532 Arun Padakandla An Algebraic framework for multi-terminal communication
February 6 John Hasenbein Rapid Detection of Viruses on Contact Networks
February 13 Vivek Borkar Gossip Algorithms and its Variants
March 6 Joe Neeman Some phase transitions in the stochastic block model
March 25 William A. Massey Gaussian Skewness Approximation for Dynamic Rate Multi-Server Queues with Abandonment
April 3 Antonio Sodre Asymptotic Speed of Restart Walks on Point Processes
April 10 Anton Dochtermann Warmth and edge spaces of graphs
April 27 Anne Shiu Which neural codes are convex?

Title and Abstracts

An Algebraic framework for multi-terminal communication

Arun Padakandla
University of Michigan

In this talk, we propose new coding techniques based on coset codes for communication over three multi-terminal channels including the three user discrete broadcast (3-BC) and interference channels (3-IC). Characterizing the performance of the proposed coding technique in an information theoretic framework enables us present new achievable rate regions. These new achievable rate regions strictly enlarge upon the current known largest that were derived over three decades ago. We identify instances of 3-BC and 3-IC, including non-additive ones, for which the presented achievable rate region is strictly larger than current known largest. Moreover, for these examples, the proposed coding technique is capacity achieving. Our findings are based on a new algebraic framework developed for an information theoretic study of multi-terminal communication channels.

Rapid Detection of Viruses on Contact Networks

John Hasenbein
University of Texas at Austin

In this talk we consider the problem of detecting a virus propagating on an undirected graph. The controller is allowed to place a constrained number of detectors at a subset of nodes in order to either minimize the expected time until virus detection or maximize the probability of detection by a certain time. The decision problem can be formulated as a stochastic integer program which is inherently intractable. However, under a variety of virus propagation models, the objective function can be shown to be sub- or super-modular, justifying the implementation of greedy and lazy greedy heuristics.
This problem was inspired by our work with SK-Telecom, the largest mobile provider in South Korea. We demonstrate the effectiveness of greedy solutions on data sampled from SK-Telecom contact networks. This is joint work with Jinho Lee (Republic of Korea Navy) and David Morton (Northwestern University).

Gossip Algorithms and its Variants

Vivek Borkar
Indian Institute of Technology Bombay

This talk will survey a variety of algorithms related to the classical gossip algorithm, including some nonlinear variants.

Some phase transitions in the stochastic block model

Joe Neeman
Department of Mathematics, UT Austin

The stochastic block model is a random graph model that was originally introduced 30 years ago to model community structure in networks. To generate a random graph from this model, begin with two classes of vertices and then connect each pair of vertices independently at random, with probability p if they are in the same class and probability q otherwise. Some questions come to mind: can we reconstruct the classes if we only observe the graph? What if we only want to partially reconstruct the classes? How different is this model from an Erdos-Renyi graph anyway? The answers to these questions depend on p and q, and we will say exactly how.

Gaussian Skewness Approximation for Dynamic Rate Multi-Server Queues with Abandonment

William A. Massey
Princeton University

The multi-server queue with non-homogeneous Poisson arrivals and customer abandonment is a fundamental queueing model with dynamic rates for large scale service systems such as call centers and hospitals. Scaling the arrival rates and number of servers gives us fluid and diffusion limits. The diffusion limit suggests a Gaussian approximation to the stochastic behavior. The fluid mean and diffusion variance can form a two-dimensional dynamical system that approximates the actual transient mean and variance for the queueing process. Recent work showed that a better approximation for mean and variance can be computed from a related two-dimensional dynamical system. In this spirit, we introduce a new three-dimensional dynamical system that estimates the mean, variance, and third cumulant moment. This improves on the previous two approaches by fitting the queuing distribution to one of a quadratic function for a Gaussian random variable. This is joint work with Jamol Pender of Cornell University.

Asymptotic Speed of Restart Walks on Point Processes

Antonio Sodre
Department of Mathematics, UT Austin

We study the speed of a transient random walk on a simple point process in $\R$ when the time to travel distances between points of the process is given by a restart scheme. If the realization of a clock random variable is less than the distance, the time is restarted. Then, the total time to travel two points is the sum of the failed trials and the successful one. Asymptotic speed is the limit of the ratio of the sum of distances between the points of the process over the sum of the time taken to travel these distances. Positive (zero) asymptotic speed appears when the distribution of the distance between points has lighter (heavier) tails than the distribution of the clock random variables. More generally, we can investigate this problem when the distances to travel are determined by a point-map, namely, a translation-invariant rule to map one point of the process to another.

Warmth and edge spaces of graphs

Anton Dochtermann
Department of Mathematics, University of Texas at Austin

In recent years two novel approaches for finding lower bounds on the chromatic number of a graph have been introduced. One involves studying the topological connectivity of the `edge space' of a graph, dating back to Lovasz's celebrated proof of the Kneser conjecture. The other is motivated by constructions in statistical physics and involves the notion of long range action of random branching walks and the 'warmth' of a graph, as introduced by Brightwell and Winkler.
We seek to relate these two constructions, and in particular we provide evidence for the conjecture that the warmth of a graph G is always less than three plus the connectivity of its edge space. We succeed in establishing the first nontrivial case of the conjecture, and calculate the warmth of a family of graphs with relevant edge space topology. We also demonstrate a connection between the warmth of a graph and the collection of complete bipartite subgraphs that it contains, providing an analogue for a similar result in the context of edge spaces. This is joint work with Ragnar Freij.

Which neural codes are convex?

Anne Shiu
Department of Mathematics, Texas A&M University

This talk focuses on a combinatorial and algebraic problem motivated by a question in neuroscience. Specifically, which neural codes arise from place cells? A neural code is a collection of codewords ($0$-$1$ vectors, interpreted as neuronal co-firing patterns) of the same length. A neural code is {\em convex} if there exist $n$ convex sets (place fields) in some $\mathbb{R}^d$ so that each codeword corresponds to a unique region carved out by the convex sets: the support of the codeword corresponds precisely with which convex sets the region is in. The {\em minimal embedding dimension} is the minimum such dimension $d$ for which this is possible. We will describe how to use combinatorial algebra and topology to uncover intrinsic signatures of convexity and embedding dimension in neural codes.
This is joint work with Carina Curto, Elizabeth Gross, Jack Jeffries, Katie Morrison, Mohamed Omar, Zvi Rosen, and Nora Youngs.