Sign In

Communications of the ACM


Refine your search:
datePast Month

From Computational Complexity

Jim Simons (1938-2024)

Jim Simons passed away Friday at the age of 86. In short he was a math professor who quit to use math to make money before it was fashionable and used part of his...

From Computational Complexity

Favorite Theorems: Dichotomy

A constraint satisfaction problem has a group of constraints applied to a set of variables and we want to know if there is a setting of the variables that makeA...

From Computational Complexity

Our Obsession with Proofs

Bullinger's post on this blog last week focused on Vijay Vazirani's public obsession of finding a proof for the 1980 Micali-Vazirani matching algorithm. But why...

From Computational Complexity

Is Persistence an Anachronism?

Guest post by Martin BullingerVery recently, Vijay Vazirani's paper A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length got accepted...

From Computational Complexity

Favorite Theorems: Quantum Provers

For our next favorite theorem, we look at the surprising power of provers who share entangled bits. If you can prove something to an arbitrarily computable verifier...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account