complexity theory 1hardness of approximation 1learning theory 1monotone circuits 1proof complexity 1
From the 1 of 2 linked papers with an AI index.
2 papers
cs.CC2026
ETH-Hardness of Learning Monotone Circuits and Approximating Their Size
Bruno Cavalar, Susanna F. de Rezende, Matthew Gray +1
The paper proves that, assuming the Randomised Exponential-Time Hypothesis, both PAC-learning monotone formulas and multiplicatively approximating the minimum monotone circuit size…
cs.CC2025
Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen, Zhenjian Lu, Igor C. Oliveira +2
A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on…