105 KAM Mathematical Colloquium

Abstract

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? What if we are assured that the program is small without being given explicitly?

In this talk I will explore recent work on the complexity of search problems with guaranteed solution (the class TFNP) and the tight relationship with cryptographic assumptions and techniques.

Based on joint works with Pavel Hubacek, Ilan Komargodski and Eylon Yogev.

O přednášejícím

Profesor Moni Naor studoval informatiku na izraelskem institutu technologie Technion v Hife a doktorat ziskal na Kalifornske univerzite v Berkeley. Od roku 1993 pracuje ve Weizmannove institutu v Izraeli. Jako hostujici profesor pusobil take na univerzitach ve Stanfordu a Princetonu a opakovane rovnez v IBM laboratori (Almaden). Venuje se ruznym odvetvim teoreticke informatiky a je povazovan za jednoho z prednich odborniku v oblasti kryptografie, ve ktere proslul rozvojem rigorozniho pristupu k reseni praktickych problemu. Jeho clanky predstavily napriklad non-malleable kryptosystemy nebo take metody pro overeni, zda je uzivatel opravdu clovek, jez inspirovaly pozdejsi prace na CAPTCHA. Za sve vysledky v teoreticke informatice a kryptografii ziskal radu oceneni. V roce 2008 byl jmenovan cestnym clenem mezinarodni asociace pro vyzkum v kryptografii (IACR). V roce 2014 mu EATCS a ACM SIGACT udelili Godelovu cenu a v roce 2016 obdrzel ACM cenu Parise Kanellakise. Prazska prednaska je venovana jedne z oblasti jeho zajmu.