In the Media

Prof. Ryan Williams has published a new proof that explores computational complexity and flips the script on years of assumptions about the trade-offs between computation space and time, reports Max Springer for Scientific American. Williams found that “any problem can be transformed into one you can solve by cleverly reusing space, deftly cramming the necessary information into just a square-root number of bits,” Springer explains. “This progress is unbelievable,” says Mahdi Cheraghchi of the University of Michigan. “Before this result, there were problems you could solve in a certain amount of time, but many thought you couldn’t do so with such little space.”