The #P-complete problems form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties:
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.
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 Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.
Vijay Virkumar Vazirani is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine.
Christos Charilaos Papadimitriou is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.
Noga Alon is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.
Jaroslav (Jarik) Nešetřil is a Czech mathematician, working at Charles University in Prague. His research areas include combinatorics, graph theory, algebra, posets, computer science.
Martin Charles Golumbic is a mathematician and computer scientist known for his research on perfect graphs, graph sandwich problems, compiler optimization, and spatial-temporal reasoning. He is a professor emeritus of computer science at the University of Haifa, and was the founder of the journal Annals of Mathematics and Artificial Intelligence.
Kurt Mehlhorn is a German theoretical computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science.
Michael Stewart Paterson, is a British computer scientist, who was the director of the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick until 2007, and chair of the department of computer science in 2005.
Michael Ralph Fellows AC HFRSNZ MAE is a computer scientist and the Elite Professor of Computer Science in the Department of Informatics at the University of Bergen, Norway as of January 2016.
János Pach is a mathematician and computer scientist working in the fields of combinatorics and discrete and computational geometry.
Mark Richard Jerrum is a British computer scientist and computational theorist.
Alistair Sinclair is a British computer scientist and computational theorist.
Martin Edward Dyer is a professor in the School of Computing at the University of Leeds, Leeds, England. He graduated from the University of Leeds in 1967, obtained his MSc from Imperial College London in 1968 and his PhD from the University of Leeds in 1979. His research interests lie in theoretical computer science, discrete optimization and combinatorics. Currently, he focuses on the complexity of counting and the efficiency of Markov chain algorithms for approximate counting.
Esther M. (Estie) Arkin is an Israeli–American mathematician and computer scientist whose research interests include operations research, computational geometry, combinatorial optimization, and the design and analysis of algorithms. She is a professor of applied mathematics and statistics at Stony Brook University. At Stony Brook, she also directs the undergraduate program in applied mathematics and statistics, and is an affiliated faculty member with the department of computer science.
In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.
In economics, a budget-additive valuation is a kind of a utility function. It corresponds to a person that, when given a set of items, evaluates them in the following way:
Shmuel Onn is a mathematician, Professor of Operations Research and Dresner Chair at the Technion - Israel Institute of Technology. He is known for his contributions to integer programming and nonlinear combinatorial optimization.
