Σας προσκαλούμε στη διάλεξη του κ. Γεώργιου Μπαρμπαλιά, Καθηγητή στη Κινεζική Ακαδημία Επιστημών, (http://www.barmpalias.net). Η διάλεξη θα πραγματοποιηθεί την Τρίτη 15 Ιουλίου 2024 & ώρα 11:00, στην Αίθουσα Σεμιμαρίων του Τομέα Μαθηματικών.

Title: Computable one-way functions on the reals

Abstract: A major open problem in computational complexity is the existence of a one-way function, namely a function from strings to strings which is computationally easy to compute but hard to invert. Levin (2023) formulated the notion of one-way functions from reals (infinite bit-sequences) to reals in terms of computability, and asked whether partial computable one-way functions exist. We give a strong positive answer using the hardness of the halting problem and exhibiting a total computable one-way function.

This is joint work with Xiaoyan Zhang.

Preprint: http://arxiv.org/abs/2406.15817=

Από την Επιτροπή Σεμιναρίων του Τομέα Μαθηματικών