7 citations · 19 across the 18 of their papers we have counts for
4 papers · 1 filter
Towards a Doubly Efficient IP=PSPACE
Liyan Chen, Matthew M. Hong, Yael Tauman Kalai +1
We show that every language in PSPACE decidable by a Turing machine in time admits a doubly efficient interactive proof system: the prover runs in time polynom…
Efficiently Batching Unambiguous Interactive Proofs
Bonnie Berger, Rohan Goyal, Matthew M. Hong +1
We show that if a language admits a public-coin unambiguous interactive proof (UIP) with round complexity , where bits are communicated per round, then the batch lang…
On the works of Avi Wigderson
Boaz Barak, Yael Kalai, Ran Raz +2
This is an overview of some of the works of Avi Wigderson, 2021 Abel prize laureate. Wigderson's contributions span many fields of computer science and mathematics. In this survey…
Non-Signaling Proofs with Provers are in PSPACE
Dhiraj Holden, Yael Kalai
Non-signaling proofs, motivated by quantum computation, have found applications in cryptography and hardness of approximation. An important open problem is characterizing the power…