BCBruno Cavalar

Bruno Cavalar

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Bruno Cavalar has a total of 9 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Negations are powerful even in small depth

    by Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff

    We study the power of negation in the Boolean and algebraic settings and show the following results. * We construct a family of polynomials $P_n$ in $n$ variables, all of whose monomials have positive coefficients, such that $P_n$ can be computed by a depth three circuit of polynomial size but any monotone circuit computing it has size $2^{Ω(n)}$. This is the strongest possible separation result between monotone and non-monotone arithmetic computations and improves upon all earlier results, including the seminal work of Valiant (1980) and more recently by Chattopadhyay, Datta, and Mukhopadhyay (2021). We then boot-strap this result to prove strong monotone separations for polynomials of constant degree, which solves an open problem from the survey of Shpilka and Yehudayoff (2010). * By moving to the Boolean setting, we can prove superpolynomial monotone Boolean circuit lower bounds for specific Boolean functions, which imply that all the powers of certain monotone polynomials cannot be computed by polynomially sized monotone arithmetic circuits. * We then define a collection of problems with linear-algebraic nature, which are similar to span programs, and prove monotone Boolean circuit lower bounds for them. In particular, this gives the strongest known monotone lower bounds for functions in uniform (non-monotone) $\textbf{NC}^2$. Our construction also leads to an explicit matroid that defines a monotone function that is difficult to compute, which solves an open problem by Jukna and Seiwert (2020). Our monotone arithmetic and Boolean circuit lower bounds are based on known techniques, such as reduction from monotone arithmetic complexity to multipartition communication complexity and the approximation method for proving lower bounds for monotone Boolean circuits, but we overcome several new challenges in order to obtain efficient upper bounds using low-depth circuits.

  • Open Access

    On the Computational Hardness of Quantum One-Wayness

    by Bruno Cavalar, Eli Goldin, Matthew Gray, Peter Hall, Yanyi Liu, Angelos Pelecanos

    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 generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that P≠NP, which gives a lower bound on the necessary hardness.One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory.We show that pseudorandom states compressing n bits to log⁡n+1 qubits can be used to build one-way state generators and pseudorandom states compressing n bits to ω(log⁡n) qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than clog⁡n-qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a PP oracle.An interesting implication of our results is that a t(n)-copy one-way state generator exists unconditionally, for every t(n)=o(n/log⁡n). This contrasts nicely with the previously known fact that O(n)-copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments.


  • Open Access

    A Meta-Complexity Characterization of Quantum Cryptography

    by Bruno P. Cavalar, Eli Goldin, Matthew Gray, Peter Hall

    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 distribution of binary strings over which it is hard to approximate Kolmogorov complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a uncomputable problem. This brings to the quantum setting a recent line of work that characterizes classical cryptography with the average-case hardness of a meta-complexity problem, initiated by Liu and Pass. Moreover, since the average-case hardness of Kolmogorov complexity over classically polynomial-time samplable distributions characterizes one-way functions, this result poses one-way puzzles as a natural generalization of one-way functions to the quantum setting. Furthermore, our equivalence goes through probability estimation, giving us the additional equivalence that one-way puzzles exist if and only if there is a quantum samplable distribution over which probability estimation is hard. We also observe that the oracle worlds of defined by Kretschmer et. al. rule out any relativizing characterization of one-way puzzles by the hardness of a problem in NP or QMA, which means that it may not be possible with current techniques to characterize one-way puzzles with another meta-complexity problem.