Ομιλητής: Γιώργος Μπαρμπαλιάς (Κινέζικη Ακαδημία
Επιστημών)
Τίτλος: Computable one-way functions on the reals
Ημερομηνία: 16-7-2024
Αίθουσα: Αίθουσα Σεμιναρίων ΣΕΜΦΕ 2ος όροφος Κτίριο Ε -
Γενικές έδρες, Σχολή Εφαρμοσμένων Μαθηματικών και Φυσικών Επιστημών
Σύνοψη
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