Abstract

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.