7 citations · 19 across the 18 of their papers we have counts for
6 papers · 1 filter
The Entire Quantum Computer on a Classical Leash
Yael Tauman Kalai, Dakshita Khurana, Justin Raizes
We show that a classical client with no quantum hardware can use a single untrusted and potentially malicious quantum server as if it were its own trusted quantum computer. Through…
Tight Post-Quantum Parallel Repetition for Private-Coin Arguments
Zvika Brakerski, Andrew Huang, Yael Tauman Kalai +1
We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness…
Semi-Quantum Cryptography with Certified Deletion
Yael Tauman Kalai, Justin Raizes
Certified deletion allows a client to upload encrypted data to a server as a quantum state, then later request that the server delete their data and detect whether the server compl…
How to Avoid Debate: Scalable AI Safety via Doubly-Efficient Interactive Proofs
Liyan Chen, Yael Tauman Kalai, Zoe Xi
As AI models continue to develop powerful capabilities, it becomes critical that we are able to verify that their output is aligned with our intentions. A recent line of work focus…
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…
How to Classically Verify a Quantum Cat without Killing It
Yael Tauman Kalai, Dakshita Khurana, Justin Raizes
A quantum verifier decides membership in QMA using a (single) quantum witness state. This witness may be arbitrary, and no requirement is placed on it beyond its acceptance probabi…