## Authors: Luc Pellissier and Thomas Seiller

## Paper Information

Title: | Entropy and Complexity Lower Bounds |

Authors: | Luc Pellissier and Thomas Seiller |

Proceedings: | Linearity/TLLA Pre-proceedings |

Editors: | Maribel Fernandez, Valeria de Paiva, Thomas Ehrhard and Lorenzo Tortora De Falco |

Keywords: | Semantics, Complexity Theory, Dynamical Systems, Algebraic Geometry |

Abstract: | ABSTRACT. Finding lower bounds in complexity theory has proven to be an extremely difficult task. Nowadays, only one research direction is commonly acknowledged to have the ability to solve current open problems, namely Mulmuley's Geometric Complexity Theory programme. Relying on heavy techniques from algebraic geometry, it stemmed from a first lower bound result for a variant of Parallel Random Access Machines. We analyse this original proof, together with two other proofs of lower bounds from a semantics point of view, interpreting programs as graphings -- generalizations of dynamical systems. We show that, abstracted to a more general setting that exploits the classic notion of topological entropy, this three proofs share the same structure. This reformulation recentres the proofs around dynamical aspects, relegating the use of algebraic geometry to a model-driven choice rather than a key concept of the method. |

Pages: | 5 |

Talk: | Jul 08 09:55 (Session 34J) |

Paper: |