5 citations · 9 across the 7 of their papers we have counts for
10 papers
Improved Quantum Random Self-Reduction for Linear Problems
Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu
We study quantum random self-reductions for linear problems over finite fields. Let be an arbitrary matrix, and let be an oracle that agr…
Multi-Prover Interactive Proof Systems with Leakage
Vahid R. Asadi, Atsuya Hasegawa, François Le Gall
It is known that there exist multi-prover interactive protocols ( protocols) for the complexity class , succinct protocols for $\mathsf{…
Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
Vahid R. Asadi, Richard Cleve
The Tree Evaluation Problem () is a computational problem originally proposed as a candidate to prove a separation between complexity classes and $\…
Conditional disclosure of secrets with quantum resources
Vahid R. Asadi, Kohdai Kuroiwa, Debbie Leung +3
The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and securit…
Linear gate bounds against natural functions for position-verification
Vahid Asadi, Richard Cleve, Eric Culf +1
A quantum position-verification scheme attempts to verify the spatial location of a prover. The prover is issued a challenge with quantum and classical inputs and must respond with…
Rank lower bounds on non-local quantum computation
Vahid R. Asadi, Eric Culf, Alex May
A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two c…
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
Vahid R. Asadi, Alexander Golovnev, Tom Gur +2
We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quan…
Worst-Case to Average-Case Reductions via Additive Combinatorics
Vahid R. Asadi, Alexander Golovnev, Tom Gur +1
We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time…
Private Boosted Decision Trees via Smooth Re-Weighting
Vahid R. Asadi, Marco L. Carmosino, Mohammadmahdi Jahanara +2
Protecting the privacy of people whose data is used by machine learning algorithms is important. Differential Privacy is the appropriate mathematical framework for formal guarantee…
Relaxed Locally Correctable Codes with Improved Parameters
Vahid R. Asadi, Igor Shinkar
Locally decodable codes (LDCs) are error-correcting codes that admit a local decoding algorithm that recovers each individual bit of the message by querying only…