- You are here:
- GT Home
- Home
- News & Events

Series: ACO Student Seminar

It has been found about ten years ago that most of the real networks are not random ones in the Erdos-Renyi sense but have different topology (structure of the graph of interactions between the elements of a network). This finding generated a steady flux of papers analyzing structural aspects of networks. However, real networks are rather dynamical ones where the elements (cells, genes, agents, etc) are interacting dynamical systems. Recently a general approach to the studies of dynamical networks with arbitrary topology was developed. This approach is based on a symbolic dynamics and is in a sense similar to the one introduced by Sinai and the speaker for Lattice Dynamical Systems, where the graph of interactions is a lattice. The new approach allows to analyze a combined effect of all three features which characterize a dynamical network ( topology, dynamics of elements of the network and interactions between these elements) on its evolution. The networks are of the most general type, e.g. the local systems and interactions need not to be homogeneous, nor restrictions are imposed on a structure of the graph of interactions. Sufficient conditions on stability of dynamical networks are obtained. It is demonstrated that some subnetworks can evolve regularly while the others evolve chaotically. Some natural graph theoretical and dynamical questions appear in the farther developments of this approach. No preliminary knowledge of anything besides basic calculus and linear algebra is required to understand what is going on.

Series: ACO Student Seminar

This study focuses on computations on large graphs (e.g., the web-graph) where the edges of the graph are presented as a stream. The objective in the streaming model is to maintain small amount of memory and perform few passes over the data.
In the streaming model, we show how to perform several graph computations including estimating the probability distribution after a random walk of certain length l, estimate the mixing time, and the conductance. We can compute the approximate PageRank values in O(nM^{-1/4}) space and O(M^{3/4}) passes (where n is the number of nodes and M is the mixing time of the graph). In comparison, a standard (matrix-vector multiplication) implementation of the PageRank algorithm will take O(n) space and O(M) passes. The main ingredient in all our algorithms is to explicitly perform several random walks of certain length efficiently in the streaming model. I shall define and motivate the streaming model and the notion of PageRank, and describe our results and techniques.
Joint work with Sreenivas Gollapudi and Rina Panigrahy from Microsoft Research.

Series: ACO Student Seminar

Constraint Programming is a powerful technique developed by the Computer Science community to solve combinatorial problems. I will present the model, explain constraint propagation and arc consistency, and give some basic search heuristics. I will also go through some illustrative examples to show the solution process works.

Series: ACO Student Seminar

The notion of a correlation decay, originating in statistical physics, has recently played an important role in yielding deterministic approximation algorithms for various counting problems. I will try to illustrate this technique with two examples: counting matchings in bounded degree graphs, and counting independent sets in certain subclasses of claw-free graphs.

Series: ACO Student Seminar

A successful approach to solving linear programming problems exactly has been to solve the problems with increasing levels of fixed precision, checking the final basis in exact arithmetic and then doing additional simplex pivots if necessary. This work is a computational study comparing different techniques for the core element of our exact computation: solving sparse rational systems of linear equations exactly.

Series: ACO Student Seminar

In order to estimate the spread of potential pandemic diseases and the efficiency of various containment policies, it is helpful to have an accurate model of the structure of human contact networks. The literature contains several explicit and implicit models, but none behave like actual network data with respect to the spread of disease. We discuss the difficulty of modeling real human networks, motivate the study of some open practical questions about network structure, and suggest some possible avenues of attack based on some related research.