Algorithms

Artificial intelligence learned how to generate text and art better than ever before, while computer scientists developed algorithms that solved long-standing problems.

Two researchers have improved a well-known technique for lattice basis reduction, opening up new avenues for practical experiments in cryptography and mathematics.

Researchers prove that navigating certain systems of vectors is among the most complex computational problems.

Three computer scientists have disproved a long-standing conjecture about a fundamental problem involving imperfect information.

What makes a quantum computer more powerful than a classical computer? It’s a surprisingly subtle question that physicists are still grappling with, decades into the quantum age.

Shor’s algorithm will enable future quantum computers to factor large numbers quickly, undermining many online security protocols. Now a researcher has shown how to do it even faster.

Mathematical proofs based on a technique called diagonalization can be relentlessly contrarian, but they help reveal the limits of algorithms.

New results break with decades of conventional wisdom for the gradient descent algorithm.

Quantum algorithms can find their way out of mazes exponentially faster than classical ones, at the cost of forgetting the path they took. A new result suggests that the trade-off may be inevitable.