5 citations · 8 across the 5 of their papers we have counts for
6 papers
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…
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…