The way of the empty proof

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

• Jean-Louis Lassez
• Friday 11 October 2019, 14:00-15:00
• FW26.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• FW26
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.