Algorithms

Computer scientist Lance Fortnow writes that by embracing the computations that surround us, we can begin to understand and tame our seemingly random world.

By making use of randomness, a team has created a simple algorithm for estimating large numbers of distinct objects in a stream of data.

After years of false starts, a team of computer scientists has found a way to efficiently deduce the Hamiltonian of a physical system at any constant temperature.

Researchers have shown how to find the simplest description of a data set faster than by simply checking every possibility.

The prolific researcher found deep connections between randomness and computation and spent a career influencing cryptographers, complexity researchers and more.

Researchers have shown that a problem relating to the energy of a quantum system is easy for quantum computers but hard for classical ones.

By eliminating a hidden inefficiency, computer scientists have come up with a new way to multiply large matrices that’s faster than ever.

Seventy years after the invention of a data structure called a hash table, theoreticians have found the most efficient possible configuration for it.

Two mathematicians have shown that origami can, in principle, be used to perform any possible computation.