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}
}

Document

DOI: 10.4230/LIPIcs.CCC.2024.15

Quantum Automating TC⁰-Frege Is LWE-Hard

Authors: Noel Arteche, Gaia Carenini, and Matthew Gray

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract

We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate TC⁰-Frege. This extends the line of results of Krajíček and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and Raz (FOCS, 1997), and Bonet, Domingo, Gavaldà, Maciel, and Pitassi (Computational Complexity, 2004), who showed that Extended Frege, TC⁰-Frege and AC⁰-Frege, respectively, cannot be weakly automated by classical algorithms if either the RSA cryptosystem or the Diffie-Hellman key exchange protocol are secure. To the best of our knowledge, this is the first interaction between quantum computation and propositional proof search.

Cite as

Noel Arteche, Gaia Carenini, and Matthew Gray. Quantum Automating TC⁰-Frege Is LWE-Hard. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 15:1-15:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arteche_et_al:LIPIcs.CCC.2024.15,
  author =	{Arteche, Noel and Carenini, Gaia and Gray, Matthew},
  title =	{{Quantum Automating TC⁰-Frege Is LWE-Hard}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{15:1--15:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.15},
  URN =		{urn:nbn:de:0030-drops-204117},
  doi =		{10.4230/LIPIcs.CCC.2024.15},
  annote =	{Keywords: automatability, post-quantum cryptography, feasible interpolation}
}

Search Results

Documents authored by Gray, Matthew

ETH-Hardness of Learning Monotone Circuits and Approximating Their Size

Abstract

Cite as

Quantum Automating TC⁰-Frege Is LWE-Hard

Abstract

Cite as

Thanks for your feedback!

Could not send message