It has been a very nice event, full of interesting short presentations of past and current PhD students. As Luca and Alessio (which are respectively current and past PhD students) were not in Italy, I presented a short summary of our works about community detection.

There is a video and there are also the pictures

These are shorten versions of the original books by Runestone Interactive. This version has been modified by me for the lectures of Laboratorio di Algoritmi at Informatica Umanistica, University of Pisa. I modified the original version according to GNU Free Documentation License, Version 1.3. I am redistributing the new material under the same License. The original Forward, Prefaces, and Contributor List can be accessed at the end of the table of contents.

Check out the table of contents for basic programming or the one for algorithms and data structures.

Benefits of this book:
– You can experiment with activecode examples right in the book
– You can do your homework right in the textbook.
– Interactive questions make sure that you are on track and help you focus.
– Codelens helps you develop a mental model of how Python works.

https://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Currently there are 107 proofs. Probably, all of them are wrong (otherwise, probably we would know the guy) and the nice scoring function provided by Scott Aaranson here can be applied. This scoring function is the number of signs exhibited by the paper among the “Ten Signs a Claimed Mathematical Breakthrough is Wrong”.

1. The authors don’t use TeX.
2. The authors don’t understand the question.
3. The approach seems to yield something much stronger and maybe even false (but the authors never discuss that).
4. The approach conflicts with a known impossibility result (which the authors never mention).
5. The authors themselves switch to weasel words by the end.
6. The paper jumps into technicalities without presenting a new idea.
7. The paper doesn’t build on (or in some cases even refer to) any previous work.
8. The paper wastes lots of space on standard material.
9. The paper waxes poetic about “practical consequences,” “deep philosophical implications,” etc.
10. The techniques just seem too wimpy for the problem at hand.

Thanks to all the coauthors Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi and Henning Meyerhenke. This work is the result of a merge between our work (see here) and the work by Elisabetta and Henning. It’s a pleasure to start this new collaboration.

This is the abstract of the final paper.

Centrality indices are widely used analytic measures for the importance of nodes in a network.
Closeness centrality is very popular among these measures. For a single node v, it takes the sum of
the distances of v to all other nodes into account. The currently best algorithms in practical applications
for computing the closeness for all nodes exactly in unweighted graphs are based on breadth-first search (BFS) from every node. Thus, even for sparse graphs, these algorithms require quadratic running time in the worst case,
which is prohibitive for large networks.

In many relevant applications, however, it is unnecessary to compute closeness values for all nodes. Instead,
one requires only the k nodes with the highest closeness values in descending order.
Thus, we present a new algorithm for computing this top-k ranking in unweighted graphs. Following the rationale of previous work, our algorithm significantly reduces the number of traversed edges. It does so by computing upper bounds on the closeness and stopping the current BFS search when k nodes already have higher closeness than the bounds computed for the other nodes.

In our experiments with real-world and synthetic instances of various types, one of these new bounds is good for small-world graphs with low diameter (such as social networks), while
the other one excels for graphs with high diameter (such as road networks). Combining them
yields an algorithm that is faster than the state of the art for top-k computations for all test instances,
by a wide margin for high-diameter graphs.

Finally, we prove that the quadratic worst-case complexity cannot be improved on directed, disconnected graphs, under reasonable complexity assumptions.

 

Thanks to the organisers Pierluigi Crescenzi, Michele Loreti, Betti Venneri for the nice event.

Thanks to the invited speaker Luca Aceto and thanks to all the participants.

You can see the full collection here. It includes an impressive collection of Fender Stratocaster Sunburst year by year, from the first one in 1954 to the last one in 1974. For some older models, there is even the name of the girl or guy was working on the guitar.

You can read the history of Fender brand here or you can read the book by Tom Wheleer, Stratocaster Chronicles. You can see a tour of Fender factory in 1959 here:

In the same web site you can also read the interesting story of Marshall amplifiers.

For each class of the followings:

• Geometry
• Graph
• Hypergraph
• Matroid
• Order
• Other
• Permutation
• SAT
• Set
• String

several enumeration problems are enumerated. For each of them, the state of the art is given. Enjoy!