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…