Rank | Institution | Average Count | Faculty |

1 | ? University of Warsaw ? | 8.4 | 24 |

2 | ? Massachusetts Institute of Technology ? | 8.2 | 20 |

3 | ? University of Texas - Austin ? | 7.3 | 8 |

4 | ? Stanford University ? | 7.1 | 12 |

5 | ? Cornell University ? | 6.9 | 14 |

6 | ? Northeastern University ? | 6.1 | 10 |

7 | ? New York University ? | 5.9 | 10 |

7 | ? Carnegie Mellon University ? | 5.9 | 14 |

9 | ? University of Illinois at Urbana-Champaign ? | 5.7 | 14 |

9 | ? University of California - San Diego ? | 5.7 | 10 |

Quite surprising... as all the ranking are usually. However, there might be some reasons for this. First of all, we cover all three areas that are counted in theory. For example, logic is visibly stronger in Warsaw than in other places included in top 10. Second, we indeed started doing quite well, e.g., we got 6 ERC grants so far. I do not really believe in rankings, but at least it is some indication that Warsaw is not such a bad place to be - see the cat meme.

]]>I clicked the automatic assignment button and I got a very unfair assignment. EasyChair wanted to punish 3 of my PC members by giving them 11, drugs 12 and 15 papers from their No list. In EasyChair one can bid Yes, Maybe and No on papers. I found this rather absurd as 15 paper was more than half of the total review load. The question is: Does this poor guy need to get so many Nos in optimal assignment?. The short intuitive answer is: most probably no, as there is a lot of freedom in each maximal size matching (by Gallai-Edmonds decomposition).

Hence, in 2 hours I coded my own assignment procedure. I assumed that in the assignment:

- first, I want to maximize the number of papers assigned to Maybes and Yeses,
- second, under the first assumption, I want to maximize the number of papers assigned Yeses.

This can be formalized as a maximum-cost maximum-flow problem:

- connect the source vertex with each PC member with a zero cost edge of capacity equal to review load,
- connect each PC member with each paper with edges of capacity 1 and cost 0 for No, 10000 for Maybe and 10001 for Yes.
- connect each paper with the sink with edge of cost 0 and capacity 3.

I executed it and I got assignment with the same number of Nos - 80 and Maybes -100 as EasyChair. And of course, it was not much more fair than the one given by EasyChair. If you always wondered how EasyChair computes the assignment this is the way. Essentially, there is no reason for this to be fair in any sense. One is optimizing global cost, so it should be clear that locally it can be bad, e.g., some PC members will get bad assignments without any good reason. It can be even worse as one can be getting many Nos due to the execution order of procedure, as there is always a lot of freedom in the optimal matching. It can happen that even if you bid on almost everything you will get all the Nos if all people bid No on the same papers.

There is a solution here - I added third assumption to my procedure:

- zero, no PC member can get more than X Nos, where X is a parameter.

This can be easily incorporated into the max-flow problem. One just needs to split a vertex representing each PC member into three vertices: PC_0, PC_No and PC_NotNo. The maximum-cost maximum-flow problem becomes:

- connect the source vertex with all PC_0 vertices with a zero cost edge of capacity equal to review load,
- connect PC_0 to PC_No with zero cost edge of capacity X,
- connect PC_0 to PC_NotNo with zero cost edge of capacity equal to review load,
- connect PC_No with edges of cost 0 to all papers with No,
- connect PC_NotNo with each paper with edges of capacity 1 and cost 10001 for Maybe and 10001 for Yes.
- connect each paper with sink with edge of cost 0 and capacity 3.

I executed it - the table below shows the number of Maybes in the assignment in dependence on the parameter X.

X | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

#Maybes | 120 | 116 | 112 | 109 | 106 | 104 | 102 | 100 | 100 |

One striking thing is that there exists an optimal assignment where the poor guy that was getting 15 Nos is getting only 11 Nos. Essentially, there was no reason for giving 15 Nos to this PC member! This probably already happened to many of you ;). I the final assignment I went for X=4 as this actually meant that almost everyone gets 3 Nos and only 2 PC members get 4 Nos. This much fairer assignment costed only 20 Maybes in the quality, what I found a fair cost of being fairer.

]]>The HALG conference has opened the registration and the program is available as well - see the links below. The program looks very interesting so I hope many of you will be coming.

Highlights of Algorithms - HALG 2016

June 6-8, link 2016, ask Paris, France

http://highlightsofalgorithms.

