1 citations · 1 across the 5 of their papers we have counts for
7 papers
Private Proofs of When and Where
Uma Girish, Greg Gluch, Shafi Goldwasser +3
Position verification schemes are interactive protocols where entities prove their physical location to others; this enables interactive proofs for statements of the form "I am at…
Is nasty noise actually harder than malicious noise?
Guy Blanc, Yizhi Huang, Tal Malkin +1
We consider the relative abilities and limitations of computationally efficient algorithms for learning in the presence of noise, under two well-studied and challenging adversarial…
Provably Robust Watermarks for Open-Source Language Models
Miranda Christ, Sam Gunn, Tal Malkin +1
The recent explosion of high-quality language models has necessitated new methods for identifying AI-generated text. Watermarking is a leading solution and could prove to be an ess…
Lower Bounds for Oblivious Near-Neighbor Search
Kasper Green Larsen, Tal Malkin, Omri Weinstein +1
We prove an lower bound on the dynamic cell-probe complexity of statistically approximate-near-neighbor search () over…
Two Party Distribution Testing: Communication and Security
Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki
We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have samples from, re…
Non-Malleable Codes for Small-Depth Circuits
Marshall Ball, Dana Dachman-Soled, Siyao Guo +2
We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial si…
Strong Hardness of Privacy from Weak Traitor Tracing
Lucas Kowalczyk, Tal Malkin, Jonathan Ullman +1
Despite much study, the computational complexity of differential privacy remains poorly understood. In this paper we consider the computational complexity of accurately answering a…