computational complexity
Computer Science Proof Unveils Unexpected Form of Entanglement
Three computer scientists have posted a proof of the NLTS conjecture, showing that systems of entangled particles can remain difficult to analyze even away from extremes.
quantum computing
Quantum Algorithms Conquer a New Kind of Problem
Computer scientists have found a new type of problem that quantum computers can solve dramatically faster than their classical counterparts.
Q&A
The Computer Scientist Who Parlays Failures Into Breakthroughs
Daniel Spielman solves important problems by thinking hard — about other questions.
computational complexity
How Computer Scientists Learned to Reinvent the Proof
Why verify every line of a proof, when just a few checks will do?
computational complexity
Computer Scientists Prove That Certain Problems Are Truly Hard
Finding out whether a question is too difficult to ever solve efficiently depends on figuring out just how hard it is. Researchers have now shown how to do that for a major class of problems.
neural networks
Researchers Gain New Understanding From Simple AI
Language processing programs are notoriously hard to interpret, but smaller versions can provide important insights into how they work.
cryptography
Cryptographers Achieve Perfect Secrecy With Imperfect Devices
For the first time, experiments demonstrate the possibility of sharing secrets with perfect privacy — even when the devices used to share them cannot be trusted.
artificial intelligence
Computer Scientists Prove Why Bigger Neural Networks Do Better
Two researchers show that for neural networks to be able to remember better, they need far more parameters than previously thought.
information theory
Qubits Can Be as Safe as Bits, Researchers Show
A new result shows that quantum information can theoretically be protected from errors just as well as classical information can.