Скачать или смотреть Innovations in Theoretical Computer Science 2020 Session 4

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 4 Chair: Luca Trevisan

The Random-Query Model and the Memory-Bounded Coupon Collector by Ran Raz; Wei Zhan.

Resolution with Counting: Dag-Like Lower Bounds and Different Moduli by Fedor Part; Iddo Tzameret.

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria by Kousha Etessami; Christos Papadimitriou; Aviad Rubinstein; Mihalis
Yannakakis.

Computational pseudorandomness, Complexity=Volume, and constraints on the AdS/CFT duality by Adam Bouland; Bill Fefferman; Umesh V. Vazirani.

More information is available at http://itcs-conf.org. These lectures were recorded on 2/12/20 and are closed captioned.