XRDS

Crossroads The ACM Magazine for Students

Sign In

Association for Computing Machinery

Articles Tagged: Computability

Articles & Features

Kristin Lauter on Cryptography and Mathematics

SECTION: Features

Kristin Lauter on Cryptography and Mathematics

There are unique challenges posed by cryptography research. This interview examines potential threats to modern security techniques and how to overcome them.

By Shashank Agrawal, Billy Rathje, March 2015

PDF | HTML | In the Digital Library

An interview with Robert Soare

An interview with Robert Soare

University of Chicago's Robert Soare, the Paul Snowden Russell Distinguished Service Professor of Mathematics and Computer Science, offers his reflections on Alan Turing.

By Arefin Huq, March 2012

PDF | HTML | In the Digital Library

Invitation to complexity theory

Invitation to complexity theory

Complexity theory provides new viewpoints on various phenomena that were considered by past thinkers.

By Oded Goldreich, March 2012

PDF | HTML | In the Digital Library

The tale of the PCP theorem

The tale of the PCP theorem

How the search for the limits of computing led to the discovery of the unexpected power of proofs.

By Dana Moshkovitz, March 2012

PDF | HTML | In the Digital Library

Software verification and validation with destiny

This paper presents an introduction to computer-aided theorem proving and a new approach using parallel processing to increase power and speed of this computation. Automated theorem provers, along with human interpretation, have been shown to be powerful tools in verifying and validating computer software. Destiny is a new tool that provides even greater and more powerful analysis enabling greater ties between software programs and their specifications.

By Josiah Dykstra, April 2002

PDF | HTML | In the Digital Library