Category Graph Algorithms

The densest subgraph problem with negative weights

Few days ago I uploaded on Arxiv our preprint “Novel Dense Subgraph Discovery Primitives: Risk Aversion and Exclusion Queries”.  This is joint work with Tianyi, Nao, and Jakub. In this paper we study the following extension of the densest subgraph problem (DSP) that is known to be solvable exactly in polynomial time on graphs with […]

Denoising binary images

Data science is transforming the world: we already see self-driving cars moving from research to production, data-driven cancer diagnostic systems, machine learning trader bots and lots of other exciting technologies because the corresponding problems have been reduced to understanding data. While the science of data for centuries was known as statistics, computer scientists, together with […]

Writing history in about 20 minutes

    Here is an abstract from an interview with Edsger Dijkstra about his shortest path algorithm. There’s a curious story behind your “shortest path” algorithm. In 1956 I did two important things, I got my degree and we had the festive opening of the ARMAC.c We had to have a demonstration. Now the ARRA, […]