Title: Online Data Reconstruction

In online property-preserving data reconstruction, we consider a dataset which is assumed to satisfy various known structural properties. It may consist of sorted numbers, or points on a manifold, or vectors in a polyhedral cone, or codewords from an error-correcting code. Because of noise and errors, however, an (unknown) fraction of the data is deemed in violation with the expected structural properties.

Can a client still query into the dataset in an online fashion and be provided non-violating data that differs only slightly with the actual data?

We show that in some cases it is possible to design such a filter that stands between the client and the dataset, serves as a sound facade of an unsound dataset, while performing only poly-log queries to the dataset per client-query.

This is joint work with Bernard Chazelle, Seshadhri Comandur and Ding Liu.

Title: Oscillations with TCP-like Congestion Control in Networks of Queues

We consider a set of flows passing through a network of constant-rate queues. We assume that the injection rate into each flow is governed by a TCP-like congestion control mechanism that increases the injection rate when all the servers on the flow's path are empty and decreases the injection rate when some server is congested. We show that if the queueing dynamics are considered then such a system can oscillate, for (essentially) any given congestion control mechanism.

Joint work with Alex Slivkins (Cornell).

Title: Combinatorial descriptions of geometric invariants

In enumerative geometry, we are interested in counting the number of geometric objects of a certain type, which satisfy certain conditions. For example, one may ask how many lines intersect four given lines in general position. Such questions can be understood by utilizing the cohomology rings of Grassmann varieties, and have a beautiful answer in terms of counting Young tableaux, known as the classical Littlewood-Richardson rule. I will explain these connections, and possibly generalizations (if time allows).

Title: Placing Relay Nodes for Intra-Domain Path Diversity

To increase reliability and robustness of mission-critical services in the face of routing changes, it is often desirable and beneficial to take advantage of path diversity provided by the network topology. One way of achieving this inside a single Autonomous System (AS) is to use two paths between every Origin-Destination (OD) pair. One path is the default path defined by the intra-domain routing protocol; the other path is defined as an overlay path that passes through a strategically placed relay node. The key question then is how to place such relay nodes inside an AS, which is the focus of this paper. We propose two heuristic algorithms to find the positions of relay nodes such that every OD pair has an overlay path, going through a relay node, that is disjoint from the default path.

Title: Applications of self-organizing systems to epidemiology: what social insect biology can teach us about humans

Transmission of infectious diseases depends greatly on the social interactions between and among individuals. However, understanding these interactions and how small differences in localized behaviors can affect disease spread on a population wide scale is incredibly difficult. Social insects can provide a convenient, "simplified" biological system for examining certain scenarios and mathematical modeling leads us the rest of the way to fascinating insights in population-wide disease dynamics, not only for insects but for humans as well.

Title: Structure and Content Scoring for XML

XML repositories are usually queried both on structure and content. Due to structural heterogeneity of XML, queries are often interpreted approximately and their answers are returned ranked by scores. Computing answer scores in XML is an active area of research that oscillates between pure content scoring such as the well known tf*idf and taking structure into account. However, none of the existing proposals fully accounts for structure and combines it with content to score query answers. We propose novel XML scoring methods that are inspired by tf*idf and that account for both structure and content while considering query relaxations. Twig scoring, accounts for the most structure and content and is thus used as our reference method. Path scoring is an approximation that loosens correlations between query nodes hence reducing the amount of time required to manipulate scores during top-k query processing. We propose efficient data structures in order to speed up ranked query processing. We run extensive experiments that validate our scoring methods and that show that path scoring provides very high precision while improving score computation time.

Title: Random discrete matrices

I am going to discuss recent progress on several basic problems concerning random matrices with discrete entries, in particular those with (-1,1) entries.