BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Marius ZIMAND (Towson University)
DTSTART:20250326T160000Z
DTEND:20250326T171500Z
DTSTAMP:20260423T040002Z
UID:AAIT/46
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/AAIT/46/">On
  the existence of one-way functions and the hardness of approximating Kolm
 ogorov complexity.</a>\nby Marius ZIMAND (Towson University) as part of Se
 minar on Algorithmic Aspects of Information Theory\n\n\nAbstract\nOne-way 
 functions are functions that are easy to compute and hard to invert. They 
 yield private-key encryption\, zero-knowledge proofs\, digital signatures\
 , commitment schemes\, and other applications in cryptography. They are wi
 dely believed to exist but an unconditional proof of this fact implies P \
 \not= NP. I will present a recent characterization due to Ilango\, Ren\, a
 nd Santhanam: there exists a one-way function IFF approximating the Kolmog
 orov complexity is hard on average with respect to some efficiently sampla
 ble distribution.\n\nThe paper by Ilango\, Ren\, and Santhana is available
  in Proc. STOC 2022\, https://dl.acm.org/doi/10.1145/3519935.3520051\nSee 
 also by M. Zimand https://eccc.weizmann.ac.il/report/2024/201/\n
LOCATION:https://researchseminars.org/talk/AAIT/46/
END:VEVENT
END:VCALENDAR