“How can one check a routine in the sense of making sure that it is right?” asked Alan Turing in 1949, foreshadowing the science of program proving decades before it became a formally accepted field…
Computation, unlike mathematics, is a physical process that takes time, energy, and space. Humans have dominated this planet’s ecosystem by learning to share and consolidate the outcome of their computation in an unprecedented way. Now…
We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in polylogarithmic time on quasi-polynomially many processors. The result is obtained by…
As algorithms reach ever more deeply into our daily lives, increasing concern that they be “fair” has resulted in an explosion of research in the theory and machine learning communities. This talk surveys key results…
