Computation

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.” 

Prof. Ryan Williams speaks with New Scientist reporter Matthew Sparkes about his finding concerning the relationship between the amount of memory a computation requires and how long it takes, a discovery that has “wowed computer scientists.” Says Williams of the discovery: “It kind of shakes my world view. I’m still just shocked that it even exists.”

Graduate student Rida Qadri writes for Wired about the National Database and Registration Authority, a kinship-based digital ID system used in Pakistan. “Pakistan’s experience with creating databases that encode kinship reveals important lessons about the complexities of building digital ID systems,” writes Qadri “Database design is not just computational. At every step, social, political, and technical decisions coalesce." 

Research by Prof. Erik Demaine looks to find the best method for wrapping spherical objects, writes Sophie Bushwick for Popular Science. By examining how an Austrian candy maker wraps round candies, Demaine found that foil is the best material as “it makes lots of little tiny crinkles, or folds.”

Graduate student Greg Borenstein speaks with BBC News about his efforts to make chess more appealing as a spectator sport. “There’s really something magical about the ability to use computation and statistics to take that drama and that excitement and those brilliant moments and make them visible,” Borenstein explains. 

Katie Collins writes for Wired that MIT researchers have developed a new algorithm that will allow delivery drones to monitor their own health. “Drones will be able to keep an eye on their ability to do the job by predicting fuel levels and checking on the condition of propellers, cameras and other sensors,” writes Collins. 

BetaBoston reporter Nidhi Subbaraman writes that MIT researchers are developing new techniques to make future delivery drones more functional and efficient. “We have broken the large problem into lots of small problems,” says Ali-akbar Agha-mohammadi.