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.
information theory
Researchers Defeat Randomness to Create Ideal Code
By carefully constructing a multidimensional and well-connected graph, a team of researchers has finally created a long-sought locally testable code that can immediately betray whether it’s been corrupted.
mathematical physics
Mathematicians Prove Melting Ice Stays Smooth
After decades of effort, mathematicians now have a complete understanding of the complicated equations that model the motion of free boundaries, like the one between ice and water.
geometry
Mathematicians Identify Threshold at Which Shapes Give Way
A new proof establishes the boundary at which a shape becomes so corrugated, it can be crushed.