## COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2010 |

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca). To get e-mail notification of our seminars and other events, you can subscribe to the CAG e-mail list at http://mailman.csc.uvic.ca/mailman/listinfo/cag

Date | Place | Time | Speaker | Abbreviated Title |
---|---|---|---|---|

Wed. Oct. 6 | 1:30pm | ECS 642 | Mohammed Hajiabadi | Modal Logic and Reasoning About Knowledge by Mohammad Hajiabadi. |

Fri. Oct. 15 | 2:30pm | ECS 660 | Mohammad Bagher Ahmadi | Hierarchical Communication Network and its Survivability |

Fri. Oct. 29 | 2:30pm | ECS 660 | Dimitri Marinakis | Occam's Razor Applied to Network Topology Inference |

Fri. Nov. 5 | 2:30pm | ECS 660 | Sue Whitesides | Motion Planning and Graph Layout |

Fri. Nov. 26 | 2:30pm | ECS 660 | Peter Otto | Mixing Times of Glauber Dynamics for Models in Statistical Mechanics |

Wed. Oct 6, 1:30 pm, ECS 642

Mohammed Hajiabadi

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.

Fri. Oct 15, 2:30 pm, ECS 660

Dr. Mohammad Bagher Ahmadi

Mathematics Department, Shiraz University

Sabbatical visitor at University of Victoria

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.

Fri. Oct. 29, 2:30pm, ECS 660

Dimitri Marinakis

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.

Fri. Nov. 5, 2:30 pm, ECS 660

Sue Whitesides

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.

Fri. Nov. 26, 2:30 pm, ECS 660

Peter Otto

Department of Mathematics, Willamette University

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.

CAG Schedule of Talks: Fall 2010 / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised Jan. 20, 2011