Technical Perspective: Tapping the Link between Algorithmic Model Counting and Streaming

It is rare and rewarding to connect two vastly different areas of computer science. Fast randomized algorithms in model counting were discovered in the early 1980s, while the area of streaming algorithms did not take off in the theory community until the late 1990s. Only recently were these disparate areas connected in the accompanying paper, where it was observed that the algorithmic techniques developed in the two areas were strikingly similar. This connection has given us exciting streaming algorithms used in database design and in network monitoring, as well as a unified perspective on existing algorithms. What exactly is model counting?