Toniann Pitassi | |
---|---|
![]() Pitassi at the MFO workshop Proof Complexity and Beyond, 2017 | |
Nationality |
|
Education | |
Spouse | Richard Zemel |
Scientific career | |
Fields | Mathematics, computer science |
Institutions |
|
Doctoral advisor | Stephen Cook |
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. [1] [2]
A native of Pittsburgh, Pitassi earned bachelor's and master's degrees at Pennsylvania State University before moving to the University of Toronto for her doctoral studies; she earned her PhD in 1992 from Toronto under the supervision of Stephen Cook. After postdoctoral studies at the University of California, San Diego and faculty positions at the University of Pittsburgh and University of Arizona, she returned to Toronto in 2001, and was a professor in the University of Toronto Department of Computer Science and University of Toronto Department of Mathematics until 2021, when she joined the faculty of Columbia University. [3] [4]
She was an invited speaker at International Congress of Mathematicians in Berlin in 1998. [5] [6] She was the program chair for the 2012 Symposium on Theory of Computing. [7] From September through December 2017, she was a visiting professor at the Institute for Advanced Study. [8]
Pitassi's research has largely focused on proof complexity, a branch of computational complexity theory that seeks upper and lower bounds on the lengths of mathematical proofs of logical propositions within various formalized proof systems. The goal of this study is to use these bounds to understand both the time complexity of proof-finding procedures, and the relative strengths of different proof systems.
Research contributions that she has made in this area include exponential lower bounds for Frege proofs of the pigeonhole principle, [9] exponential lower bounds for the cutting-plane method applied to propositions derived from the maximum clique problem, [10] exponential lower bounds for resolution proofs of dense random 3-satisfiability instances, [11] and subexponential upper bounds for the same dense random instances using the Davis–Putnam algorithm. [12] With Paul Beame, she also wrote a survey of proof complexity. [13]
Pitassi was elected as an ACM Fellow in 2018 for "contributions to research and education in the fields of computational and proof complexity". [14]
Pitassi was also the recipient of the EATCS (European Association for Theoretical Computer Science) Award in 2021 for her "fundamental and wide-ranging contributions to computational complexity". [15]
She was named to the National Academy of Sciences in 2022. [2] [16]
Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.
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.
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 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.
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.
Michael Fredric Sipser is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the dean of science at the Massachusetts Institute of Technology.
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 theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits .
ACC0, sometimes called ACC, is a class of computational models and problems defined in circuit complexity, a field of theoretical computer science. The class is defined by augmenting the class AC0 of constant-depth "alternating circuits" with the ability to count; the acronym ACC stands for "AC with counters". Specifically, a problem belongs to ACC0 if it can be solved by polynomial-size, constant-depth circuits of unbounded fan-in gates, including gates that count modulo a fixed integer. ACC0 corresponds to computation in any solvable monoid. The class is very well studied in theoretical computer science because of the algebraic connections and because it is one of the largest concrete computational models for which computational impossibility results, so-called circuit lower bounds, can be proved.
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.
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.
Lance Jeremy Fortnow is a computer scientist known for major results in computational complexity and interactive proof systems. He is the Dean of the College of Computing at the Illinois Institute of Technology.
Richard Ryan Williams, known as Ryan Williams, is an American theoretical computer scientist working in computational complexity theory and algorithms.
In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis. Informally, it states that all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms.
Ronald Michiel de Wolf is a Dutch Computer Scientist, currently a Senior Researcher at Centrum Wiskunde & Informatica (CWI) and a professor at the Institute for Logic, Language and Computation (ILLC) of the University of Amsterdam (UvA).
Virginia Vassilevska Williams is a theoretical computer scientist and mathematician known for her research in computational complexity theory and algorithms. She is currently the Steven and Renee Finn Career Development Associate Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. She is notable for her breakthrough results in fast matrix multiplication, for her work on dynamic algorithms, and for helping to develop the field of fine-grained complexity.
In theoretical computer science, the log-rank conjecture states that the deterministic communication complexity of a two-party Boolean function is polynomially related to the logarithm of the rank of its input matrix.
Jeff Edmonds is a Canadian and American mathematician and computer scientist specializing in computational complexity theory.
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.