7 papers
New bounds on private simultaneous quantum message passing
Uma Girish, Alex May, Natalie Parham +1
In the private simultaneous message (PSM) setting, players obtain inputs and then each send messages to a referee, who should learn but no ot…
Fourier Spectrum of Noisy Quantum Algorithms
Uma Girish
Quantum computing promises exponential speedups for certain problems, yet fully universal quantum computers remain out of reach and near-term devices are inherently noisy. Motivate…
Comparing classical and quantum conditional disclosure of secrets
Uma Girish, Alex May, Leo Orshansky +1
The conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum…
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…
Trade-offs between Entanglement and Communication
Srinivasan Arunachalam, Uma Girish
We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we…
Magic and communication complexity
Uma Girish, Alex May, Natalie Parham +1
We establish novel connections between magic in quantum circuits and communication complexity. In particular, we show that functions computable with low magic have low communicatio…