[logic-ml] Talk by Thomas Seiller (October 3rd, 11.00-)

[Kazushige TERUI]

みなさま

今週木曜日に京都大学にてThomas Seillerさんによるご講演があります。
詳細は下記の通りです。よろしければぜひご参加ください。

京都大学数理解析研究所
照井一成

==========
Time:    11:00-12:00, October 3rd, 2019
Place:    Rm 478, Research Building 2, Main Campus, Kyoto University
    京都大学 本部構内 総合研究2号館 4階478号室
    http://www.kyoto-u.ac.jp/en/access/yoshida/main.html (Building 34)



Speaker: Thomas Seiller (LIPN, University of Paris 13)

Title: Dynamical systems and computational complexity

Abstract:
Based on previous work on semantics of linear logic which used the notion
of “graphing”, I started to study how these mathematical objects, which
generalize partial dynamical systems, can shed new light on computability.

Focussing on questions of complexity, Pellissier and I recently showed how
interpreting programs as dynamical systems can lead to an abstract method
for proving lower bounds that capture several previously known results.
More importantly, the method can be refined to strengthen the previously
best-known partial result towards settling the Ptime vs NC question
negatively.

Building on some realisability construction for linear logic capturing
standard complexity classes, this leads to wonder about how much can be
learned from dynamical systems, and if the field can provide new insights
on important questions such that “Is Ptime equal to Logspace?”.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.fos.kuis.kyoto-u.ac.jp/pipermail/logic-ml/attachments/20191001/abec4185/attachment.html>