The Highlights of Algorithms conference is designed to be a forum for presenting the highlights of recent developments in algorithms and for discussing potential further advances in this area. The conference will provide a broad picture of the latest research in algorithms through a series of survey and invited talks, as well as possibility for all researchers and students to present their recent results through a series of short talks and poster presentations. Attending the Highlights of Algorithms conference will also be an opportunity for networking and meeting leading researchers in algorithms.

The registration for the Highlights of Algorithms conference is open.

To register, please visit the link at http://highlightsofalgorithms.

A preliminary program is available online at http://highlightsofalgorithms.

The program is packed with 28 invited talks and with even a larger number of short contributions.

Those interested in attending the conference are advised to book accommodation as early as possible (given the high hotel prices in Paris).

]]>

This summer, drug on June 6-8 in Paris, help we will be having a new algorithmic event: Highlights of Algorithms 2016 (HALG 2016) conference.

This conference will be quite unlike the conferences we are all used to. First of all, patient it will consist mainly of invited talks and tutorials, accompanied by a smaller number of contributed talks and posters. Secondly, there will be no conference proceedings, i.e., presenting work already published at a different venue or journal (or to be submitted there) is absolutely welcome and even encouraged.

The call for submissions of contributed short talks and posters has been just posted online. The program committee is currently in the process of selecting invited speakers (partially based on the nominations from the community).

We already have a number of very exciting speakers committed and we expect to add a few more names shortly.

The intention here is to make HALG a forum for presenting the highlights of some of the most exciting recent developments in algorithms, discussing potential further advances in this area, as well as networking and initiating new collaborations. In a way, we want HALG to be a place one can go to catch up on what are the hottest results/topics

at the moment, as well as what one missed by not being able to attend all the STOC/FOCS/SODA/ESA/ICALP/PODC/ITCS/… conferences that year.

We believe that this kind of venue is very much needed today and will help to make our community stronger and more cohesive. In particular, we hope that the success of the first edition will make HALG become a recurring event. In fact, HALG draws some inspiration from Highlights of Logic, Games and Automata (HLGA) conference series that became very successful in its respective community already. There are some differences in how both conferences are constructed: HALG will concentrate on invited talks with some contributed talks, whereas HLGA was only having short contributed talks so far; but the overall premise is the same and seems to be working very well. (We also heard some rumors that the next edition of HLGA will move in the direction of HALG and have invited talks too.)

In any case, the HALG 2016 in Paris should be a lot of fun. We hope to see many of you there! So please submit your work to HALG.

]]>In our paper "*The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree*" we have shown the first sublinear time algorithm which maintains a constant approximate Steiner tree under terminal additions and deletions. We show that we can maintain a -approximate Steiner tree of a general graph in time per terminal addition or removal. Here, denotes the stretch of the metric induced by the graph. For planar graphs we achieve the same running time and the approximation ratio of . Observe that due to the sparsity of real world networks only algorithms with such sublinear complexity could be of some practical importance and could potentially be used to reduce the communication cost of dynamic multicast trees. Our paper aims to be a theoretical proof of concept that from algorithmic complexity perspective such algorithms are indeed possible. However, turning these theoretical ideas into useful algorithms will require much more research. In particular, a natural question here is whether the approximation factor of our algorithms could be considerably improved while keeping the running time sublinear?

Let me note that this might be hard as the approximation factor of for Steiner tree in general graphs comes from using 3-approximate oracles [10], using 2-approximation of the Steiner tree by the MST in the metric closure, and -approximate online MST algorithm. In other words we hit two challenging bounds: in order to improve our approximation factors, one would need either to improve the approximation ratio of the oracles which are believed to be optimal, or devise a framework not based on computing the MST. The second challenge would require to construct simple and fast (e.g., near-linear time) approximation algorithms for Steiner tree that would beat the MST approximation ratio of 2. Constructing such algorithms is yet another challenging open problem.

If you would like to learn more on how it works, you can still attend our talk during the coming STOC in Portland on Monday at 9:00, or have look into the full version of the paper on arXiv.

[1] M. Imase and B. M. Waxman. Dynamic Steiner tree problem. SIAM J. Discrete Math., 4(3):369–384, 1991.

[2] N. Megow, M. Skutella, J. Verschae, and A. Wiese. The power of recourse for online MST and TSP. In ICALP, pages 689–700. 2012.

[3] A. Gu, A. Gupta, and A. Kumar. The power of deferral: maintaining a constant-competitive Steiner tree online. In STOC, pages 525–534, 2013.

