COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2010

In this presentation, we will talk about modal logic and change of information. Specifically, we will look at Dynamic Epistemic Logic and explore some interesting problems concerning certainty of knowledge and common knowledge that can be modeled in this setting. When developing some logic, the first question that arises is how we can present a sound and complete logical system (deduction system) for it. We will formally define these terms in our talk and will consider some Hilbert Style proof systems for propositional modal logics. Finally, we will review the differences between Knowledge and Belief and will see how we can axiomatize these notions in the logic.

One top-level model of a communication network is a Multi-commodity Flow Network (MFN) and a Hierarchical Communication Network (HCN) is a type of MFN. Here we consider the survivability of HCN's. We analyze the survivability of a HCN under uncertain conditions and try to increase it. Network survivability analysis means estimating the network quality decrease as a result of edge capacity reduction if the defeated edges are unknown beforehand. The quality of the network functioning is evaluated based on completeness of the supply of flow demands user-pairs.

We present a method for inferring the topology of a sensor network given non-discriminating observations of activity in the monitored region. This is accomplished based on no prior knowledge of the relative locations of the sensors and weak assumptions regarding environmental conditions. Our approach employs a two-level reasoning system made up of a stochastic Expectation Maximization algorithm and a higher level search strategy employing the principle of Occam's Razor to look for the simplest solution explaining the data. The result of the algorithm is a Markov model describing the behavior of agents in the system and the underlying traffic patterns. Numerical simulations and experimental assessment conducted on a real sensor network suggest that the technique could have promising real world applications in the area of sensor network self-configuration.

We review results on layout and reconfiguration properties of paths and cycles whose edge lengths are fixed. Then we consider results on representing graphs by binary geometric relations, namely, visibility and proximity. Finally, we illustrate graph drawing principles in the context of micromanufacturing technology.

The mixing time of a Markov chain is a measure of the convergence rate of the state distribution to the stationary distribution and is fundamental in the application of Markov chains in sampling and randomized algorithms. In this talk, I will discuss our recent work on mixing times for chains (Glauber dynamics) whose stationary distributions are models in equilibrium statistical mechanics.