Georgia Institute of Technology College of Sciences

We consider random walks on Z^d among nearest-neighbor random conductances which are i.i.d., positive, bounded uniformly from above but which can be arbitrarily close to zero. Our focus is on the detailed properties of the paths of the random walk conditioned to return back to the starting point after time 2n. We show that in the situations when the heat kernel exhibits subdiffusive behavior --- which is known to be possible in dimensions d \geq 4-- the walk gets trapped for time of order n in a small spatial region. This proves that the strategy used to infer subdiffusive lower bounds on the heat kernel in earlier studies of this problem is in fact dominant. In addition, we settle a conjecture on the maximal possible subdiffusive decay in four dimensions and prove that anomalous decay is a tail and thus zero-one event. Joint work with Marek Biskup, Alexander Vandenberg and Alexander Rozinov.

This is a survey of Hub Labeling results for general and road networks.Given a weighted graph, a distance oracle takes as an input a pair of vertices and returns the distance between them. The labeling approach to distance oracle design is to precompute a label for every vertex so that distances can be computed from the corresponding labels. This approach has been introduced by [Gavoille et al. '01], who also introduced the Hub Labeling algorithm (HL). HL has been further studied by [Cohen et al. '02].We study HL in the context of graphs with small highway dimension (e.g., road networks). We show that under this assumption HL labels are small and the queries are sublinear. We also give an approximation algorithm for computing small HL labels that uses the fact that shortest path set systems have small VC-dimension.Although polynomial-time, precomputation given by theory is too slow for continental-size road networks. However, heuristics guided by the theory are fast, and compute very small labels. This leads to the fastest currently known practical distance oracles for road networks.The simplicity of HL queries allows their implementation inside of a relational database (e.g., in SQL), and query efficiency assures real-time response. Furthermore, including HL data in the database allows efficient implementation of more sophisticated location-based queries. These queries can be combined with traditional SQL queries. This approach brings the power of location-based services to SQL programmers, and benefits from external memory implementation and query optimization provided by the underlying database.Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck.

We prove an analog of the Caffarelli-Kohn-Nirenberg theorem for weak solutions of a system of PDE that model a viscoelastic fluid in the presence of an energy damping mechanism. The system was recently introduced in a method of establishing the global in time existence of weak solutions of the well known Oldroyd model, which remains an open problem.

How advances in science are made, and how they may come to benefit mankind at large are complex issues. The discoveries that most infuence the way we think about nature seldom can be anticipated, and frequently the applications for new technologies developed to probe a specific characteristic of nature are also seldom clear, even to the inventors of these technologies. One thing is most clear: seldom do individuals make such advances alone. Rather, they result from the progress of the scientific community, asking questions, developing new technologies to answer those questions, and sharing their results and their ideas with others. However, there are indeed research strategies that can substantially increase the probability of one's making a discovery, and the speaker will illustrate some of these strategies in the context of a number of well known discoveries, including the work he did as a graduate student, for which he shared the Nobel Prize for Physics in 1996.