[4] A. Gupta and A. Kumar. Online Steiner tree with deletions. In SODA, pages 455–467. SIAM, 2014.

[5] X. Cheng, Y. Li, D.-Z. Du, and H. Ngo. Steiner trees in industry. In D.-Z. Du and P. Pardalos, editors, Handbook of Combinatorial Optimization, pages 193–216. Springer US, 2005.

[6] F. Bauer and A. Varma. ARIES: A rearrangeable inexpensive edge-based on-line Steiner algorithm. IEEE Journal of Selected Areas in Communications, 15:382–397, 1995.

[7] E. Aharoni and R. Cohen. Restricted dynamic steiner trees for scalable multicast in datagram networks. In INFOCOM ’97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution., Proceedings IEEE, volume 2, pages 876–883 vol.2, Apr 1997.

[8] S.-P. Hong, H. Lee, and B. H. Park. An efficient multicast routing algorithm for delaysensitive applications with dynamic membership. In INFOCOM ’98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 3, pages 1433–1440 vol.3, Mar 1998.

[9] S. Raghavan, G. Manimaran, C. Siva, and R. Murthy. A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees. IEEE/ACM Transactions on Networking, 7:514–529, 1999.

[10] M. Thorup and U. Zwick. Approximate distance oracles. J. ACM, 52(1):1–24, 2005.

A closer look at the known algorithms for graphs of bounded degree or graphs excluding a fixed minor reveals that the dependency in the running time bound on the "forbidden pattern" is quite bad: in the first case or in the second case, for some function . Seeing such dependencies, a natural question is: do there exist fixed-parameter algorithms, parameterized by the "forbidden pattern"? In other words, does the exponent in the polynomial factor in need to depend on the pattern, on can we obtain an algorithm with running time ?

This question remains widely open for all aforementioned cases of bounded degree or excluded minor. In our recent FOCS 2014 paper, we have answered the question affirmatively for the special case of bounded treewidth graphs, proving that isomorphism of two -vertex graphs of treewidth can be tested in time .

As a starting point, observe that comparing (testing isomorphism) of two graphs *together with their given tree decompositions* (that is, we want to check if the whole structures consisting of a graph and its decomposition are isomorphic) can be done easily in time polynomial in the size of the graphs, and exponential in the width of the decompositions. This is a relatively standard, but tedious, exercise from the area of designing dynamic programming algorithms on tree decompositions: if you have seen a few of these, I guess you can figure out the details, but if you don't, this is probably one of the worst examples to start with, so just assume it can be done. Alternatively, you may use the recent results of Otachi and Schweitzer that say that one needs only a set of bags for the decomposition, even without the structure of the decomposition tree itself.

With this observation, the task of comparing two bounded-treewidth graphs reduces to the following: given a graph of treewidth , we would like to compute *in an isomorphic-invariant way* a tree decomposition of $G$ of near-optimal width. Here, isomorphic-invariant means that we do not want to make any decisions depending on the representation of the graph in the memory (like, "take arbitrary vertex"), and the output decomposition should be the same (isomorphic) for isomorphic input graphs. Given such an isomorphic-invariant treewidth approximation algorithm, we can now compute the decompositions of both input graphs, and compare given pairs (graph, its tree decomposition), as described in the previous paragraph. Note that for this approach we do not need to output exactly *one* tree decomposition; we can output, say, of them, and compare every pair of decompositions for two input graphs for the Graph Isomorphism problem; we only need that the set of output decompositions is isomorphic invariant.

To cope with this new task, let us look at the known treewidth approximation algorithms; in particular, the arguably simplest one - the Robertson-Seymour algorithm. This algorithm provides a constant approximation in time, where is the treewidth of the input -vertex graph . It is a recursive procedure that decomposes a part of the input graph, given a requirement that a set should be contained in the top bag of the output decomposition. Think of as an interface to the rest of the graph; we will always have , but for technical reasons the set could be larger. During the course of the algorithm we maintain an invariant .

