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.
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.