# Category Computer Science

## 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 […]

## Graph mining with a faulty oracle

Pythia was a powerful and respected woman in Ancient Greece. She was the high priestess of the Temple of Apollo at Delphi. I was surprised to read in the Wikipedia article that the name Pythia is derived from the verb πύθειν (púthein) which means “to rot”; I find this to be unlikely. An etymology that sounds […]

## Riddles from the White House

It is well known that President Obama was a strong supporter of computer science, and was the first US President to write code. During his presidency, brain teasers were published from the White House web page. I came across this nice riddle that illustrates how Boolean logic can be used to achieve success in cooperation. […]

## 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, […]

## Dense subgraph discovery applications

Recently, I compiled a collection of applications that rely on dense subgraph discovery for my KDD’15 tutorial with Aris Gionis. In general, dense subgraph discovery is a key graph mining primitive. While by “dense” we generally mean subgraphs which are large enough and contain many edges, the exact notion of dense is application dependent. The […]

## Provably Fast Inference of Latent Features from Networks

Latent feature learning: where overlapping communities, correlation clustering, binary matrix factorization and extremal graph theory meet Motivation: Suppose we are given the following. Agents: Five agents, represented by . Binary vertex features. An agent can either be interested or not in each out of three news categories business, entertainment, sports. Each interest is represented by a […]