University of Cambridge > > Logic and Semantics Seminar (Computer Laboratory) > The way of the empty proof

The way of the empty proof

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Anuj Dawar.

There is a strong conceptual link between proofs and algorithms and their eventual simplicity. With the right data structures algorithms become simpler, sometimes much simpler. With the right definitions proofs become simpler to the point where they might vanish. But there is a dark side to simplicity. If you find a simple proof or a simple algorithm, it may be dismissed as being “simple”, even if it is new and interesting. The challenge is to find a simple proof or a simple algorithm that brings a solution to a hard problem. Examples are drawn from Automata Theory applied to Theater, word equations arising from Lie Algebras, coding theory as applied to the genetic code. And a striking example where a graphic visualization of Symbolic Gaussian elimination leads to a better understanding of Ershov’s theorem and Perron Frobenius’ theorem as most relevant to Google’s search engine. In Linear programming and Geometry we have major theorems and algorithms and open problems which can be viewed in much simpler ways using an old elimination algorithm due to Fourier, when we understand the link between Fourier elimination and Gaussian elimination, when inequalities are in fact implicit equalities.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity