4 citations · 4 across the 5 of their papers we have counts for
6 papers
ETH-Hardness of Learning Monotone Circuits and Approximating Their Size
Bruno Cavalar, Susanna F. de Rezende, Matthew Gray +1
We show the following hardness results for monotone learning and approximation of monotone circuit size: 1. Under the Randomised Exponential-Time Hypothesis (rETH), it requires tim…
A Meta-Complexity Characterization of Minimal Quantum Cryptography
Bruno Cavalar, Boyang Chen, Andrea Coladangelo +4
We give a meta-complexity characterization of EFI pairs, which are considered the "minimal" primitive in quantum cryptography (and are equivalent to quantum commitments). More prec…
Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
Bruno Cavalar, Eli Goldin, Matthew Gray +3
One of the most fundamental problems in distribution testing is the identity testing problem: given samples , the goal is to determine whether the samples are drawn…
A Meta-Complexity Characterization of Quantum Cryptography
Bruno P. Cavalar, Eli Goldin, Matthew Gray +1
We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribu…
On Central Primitives for Quantum Cryptography with Classical Communication
Kai-Min Chung, Eli Goldin, Matthew Gray
Recent work has introduced the "Quantum-Computation Classical-Communication" (QCCC) (Chung et. al.) setting for cryptography. There has been some evidence that One Way Puzzles (OWP…
On the Computational Hardness of Quantum One-Wayness
Bruno Cavalar, Eli Goldin, Matthew Gray +3
There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generato…