Innovations in Theoretical Computer Science 2020 Session 10 (1) скачать в хорошем качестве

Innovations in Theoretical Computer Science 2020 Session 10 (1)

The ITCS conference seeks to promote research that carries a strong conceptual message, for example, introducing a new concept or model, opening a new line of inquiry within traditional or interdisciplinary areas, or introducing new techniques or new applications of known techniques. Session 10 Chair: Anna Gal Computational Hardness of Certifying Bounds on Constrained PCA Problems by Afonso S. Bandeira; Dmitriy Kunisky; Alexander S. Wein. Unexpected Power of Random Strings by Shuichi Hirahara. Beyond Natural Proofs: Hardness Magnification and Locality by Lijie Chen; Shuichi Hirahara; Igor Oliveira; Jan Pich; Ninad Rajgopal; Rahul Santhanam. Hardness Amplification of Optimization Problems by Elazar Goldenberg; Karthik C. S.. Pseudorandomness and the Minimum Circuit Size Problem by Rahul Santhanam. Top-down induction of decision trees: rigorous guarantees and inherent limitations by Guy Blanc; Jane Lange; Li-Yang Tan. More information is available at http://itcs-conf.org. These lectures were recorded on 1/14/20 and are closed captioned