Jeff Edmonds | |
|---|---|
 | |
| Born | August 10, 1963 (age 60) |
| Nationality | American, Canadian |
| Alma mater | University of Toronto |
| Scientific career | |
| Fields | Mathematics Computer Science |
| Institutions | York University |
| Doctoral advisor | Faith Ellen |
Jeff Edmonds is a Canadian and American mathematician and computer scientist specializing in computational complexity theory.
Edmonds received his Bachelors at Waterloo in 1987 and his Ph.D. in 1993 at University of Toronto. His thesis proved lower bounds on time-space tradeoffs. He did his post-doctorate work at the ICSI in Berkeley on secure data transmission over networks for multi-media applications. He joined Department of EECS at Lassonde School of Engineering York University in 1995. [1] [2]
Edmonds' research interests include complexity theory, scheduling, proof systems, probability theory, combinatorics and machine learning.
Edmonds is the son of another mathematician, Jack Edmonds.
In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines. The problem is usually stated as follows: two parties each receive a -bit string and . The goal is for Alice to compute the value of a certain function, , that depends on both and , with the least amount of communication between them.
Manuel Blum is a Venezuelan born American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.
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.
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, Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions.
In logic and theoretical computer science, and specifically proof theory and computational complexity theory, proof complexity is the field aiming to understand and analyse the computational resources that are required to prove or refute statements. Research in proof complexity is predominantly concerned with proving proof-length lower and upper bounds in various propositional proof systems. For example, among the major challenges of proof complexity is showing that the Frege system, the usual propositional calculus, does not admit polynomial-size proofs of all tautologies. Here the size of the proof is simply the number of symbols in it, and a proof is said to be of polynomial size if it is polynomial in the size of the tautology it proves.
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.
In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct.
Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of the Journal of Computational Geometry.
Richard Erwin Cleve is a Canadian professor of computer science at the David R. Cheriton School of Computer Science at the University of Waterloo, where he holds the Institute for Quantum Computing Chair in quantum computing, and an associate member of the Perimeter Institute for Theoretical Physics.
In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the fastest algorithm for matrix multiplication is of major practical relevance.
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.
Richard Ryan Williams, known as Ryan Williams, is an American theoretical computer scientist working in computational complexity theory and algorithms.
Toniann Pitassi is a Canadian-American mathematician and computer scientist specializing in computational complexity theory. She is currently Jeffrey L. and Brenda Bleustein Professor of Engineering at Columbia University and was Bell Research Chair at the University of Toronto.
The Even–Paz algorithm is an computationally-efficient algorithm for fair cake-cutting. It involves a certain heterogeneous and divisible resource, such as a birthday cake, and n partners with different preferences over different parts of the cake. It allows the n people to achieve a proportional division.
In computer science, the Robertson–Webb (RW) query model is a model of computation used by algorithms for the problem of fair cake-cutting. In this problem, there is a resource called a "cake", and several agents with different value measures on the cake. The goal is to divide the cake among the agents such that each agent will consider his/her piece as "fair" by his/her personal value measure. Since the agents' valuations can be very complex, they cannot - in general - be given as inputs to a fair division algorithm. The RW model specifies two kinds of queries that a fair division algorithm may ask the agents: Eval and Cut. Informally, an Eval query asks an agent to specify his/her value to a given piece of the cake, and a Cut query asks an agent to specify a piece of cake with a given value.
Alan Louis Selman was a mathematician and theoretical computer scientist known for his research on structural complexity theory, the study of computational complexity in terms of the relation between complexity classes rather than individual algorithmic problems.
María Luisa Bonet Carbonell is a Spanish computer scientist interested in logic in computer science, including proof complexity and algorithms for the maximum satisfiability problem. She is a professor of computer science at the Polytechnic University of Catalonia.
| International | |
|---|---|
| National | |
| Academics | |
| Other | |
