@inproceedings{a43c0af1-a9fb-44ba-a457-e34ce8302775,
  abstract     = {{<p>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 time n<sup>Ω(log</sup> n<sup>)</sup> to PAC-learn monotone formulas with n input bits and size s(n) = n by monotone circuits of size n<sup>(log</sup> n<sup>)1−ϵ</sup>, for every ϵ &gt; 0. 2. Under the Randomised Exponential-Time Hypothesis (rETH), for any δ &gt; 0, there is a polynomially bounded function m such that m<sup>1−δ</sup>-multiplicatively approximating the minimum monotone circuit size of a monotone function consistent with a sequence of m(n) labelled examples {(xi, bi)} over n-bit inputs requires time m<sup>Ω(log(</sup>m<sup>))</sup>. Our results are shown by a novel application of lifting arguments in proof and communication complexity to hardness of monotone learning, by building on the seminal result of Atserias and Müller [6] on hardness of automating Resolution proofs.</p>}},
  author       = {{Cavalar, Bruno and de Rezende, Susanna F. and Gray, Matthew and Santhanam, Rahul}},
  booktitle    = {{41st Computational Complexity Conference, CCC 2026}},
  editor       = {{Moshkovitz, Dana}},
  isbn         = {{9783959774376}},
  issn         = {{1868-8969}},
  keywords     = {{hardness of approximation; lifting theorems; meta-complexity; minimum circuit size problem; monotone circuit complexity; PAC learning; Resolution}},
  language     = {{eng}},
  month        = {{07}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{Leibniz International Proceedings in Informatics, LIPIcs}},
  title        = {{ETH-Hardness of Learning Monotone Circuits and Approximating Their Size}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.CCC.2026.40}},
  doi          = {{10.4230/LIPIcs.CCC.2026.40}},
  volume       = {{383}},
  year         = {{2026}},
}