ACM Group Honors Research Team For Rare Finding In Computer Security
ACM GROUP HONORS RESEARCH TEAM FOR RARE FINDING IN COMPUTER SECURITY
Washington, DC - May 16, 2007 - ACM's Special Interest Group on Algorithms and Computing Theory (SIGACT) has recognized the contribution of two computer scientists, Alexander A. Razborov and Steven Rudich, who developed a rare finding to address a fundamental problem facing computer and network security techniques as well as many optimization techniques that make these functions work more efficiently or use fewer resources. This challenge, known as the P vs. NP Problem, is a classic question on the limits of proof and computation that has resisted resolution over the years. It applies to solving complex mathematical problems common in safeguarding the security of ATM cards, computer passwords, and electronic commerce. SIGACT and the European Association for Theoretical Computer Science (EATCS) will present the 2007 Gödel Prize for outstanding papers in theoretical computer science to Razborov and Rudich at the ACM Symposium on Theory of Computing (STOC), June 11-13, in San Diego, CA.
In a paper titled "Natural Proofs" originally presented at the 1994 ACM STOC, the authors found that a wide class of proof techniques cannot be used to resolve this challenge unless widely held conventions are violated. These conventions involve well-defined instructions for accomplishing a task that rely on generating a sequence of numbers (known as pseudo-random number generators). The authors' findings apply to computational problems used in cryptography, authentication, and access control. They show that other proof techniques need to be applied to address this basic, unresolved challenge.
The findings of Razborov and Rudich, published in a journal paper entitled "Natural Proofs" in the Journal of Computer and System Sciences in 1997, address a problem that is widely considered the most important question in computing theory. It has been designated as one of seven Prize Problems by the Clay Mathematics Institute of Cambridge, MA, which has allocated $1 million for solving each problem. It asks - if it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? This problem is posed to determine whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve.
The paper proves that there is no so-called "Natural Proof" that certain computational problems often used in cryptography are hard to solve. Such cryptographic methods are critical to electronic commerce, and though these methods are widely thought to be unbreakable, the findings imply that there are no Natural Proofs for their security.
Alexander Razborov, a mathematician and computational theorist, is a leading researcher at the Russian Academy of Science Steklov Mathematical Institute in Moscow, Russia. He was awarded the Nevanlinna Prize of the International Mathematical Union in 1990, for his profound influence on recent progress in complexity theory. He is an editor of the journal Theoretical Computer Science.
Steven Rudich is Associate Professor of Computer Science at Carnegie Mellon University in Pittsburgh, PA. He is best known to his students as the teacher of 'Great Theoretical Ideas in Computer Science,' often considered one of the most difficult classes in the undergraduate computer science curriculum. He is an editor of the Journal of Cryptology as well as an accomplished magician.
STOC 2007 will be held in conjunction with the Federated Computing Research Conference (FCRC) at the Town and Country Convention Center in San Diego. The award recognizes work of a lasting and significant impact on the field of computer science theory, which often takes many years to evaluate.
The Gödel Prize, which includes an award of $5,000, is named in honor of Kurt Gödel, who was born in Austria-Hungary (now the Czech Republic) in 1906. Gödel's work has had immense impact upon scientific and philosophical thinking in the 20th century. The award recognizes his major contributions to mathematical logic and the foundations of computer science.
About ACM
ACM, the Association for Computing Machinery http://www.acm.org, is an educational and scientific society uniting the world's computing educators, researchers and professionals to inspire dialogue, share resources and address the field's challenges. ACM strengthens the profession's collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.
About SIGACT
The ACM Special Interest Group on Algorithms and Computation Theory http://sigact.acm.org fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science. The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.