Toniann Pitassi is a Canadian-American mathematician and

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

specializing in

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

. She is currently Jeffrey L. and Brenda Bleustein Professor of Engineering at

Columbia University Columbia University in the City of New York, commonly referred to as Columbia University, is a Private university, private Ivy League research university in New York City. Established in 1754 as King's College on the grounds of Trinity Churc ...

and was Bell Research Chair at the

University of Toronto The University of Toronto (UToronto or U of T) is a public university, public research university whose main campus is located on the grounds that surround Queen's Park (Toronto), Queen's Park in Toronto, Ontario, Canada. It was founded by ...

Academic career

A native of

Pittsburgh Pittsburgh ( ) is a city in Allegheny County, Pennsylvania, United States, and its county seat. It is the List of municipalities in Pennsylvania#Municipalities, second-most populous city in Pennsylvania (after Philadelphia) and the List of Un ...

, Pitassi earned bachelor's and master's degrees at

Pennsylvania State University The Pennsylvania State University (Penn State or PSU) is a Public university, public Commonwealth System of Higher Education, state-related Land-grant university, land-grant research university with campuses and facilities throughout Pennsyl ...

before moving to the

for her doctoral studies; she earned her PhD in 1992 from Toronto under the supervision of

Stephen Cook Stephen Arthur Cook (born December 14, 1939) 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 ...

. After postdoctoral studies at the

University of California, San Diego The University of California, San Diego (UC San Diego in communications material, formerly and colloquially UCSD) is a public university, public Land-grant university, land-grant research university in San Diego, California, United States. Es ...

and faculty positions at the

University of Pittsburgh The University of Pittsburgh (Pitt) is a Commonwealth System of Higher Education, state-related research university in Pittsburgh, Pennsylvania, United States. The university is composed of seventeen undergraduate and graduate schools and colle ...

and

University of Arizona The University of Arizona (Arizona, U of A, UArizona, or UA) is a Public university, public Land-grant university, land-grant research university in Tucson, Arizona, United States. Founded in 1885 by the 13th Arizona Territorial Legislature, it ...

, 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

. She was an invited speaker at

International Congress of Mathematicians The International Congress of Mathematicians (ICM) is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union (IMU). The Fields Medals, the IMU Abacus Medal (known before ...

in Berlin in 1998. She was the program chair for the 2012

Symposium on Theory of Computing 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 ...

. From September through December 2017, she was a visiting professor at the

Institute for Advanced Study The Institute for Advanced Study (IAS) is an independent center for theoretical research and intellectual inquiry located in Princeton, New Jersey. It has served as the academic home of internationally preeminent scholars, including Albert Ein ...

Research

Pitassi's research has largely focused on

proof complexity 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. ...

, a branch of

that seeks

upper and lower bounds In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less th ...

on the lengths of

mathematical proof A mathematical proof is a deductive reasoning, deductive Argument-deduction-proof distinctions, argument for a Proposition, mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use othe ...

s of logical propositions within various formalized proof systems. The goal of this study is to use these bounds to understand both the

time complexity In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...

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 In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, of three gloves, at least two must be right-handed or at least two must be l ...

, exponential lower bounds for the

cutting-plane method In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed ''cuts''. Such procedures are commonly used ...

applied to propositions derived from the maximum clique problem, exponential lower bounds for resolution proofs of dense random 3-satisfiability instances, and subexponential upper bounds for the same dense random instances using the Davis–Putnam algorithm. With various coauthors, she has several expositions and surveys: on proof complexity in general, on algebraic proof complexity, and on semialgebraic proof complexity.

Recognition

Pitassi was elected as an

ACM Fellow ACM Fellowship is an award and fellowship that recognises outstanding members of the Association for Computing Machinery (ACM). The title of ACM Fellow A fellow is a title and form of address for distinguished, learned, or skilled individuals ...

in 2018 for "contributions to research and education in the fields of computational and proof complexity". 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". She was named to the

National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, NGO, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the ...

in 2022.

Selected publications

*. *. *. *. Reprinted in ''Current Trends in Theoretical Computer Science'', World Scientific, 2001, . *. *. * * *

References

{{DEFAULTSORT:Pitassi, Toniann Living people 21st-century Canadian women mathematicians Canadian women computer scientists University of Toronto alumni Pennsylvania State University faculty University of Pittsburgh faculty University of Arizona faculty Academic staff of the University of Toronto American theoretical computer scientists Canadian theoretical computer scientists 2018 fellows of the Association for Computing Machinery Year of birth missing (living people) Columbia University faculty