STOC2023

When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems

Lijie Chen, Roei Tell

被引用 10 次

摘要

What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of derandomizing interactive proofs systems.