In the leaves of the recursion we have , and we output a single bag . If is small, say, , then we can add an arbitrary vertex to and recurse. The interesting things happen when grows beyond the threshold .
As the graph is of treewidth , but , in an optimal decomposition of the set is spread across many bags. A simple argument shows that there exists a bag , , such that every component of contains at most vertices of . The algorithm takes as a root bag (note that ), and recurses on every connected component of ; formally, for every connected component of , we recurse on with . Since every component of contains at most vertices of , in every recursive call the new set is of size at most .
In the above algorithm, there are two steps that are very deeply not isomorphic-invariant: "take an arbitrary vertex to " in the case of small , and "take any such " in the case of large . We start fixing the algorithm in the second, more interesting case.
Before we start, let us think how we can find such a set - the argument provided two paragraphs ago only asserted its existence. One of the ways to do it is to iterate through all disjoint sets of size exactly each, and check if the minimum separator between and in is of size at most (such a separator can contain vertices of or , these are deletable as well). If such a separator is found, it is a good candidate for the set - it does not necessarily have the property that every connected component of contains at most half of the vertices of , but the claim that in the recursive calls the size of the set decreased is still true. Of course, in this approach we have two not isomorphic-invariant choices: the choice of and , and the choice of the minimum separator .
Luckily, an (almost) isomorphic-invariant way to make the second choice has already been well understood: by submodularity of cuts, there exists a well-defined notion of the minimum cut closest to , and the one closest to . But how about the choice of and ?
The surprising answer is: it works just fine if we just throw into the constructed bag *all* separators for *every choice* of and . That is, we start with the tentative bag , we iterate over all such (ordered) pairs , and throw into the constructed bag the minimum cut between and that is closest to , as long as it has size at most . We recurse on all connected components of as before; the surprising fact is that the sizes of the sets in the recursive calls did not grow. To prove this fact, we analyse what happens to the components of when you add cuts one-by-one; a single step of this induction turns out to be an elementary application of submodularity. Furthermore, note that if the size of is bounded in terms of , so is the set of the bag : .

Having made isomorphic-invariant the "more interesting" case of the Robertson-Seymour approximation algorithm, let us briefly discuss the case of the small set : we need to develop an isomorphic-invariant way to grow this set. Here, we need some preprocessing: by known tricks, we can assume that (a) the input graph does not contain any clique separators, and (b) if , then the minimum cut between and is of size at most . Furthermore, observe that in our algorithm, contrary to the original Robertson-Seymour algorithm, we always maintain the invariant that and is connected. Thus, is never a clique in , and, if , we can throw into a bag the minimum cut between and that is closest to , for every ordered pair where , .
In this way, the lack of clique separators ensures that we always make a progress in the algorithm, by "eating" at least one vertex of . The bound on the size of minimum cut between two nonadjacent vertices ensures that the bag created in this way is of size , and so are the sets in the recursive calls. Consequently, our algorithm computes in an isomorphic-invariant way a tree decomposition with adhesions of size and bags of size .
Well, there is one small catch - neither of the aforementioned steps is good to *start* the algorithm, to provide the initial call of the recursion; the Robertson-Seymour approximation starts with just and . Here, we can start with and for every pair of nonadjacent vertices, as in this call the step with the small set will work fine. But this produces not a single isomorphic-invariant tree decomposition, but a family of decompositions - which is still fine for the isomorphism test.

A cautious reader would also notice that the described algorithm results in a double-exponential dependency on the parameter in the running time, contrary to the claim of the term. Getting down to this dependency requires a bit more technical work; we refer to the full version of our paper for details.

]]>Let us narrow down the dynamic scenario we consider: say only the vertices of one side of the graph come in online, and at the time they show up they reveal all their adjacent edges. This scenario is easily motivated as follows.

There is a set of servers and a set of jobs to be executed on these servers. Every job comes with a list of servers capable of performing the job. Of course it is reasonable to serve as many jobs as possible, hence the maximum job-server matching is highly desired. Having that motivation in mind, an online scenario seems to be the most natural: jobs come in online one at the time, and request to be matched to one of the chosen servers. We care to match the job whenever its possible, so we allow some busy servers to be reallocated.

Now the question is, what is a good way of reallocating the servers, so that the dynamic algorithm can benefit from it? We adopt the following measure: each reallocation involves some reallocating cost. We want to minimize the cost of reallocating the servers.

We associate with each server an attribute called , which states how many times the server has been reallocated in the entire process. The parameter stands for time. We see the entire process of adding jobs as a sequence of turns, in each turn a new job appears with the list of eligible servers. The attribute describes the number of times was reallocated up to turn . These attributes guide us when we search for augmenting paths. We try to avoid servers with high ranks. This should distribute the necessary reallocations more or less evenly among the servers.

