Tag Archives: Algorithm

Lunch & Learn: Computational Intractability: A Barrier for Computers, Man, and Science with Sanjeev Arora

locksilverside.jpgWhile computers are exponentially more powerful and increasingly important in both society and in every area of scholastic inquiry, modern computers appear to be incapable of solving certain problems. In recent decades, computer scientists have begun to develop an understanding of what makes some computational tasks “intractable” not just for current computers but for all foreseeable computers, even if they were joined together.
Princeton is the lead institution for a new $10 million National Science Foundation grant for the study of computational intractability. At the Dec 10 Lunch ‘n Learn seminar, Sanjeev Arora, the principal investigator on the new grant, Professor of Computer Science, the Director of the Center for Theoretical Computer Science, and the Director of the Center for Intractability gave an overview of both the field and what the new center is trying to accomplish.

Continue reading

Lunch & Learn: Why Your Humble iPod May Be Holding the Biggest Mystery in All of Science with Bernard Chazelle

chazelle1.jpgIn 1965, Intel co-founder Gordon Moore predicted that the number of transistors placed on an integrated circuit would double approximately every two years. That prediction, notes Bernard Chazelle, Computer Science Professor at Princeton, if anything underestimated the results during the past half century and should continue for at least another decade. Moore’s Law, he posits, is responsible for most of the desktop and hip-pocket wonders of the computer age, notably remarkable improvements in processing speed, memory capacity, and network bandwidth.
Moore’s Law correctly predicted revolutionary technological and social change in the late 20th century. But by 2020 if not before, as transistor features approach just atoms in width, Moore’s Law will have run its course. New technologies may replace integrated circuit technologies to extend Moore’s Law for decades; Chazelle argues that the years ahead will usher in the era of the “Algorithm,” a notion which, he contends, may prove to be the most disruptive and revolutionary scientific paradigm since quantum mechanics.

Continue reading