Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

ETH-Hardness of Learning Monotone Circuits and Approximating Their Size

Cavalar, Bruno ; de Rezende, Susanna F. LU orcid ; Gray, Matthew and Santhanam, Rahul (2026) 41st Computational Complexity Conference, CCC 2026 In Leibniz International Proceedings in Informatics, LIPIcs 383.
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 m1−δ-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Ω(log(m)). Our results are... (More)

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 m1−δ-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Ω(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 [6] on hardness of automating Resolution proofs.

(Less)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
hardness of approximation, lifting theorems, meta-complexity, minimum circuit size problem, monotone circuit complexity, PAC learning, Resolution
host publication
41st Computational Complexity Conference, CCC 2026
series title
Leibniz International Proceedings in Informatics, LIPIcs
editor
Moshkovitz, Dana
volume
383
article number
40
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
41st Computational Complexity Conference, CCC 2026
conference location
Lisbon, Portugal
conference dates
2026-08-03 - 2026-08-06
external identifiers
  • scopus:105047065719
ISSN
1868-8969
ISBN
9783959774376
DOI
10.4230/LIPIcs.CCC.2026.40
language
English
LU publication?
yes
id
a43c0af1-a9fb-44ba-a457-e34ce8302775
date added to LUP
2026-08-31 14:03:15
date last changed
2026-08-31 14:03:59
@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}},
}