DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.40

ETH-Hardness of Learning Monotone Circuits and Approximating Their Size

Authors: Bruno Cavalar, Susanna F. de Rezende, Matthew Gray, and Rahul Santhanam

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

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^{Ω(log n)} to PAC-learn monotone formulas with n input bits and size s(n) = n by monotone circuits of size n^{(log n)^{1-ε}}, for every ε > 0. 2) Under the Randomised Exponential-Time Hypothesis (rETH), for any δ > 0, there is a polynomially bounded function m such that m^{1-δ}-multiplicatively approximating the minimum monotone circuit size of a monotone function consistent with a sequence of m(n) labelled examples {(x_i, b_i)} over n-bit inputs requires time m^{Ω(log(m))}. 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 [Atserias and Müller, 2020] on hardness of automating Resolution proofs.

Cite as

Bruno Cavalar, Susanna F. de Rezende, Matthew Gray, and Rahul Santhanam. ETH-Hardness of Learning Monotone Circuits and Approximating Their Size. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 40:1-40:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cavalar_et_al:LIPIcs.CCC.2026.40,
  author =	{Cavalar, Bruno and de Rezende, Susanna F. and Gray, Matthew and Santhanam, Rahul},
  title =	{{ETH-Hardness of Learning Monotone Circuits and Approximating Their Size}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{40:1--40:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.40},
  URN =		{urn:nbn:de:0030-drops-270826},
  doi =		{10.4230/LIPIcs.CCC.2026.40},
  annote =	{Keywords: monotone circuit complexity, PAC learning, lifting theorems, Resolution, meta-complexity, hardness of approximation, minimum circuit size problem}
}

Search Results

Documents authored by Cavalar, Bruno

ETH-Hardness of Learning Monotone Circuits and Approximating Their Size

Abstract

Cite as

Thanks for your feedback!

Could not send message