4 citations · 4 across the 5 of their papers we have counts for
6 papers · 1 filter
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…
Negations are powerful even in small depth
Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay +2
We study the power of negation in the Boolean and algebraic settings and show the following results. * We construct a family of polynomials in variables, all of whose mon…
Monotone Circuit Complexity of Matching
Bruno Cavalar, Mika Göös, Artur Riazanov +2
We show that the perfect matching function on -vertex graphs requires monotone circuits of size . This improves on the lower bound of Razbo…
Boolean Circuit Complexity and Two-Dimensional Cover Problems
Bruno P. Cavalar, Igor C. Oliveira
We reduce the problem of proving deterministic and nondeterministic Boolean circuit size lower bounds to the analysis of certain two-dimensional combinatorial cover problems. This…
Constant-depth circuits vs. monotone circuits
Bruno P. Cavalar, Igor C. Oliveira
We establish new separations between the power of monotone and general (non-monotone) Boolean circuits: - For every , there is a monotone function in that re…
Monotone Circuit Lower Bounds from Robust Sunflowers
Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman
Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent adva…