In order to follow this approach, a certain greedy strategy comes to mind. When trying to match a new job, choose the augmenting path which minimizes the maximum rank of a server along this path. This strategy has one substantial disadvantage. If any augmenting path that we can choose to match the new job contains a vertex of high rank , then we are allowed to rematch all servers of ranks at most . That is clearly an overhead. We hence define another attribute, , for every job . This attribute says what is the rank of the lowest ranked path from to any unmatched server. When we try to match job , we search for the alternating path along which the tiers of jobs do not increase. We call such a path a tiered path. In other words, a tiered path minimizes the maximal rank on its every suffix. This seems natural: why to re-enter vertices of high rank when we can avoid them.

It turns out that this simple strategy does quite well: the ranks (and hence also the tiers) do not grow above . That means, that each server gets reallocated at most times. This is already interesting. Moreover, if we knew how to efficiently choose the right augmenting paths, the total work would be . We have an algorithm that finds all the augmenting paths in the total time , what matches the offline time of HK.

So let us first take a look on how the bound on the maximum rank is obtained. First of all, we direct the edges of the graph according to the current matching: the matched edges point from servers to jobs, while the unmatched edges point the other way around. Now, directed paths are alternating, so in each turn we need to find a directed path from the new job to a free server and reverse the edges along the path. We first show that the servers of high ranks are far from the unoccupied servers: the directed distance from any server to an unmatched server in turn is at least .

We now look at any set of vertex disjoint directed paths covering all free servers in turn before applying the augmenting path. Note, that there are no outgoing edges from free servers, so the paths end there. The rank of the directed path present in the graph in turn is the maximum rank of a server on it. Let's call the augmenting path applied in turn . We analyze the augmentation process backwards. In turn , before applying , there exists a set of vertex disjoint paths covering free servers, such that:

- every path has its counterpart , where is an injection
- has rank at least as high as , unless 's rank is smaller or equal to one plus the rank of : then the rank of may be one less then the rank of
- there is a path in that is not in the image of and has rank at least the rank of

This observation may be translated as follows. Let us, for every path in , draw a vertical bar of height equal to its rank. Let us now sort the bars in descending order and put them next to each other, as shown in Figure 1 to the left. These bars are the ranks of the paths in turn . When we take a step back to turn , we have another set of bars corresponding to paths from turn , where one additional bar pops out. Moreover, some bars may have decreased by one, but all the bars that decreased are dominated (with respect to height) by the newly added bar. This is shown in Figure 1 to the right. The process ends when we reach turn , and there is bars of height zero.

Now we move to bounding the maximum rank. The maximum rank, say , will appear on some path in some turn . We take a look at set consisting of this single path. There is only one bar of height . In the previous turn, either there is still a bar of the height , or there are two bars of height . Every time the bars decrease, there comes another bar that dominates the decreased bars. Somewhere on the way back to turn there is a set of bars with the sum of heights quadratic in . The bars, however, correspond to vertex disjoint paths, and the heights of the bars are the lower bounds on the lengths of these paths. Hence, there is vertices in the graph and .

The question that remains is whether we are able to efficiently find these paths. The main problem here is that we need augmenting paths where the tiers of jobs along the path do not increase. This is not a good news: the tiers are difficult to maintain upon the reversal of the edges on the entire augmenting path. The idea is to maintain them in a lazy manner. For each job , instead of its actual tier, the algorithm maintains an attribute . Subscript LB stands for lower bound, as we maintain the invariant that . When a new vertex turns up in some turn, is set to . The algorithm repeatedly tries to find (in the directed graph) a tiered (according to the maintained lower bounds for tiers) directed path from to a free server. It executes a search routine from , traversing only the vertices with ranks and 's bounded by . Once a job with is discovered, the upper bound on the ranks and 's of vertices visited next is recursively set to . This goes on until one of the two things happen. It might be that a free server is discovered. Then we found an augmenting path, along which the 's of the vertices are their actual tiers (the path that we found is a witness for that). We reverse the edges along the augmenting path and increase the ranks of the reallocated servers. It might also happen that the search fails. This means, that the algorithm detects a group of vertices whose 's are lower than their actual tiers. The algorithm then rightfully increases the 's associated with these vertices. It continues the search from the point where it failed. The difference is that now it can search further, as it is allowed to visit vertices with higher 's than before. The general idea is that whenever a vertex is visited by the algorithm, either its or its rank is increased. Unfortunately upon every such visit the algorithm may touch all the edges adjacent to the visited vertex. These edges, however, will be touched in total times each. The total time amounts to .

]]>