The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.
In computational complexity theory, the unique games conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP, then for many important problems it is not only impossible to get an exact solution in polynomial time, but also impossible to get a good polynomial-time approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.
ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth.
Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.
The Machtey Award is awarded at the annual IEEE Symposium on Foundations of Computer Science (FOCS) to the author(s) of the best student paper(s). A paper qualifies as a student paper if all authors are full-time students at the date of the submission. The award decision is made by the Program Committee.
Frances Foong Chu Yao is a Taiwanese-American mathematician and theoretical computer scientist. She is currently a Chair Professor at the Institute for Interdisciplinary Information Sciences (IIIS) of Tsinghua University. She was Chair Professor and Head of the Department of computer science at the City University of Hong Kong, where she is now an honorary professor.
The ACM Symposium on Principles of Distributed Computing (PODC) is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery.
The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computing Machinery special interest group SIGACT. Acceptance rate of STOC, averaged from 1970 to 2012, is 31%, with the rate of 29% in 2012.
The IEEE Annual Symposium on Foundations of Computer Science (FOCS) is an academic conference in the field of theoretical computer science. FOCS is sponsored by the IEEE Computer Society.
Ran Raz is a computer scientist who works in the area of computational complexity theory. He was a professor in the faculty of mathematics and computer science at the Weizmann Institute. He is now a professor of computer science at Princeton University.
Michael Ezra Saks is an American mathematician. He is currently the Department Chair of the Mathematics Department at Rutgers University (2017–) and from 2006 until 2010 was director of the Mathematics Graduate Program at Rutgers University. Saks received his Ph.D. from the Massachusetts Institute of Technology in 1980 after completing his dissertation titled Duality Properties of Finite Set Systems under his advisor Daniel J. Kleitman.
Ashok K. Chandra was a computer scientist at Microsoft Research in Mountain View, California, United States, where he was a general manager at the Internet Services Research Center. Chandra received his PhD in Computer Science from Stanford University, an MS from University of California, Berkeley, and a BTech from IIT Kanpur. He was previously Director of Database and Distributed Systems at IBM Almaden Research Center.
Baruch Awerbuch is an Israeli-American computer scientist and a professor of computer science at Johns Hopkins University. He is known for his research on distributed computing.
Henry Cohn is an American mathematician. He is a principal researcher at Microsoft Research and an adjunct professor at MIT. In collaboration with Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska, he solved the sphere packing problem in 24 dimensions. In 2003, with Chris Umans he initiated a group-theoretic approach to matrix multiplication, and is a core contributor to its continued development with various coauthors.
Philip N. Klein is an American computer scientist and professor at Brown University. His research focuses on algorithms for optimization problems in graphs.
Tali Kaufman is an Israeli theoretical computer scientist whose research topics have included property testing, expander graphs, coding theory, and randomized algorithms with sublinear time complexity. She is a professor of computer science at Bar-Ilan University, and a fellow of the Israel Institute for Advanced Studies.
