Impactx2 Logo and Photo

Impact x2 Qais

Impactx2 Content

How can we work together to promote better cultural understanding worldwide?

Qais Akbar Omar (GRS’16), a graduate student in the Creative Writing Program, has published a much-praised memoir, A Fort of Nine Towers: An Afghan Family Story. He recalls how the violence and tumult of civil war jolted his family, who, despite losing relatives, their home, and possessions, continued to nurture his wish to attend a university.

Impactx2 Call to Action

With your help, students like Qais gain the skills they need to tell their story and give us a broader understanding of the world.

Will you support CAS?

Knuth Prize Goes to Computer Science’s Levin

October 22nd, 2012

Leonid Levin’s career began in the Soviet Union, where he conducted pathbreaking work on computational complexity. Now a CAS Professor of Computer Science, Levin is a leader in the fields of cryptography theory and algorithmic information.

This month, he gave the Knuth Prize Lecture to a gathering of colleagues at the Symposium on Foundations of Computer Science in New Brunswick, NJ. The IEEE Computer Society, which sponsored the symposium, and the Association for Computing Machinery honored Levin with the 2012 Knuth Prize.

The Knuth Prize is named in honor of Donald Knuth of Stanford University who has been called the “father” of the analysis of algorithms. Levin received this year’s prize for his visionary research in complexity, cryptography, and information theory, including the discovery of NP-completeness. Working in the Soviet Union at the same time as Stephen Cook in the United States, Levin made his discovery of NP-completeness, the core concept of computational complexity. This discovery best explains why many computational problems require prohibitively slow brute-force solutions. Levin also developed the theory of “average-case NP-completeness,” for problems considered intractable on average.

With co-authors Laszlo Babai, Lance Fortnow, and Mario Szegedy, Levin also provided a key step in the proof of the celebrated PCP Theorem, the cornerstone of the theory of computational hardness of approximation. It investigates the inherent difficulty in designing efficient approximation algorithms for various optimization problems. Together, this team proposed the notion of “holographic proofs,” whose correctness can be checked efficiently by a program that samples only a small fraction of the bits.

In cryptography theory, Levin co-authored the “Goldreich-Levin hardcore bit” with Oded Goldreich, which has become an essential ingredient in many subsequent key results to establish improved security. He also changed the landscape of Kolmogorov complexity, a modern notion of randomness dealing with the quantity of information in individual objects. Andrey Kolmogorov, a Russian mathematician, was Levin’s doctoral advisor at Moscow University. Levin’s advances have become essential tools in the research area of algorithmic information.

Post Your Comment