4 papers
ETH-Hardness of Learning Monotone Circuits and Approximating Their Size
Bruno Cavalar, Susanna F. de Rezende, Matthew Gray +1
The paper proves that, assuming the Randomised Exponential-Time Hypothesis, both PAC-learning monotone formulas and multiplicatively approximating the minimum monotone circuit size…
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 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…
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…