セミナー：七島幹人（東京工業大学）（2021年7月20日)

開催日時：　2021年7月20日（火）13:00～
開催形態：　Zoom

タイトル：　学習困難性仮定，追加入力付き暗号プリミティヴ，メタ計算量

要　旨：本講演では，学習困難性（特に，回路のPAC学習困難性）と，計算複雑性理論・暗号理論との関係性を通して，PessilandやHeuristicaに関連する諸概念の整理を行う．特に，[Nanashima, COLT’20,’21]で得られた，追加入力付き暗号プリミティヴと学習困難性の等価性について紹介し，関連する話題として，[Carmosino et al. ,CCC’16]をはじめとする，学習困難性とメタ計算量理論との関係性についても簡単に紹介する．