Toniann Pitassi is a Canadian and American

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

and

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

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 relating these classes to each other. A computational problem is a task solved by ...

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

Columbia University Columbia University (also known as Columbia, and officially as Columbia University in the City of New York) is a private research university in New York City. Established in 1754 as King's College on the grounds of Trinity Church in Manhatt ...

and was Bell Research Chair at the

University of Toronto The University of Toronto (UToronto or U of T) is a public research university in Toronto, Ontario, Canada, located on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution ...

Academic career

A native of

Pittsburgh Pittsburgh ( ) is a city in the Commonwealth (U.S. state), Commonwealth of Pennsylvania, United States, and the county seat of Allegheny County, Pennsylvania, Allegheny County. It is the most populous city in both Allegheny County and Wester ...

, 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 Pennsylvan ...

before moving to the

for her doctoral studies; she earned her Ph.D. 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 at the Unive ...

. After postdoctoral studies at the

University of California, San Diego The University of California, San Diego (UC San Diego or colloquially, UCSD) is a public university, public Land-grant university, land-grant research university in San Diego, California. Established in 1960 near the pre-existing Scripps Insti ...

and faculty positions at the

University of Pittsburgh The University of Pittsburgh (Pitt) is a public state-related research university in Pittsburgh, Pennsylvania. The university is composed of 17 undergraduate and graduate schools and colleges at its urban Pittsburgh campus, home to the universit ...

and

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

, 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 The University of Toronto Department of Mathematics is an academic department within the Faculty of Arts and Science at the University of Toronto. It is located at the university's main campus at the Bahen Centre for Information Technology. The ...

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 Nevanlinna Prize (to be rename ...

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), located in Princeton, New Jersey, in the United States, is an independent center for theoretical research and intellectual inquiry. It has served as the academic home of internationally preeminent scholar ...

Research

Pitassi's research has largely focused on proof complexity, 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 greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an element ...

on the lengths of

mathematical proof A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proo ...

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 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 performed by ...

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, if one has three gloves (and none is ambidextrous/reversible), then there mu ...

, 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 t ...

applied to propositions derived from the

maximum clique problem In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cli ...

, exponential lower bounds for

resolution Resolution(s) may refer to: Common meanings * Resolution (debate), the statement which is debated in policy debate * Resolution (law), a written motion adopted by a deliberative body * New Year's resolution, a commitment that an individual mak ...

proofs of dense random 3-satisfiability instances, and subexponential upper bounds for the same dense random instances using the

Davis–Putnam algorithm The Davis–Putnam algorithm was developed by Martin Davis and Hilary Putnam for checking the validity of a first-order logic formula using a resolution-based decision procedure for propositional logic. Since the set of valid first-order formulas ...

. With Paul Beame, she also wrote a survey of proof complexity.

Recognition

Pitassi was elected as an

ACM Fellow ACM or A.C.M. may refer to: Aviation * AGM-129 ACM, 1990–2012 USAF cruise missile * Air chief marshal * Air combat manoeuvring or dogfighting * Air cycle machine * Arica Airport (Colombia) (IATA: ACM), in Arica, Amazonas, Colombia Computing ...

in 2018 for "contributions to research and education in the fields of computational and proof complexity". Pitassi was also the recipient of the

EATCS The European Association for Theoretical Computer Science (EATCS) is an international organization with a European focus, founded in 1972. Its aim is to facilitate the exchange of ideas and results among theoretical computer scientists as well as ...

(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, 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 Nati ...

in 2022.

Selected publications

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

References

{{DEFAULTSORT:Pitassi, Toniann Living people Canadian women mathematicians Canadian women computer scientists Canadian computer scientists University of Toronto alumni Pennsylvania State University faculty University of Pittsburgh faculty University of Arizona faculty University of Toronto faculty Theoretical computer scientists Fellows of the Association for Computing Machinery Year of birth missing (living people) Columbia University faculty