In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object with certain properties by creating or providing a method for creating such an object. This is in contrast to a non-constructive proof (also known as an existence proof or pure existence theorem) which proves the validity of a proposition without considering an example.

Some non-constructive proofs show that if a certain proposition is false, a contradiction ensues; consequently the proposition must be true (proof by contradiction). Nearly every proof which explicitly relies on the axiom of choice is non-constructive in nature because this axiom is fundamentally non-constructive. The same can be said for proofs invoking König's lemma^{[citation needed]}.

Constructivism is the philosophy that rejects all but constructive proofs in mathematics. Typically, supporters of this view deny that pure existence can be usefully characterized as "existence" at all: accordingly, a non-constructive proof is instead seen as "refuting the impossibility" of a mathematical object's existence, a strictly weaker statement.

Mario Szegedy (born October 23, 1960) is a Hungarian computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago. He held a Lady Davis Fellowship (Postdoctoral) at the Hebrew University, Jerusalem (1989-90), a postdoc at the University of Chicago, 1991-92, and a postdoc at Bell Laboratories (1992).

Szegedy's research areas include computational complexity theory and quantum computing.

He was awarded the Gödel Prize twice, in 2001 and 2005, for his work on probabilistically checkable proofs and on the space complexity of approximating the frequency moments in streamed data.