7 citations · 19 across the 18 of their papers we have counts for
20 papers
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…
Consensus Sampling for Safer Generative AI
Adam Tauman Kalai, Yael Tauman Kalai, Or Zamir
Motivated by undetectable risks in generative AI, we study a general robust aggregation problem: how to aggregate several probability distributions to boost safety. We present cons…
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…
Compiling Any into a (Succinct) Classical Interactive Argument
Andrew Huang, Yael Tauman Kalai
We present a generic compiler that converts any protocol into a succinct interactive argument where the communication and the verifier are classical, and where p…
Parallel Repetition for Post-Quantum Arguments
Andrew Huang, Yael Tauman Kalai
In this work, we show that parallel repetition of public-coin interactive arguments reduces the soundness error at an exponential rate even in the post-quantum setting. Moreover, w…
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…
Succinct Classical Verification of Quantum Computation
James Bartusek, Yael Tauman Kalai, Alex Lombardi +5
We construct a classically verifiable succinct interactive argument for quantum computation (BQP) with communication complexity and verifier runtime that are poly-logarithmic in th…
Quantum Advantage from Any Non-Local Game
Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan +1
We show a general method of compiling any -prover non-local game into a single-prover interactive game maintaining the same (quantum) completeness and (classical) soundness guar…
Constructive Post-Quantum Reductions
Nir Bitansky, Zvika Brakerski, Yael Tauman Kalai
Is it possible to convert classical cryptographic reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interac…
Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to Adversarial Corruption
Meghal Gupta, Yael Tauman Kalai, Rachel Zhang
An error correcting code () allows a sender to send a message to a receiver such that even if a constant fraction of the communicated bits are corrupted, the receiver…
Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples
Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai +1
We present a transductive learning algorithm that takes as input training examples from a distribution and arbitrary (unlabeled) test examples, possibly chosen by an adversary.…
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…
Efficient Multiparty Interactive Coding for Insertions, Deletions and Substitutions
Ran Gelles, Yael T. Kalai, Govind Ramnarayan
In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop…
Compressing Communication in Distributed Protocols
Yael Tauman Kalai, Ilan Komargodski
We show how to compress communication in selection protocols, where the goal is to agree on a sequence of random bits using only a broadcast channel. More specifically, we present…
Adaptively Secure Coin-Flipping, Revisited
Shafi Goldwasser, Yael Tauman Kalai, Sunoo Park
The full-information model was introduced by Ben-Or and Linial in 1985 to study collective coin-flipping: the problem of generating a common bounded-bias bit in a network of pl…
The impossibility of obfuscation with auxiliary input or a universal simulator
Nir Bitansky, Ran Canetti, Henry Cohn +4
In this paper we show that the existence of general indistinguishability obfuscators conjectured in a few recent works implies, somewhat counterintuitively, strong impossibility re…