Related Research Articles
In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory.
The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM).
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.
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.
László "Laci" Babai is a Hungarian professor of computer science and mathematics at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields.
Aleksandr Aleksandrovich Razborov, sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist. He is Andrew McLeish Distinguished Service Professor at the University of Chicago.
In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.
Umesh Virkumar Vazirani is an Indian–American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms.
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.
A CUR matrix approximation is a set of three matrices that, when multiplied together, closely approximate a given matrix. A CUR approximation can be used in the same way as the low-rank approximation of the singular value decomposition (SVD). CUR approximations are less accurate than the SVD, but they offer two key advantages, both stemming from the fact that the rows and columns come from the original matrix :
In the study of hierarchical clustering, Dasgupta's objective is a measure of the quality of a clustering, defined from a similarity measure on the elements to be clustered. It is named after Sanjoy Dasgupta, who formulated it in 2016. Its key property is that, when the similarity comes from an ultrametric space, the optimal clustering for this quality measure follows the underlying structure of the ultrametric space. In this sense, clustering methods that produce good clusterings for this objective can be expected to approximate the ground truth underlying the given similarity measure.
Benjamin E. Rossman is an American mathematician and theoretical computer scientist, specializing in computational complexity theory. He is currently an associate professor of computer science and mathematics at Duke University.
In convex geometry and polyhedral combinatorics, the extension complexity of a convex polytope is the smallest number of facets among convex polytopes that have as a projection. In this context, is called an extended formulation of ; it may have much higher dimension than .
Philip N. Klein is an American computer scientist and professor at Brown University. His research focuses on algorithms for optimization problems in graphs.
A parameterized approximation algorithm is a type of algorithm that aims to find approximate solutions to NP-hard optimization problems in polynomial time in the input size and a function of a specific parameter. These algorithms are designed to combine the best aspects of both traditional approximation algorithms and fixed-parameter tractability.
The small set expansion hypothesis or small set expansion conjecture in computational complexity theory is an unproven computational hardness assumption. Under the small set expansion hypothesis it is assumed to be computationally infeasible to distinguish between a certain class of expander graphs called "small set expanders" and other graphs that are very far from being small set expanders. This assumption implies the hardness of several other computational problems, and the optimality of certain known approximation algorithms.
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.
Prasad Raghavendra is an Indian-American theoretical computer scientist and mathematician, working in optimization, complexity theory, approximation algorithms, hardness of approximation and statistics. He is a professor of computer science at the University of California at Berkeley.
References
- ↑ "News from the National Academy of Sciences". National Academy of Sciences. January 16, 2018.
- ↑ "Professors". ETH Zürich.
- ↑ "curriculum vitæ". David Steurer.
- ↑ "Invited Section Lectures - List of Speakers". ICM 2018.
- ↑ "Michael and Shiela Held Prize". National Academy of Sciences.
- ↑ Lee, James; Raghavendra, Prasad; Steurer, David (June 2015). "Lower bounds on the size of semidefinite programming relaxations". STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. STOC. Portland, Oregon: ACM. pp. 567–576. arXiv: 1411.6317 .
- ↑ Dinur, Irit; Steurer, David (May 2014). "Analytical approach to parallel repetition". STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing. STOC. New York: ACM. pp. 624–633. arXiv: 1305.1979 .
