Schedule

For the past two weeks, I have been enjoying the unique atmosphere of Romania. I promise to blog a bit about Romania and its universities next week, since most people are probably not aware of this parallel academic universe.

Now it is time to get back into the real world, and possibly do some work. Of course, on the way to doing work, I might as well have some fun. My upcoming schedule is as follows:

• Oct 6: Timisoara (my first visit to this reportedly beautiful city in West Romania)
  
• Oct 7: Budapest
• Oct 8: Bratislava (first time in Slovakia)
  
• Oct 9: Amsteram
• Oct 10 -- Oct 16: Bonn
  I am visiting Yakov Nekritch, whose homepage picture reminds me of pre-1989 Romania (a mid-level Party administrator for agriculture, looking proud of his crops).
  
  On Monday, Oct 15, at 10am, I am giving the following talk:
  
  Dynamic Graph Algorithms invade Geometry
  After dynamic graph algorithms has been an area of intense research in data structures for almost 30 years, the time seems ripe for the field to tackle problems of a geometric nature. In dynamic graph algorithms, we have a graph that is being changed through updates (typically edge insertions and deletions), and we want to query it for various graph properties (say, whether two nodes are connected, the cost of an MST, the shortest path between two nodes etc).
  
  Now consider a scenario in which we have sensors distributed in the space, and each sensor can only talk to another sensor at radius r. The connectivity is defined by the intersection graph of discs of radius r/2 around every point. Can we handle a dynamic environment, e.g. a situation when new sensors can be inserted, or some sensors run
  out of battery?
  
  Our results apply to the intersection graphs of a very general class of objects (includings disks, segments, rectangles) and support the dynamic connectivity problem in time O(n^c) per update and query, where c is a constant less than 1 depending on the geometric shape in question. This opens a very broad and promising research direction:
  
  • can new graph queries be supported (e.g. shortest path queries)?
  • what is the best running time for each important geometric shape?
  
  Joint work with Timothy Chan and Liam Roditty.
  
  
• Oct 16 -- Oct 20: Brussels (first time in Belgium)
  
  Here, I am visiting Stefan Langerman. On Thrusday, Oct 18 at 12:30, I am giving a talk:
  
  Farey Sequences and Counting Primitive Lattice Points
  A primitive lattice point is a point (x,y) with x, y integers and gcd(x,y)=1. "Counting" primitive lattice points inside various planar shapes has been an active area of mathematics in the past decades. But by virtue of seeking an elementary formula, the mathematical definition of "counting" is "approximating asymptotically". We now present the first results on the informatics view of this problem: give an efficient algorithm to count primitive lattice points exactly.
  
  The problem is related to another entertaining mathematical problem that has crossed the border into informatics. The Farey sequence of order N is the sorted sequence of irreducible fractions a/b, with a≤b≤N. There are well-known algorithms for generating this sequence in its entirety. We now describe algorithms for finding just one value of the sequence (say the K-th value) significantly faster.
  
  Joint work with Jakub Pawlewicz.
  
  
• Oct 20 -- Oct 23: FOCS in Providence.
  The talk is on Monday morning at 8:30, and I am giving it (Mikkel and I use the alternation principle for choosing the speaker). The paper is here.
  
  Planning for Fast Connectivity Updates
  Understanding how a single edge deletion can affect the connectivity of a graph amounts to finding the graph bridges. But when faced with d>1 deletions, can we establish as easily how the connectivity changes? When planning for an emergency, we want to understand the structure of our network ahead of time, and respond swiftly when an emergency actually happens.
  
  
  We describe a linear-space representation of graphs which enables us to determine how a batch of edge updates can impact the graph. Given a set of d edge updates, in time O(d.polylgn) we can obtain the number of connected components, the size of each component, and a fast oracle for answering connectivity queries in the updated graph. The initial representation is polynomial-time constructible.
  

I will blog about each paper after the talk. If you want to meet in Brussels, Bonn, or Providence, drop me a line.