3 papers
cs.CC2026
ETH-Hardness of Learning Monotone Circuits and Approximating Their Size
Bruno Cavalar, Susanna F. de Rezende, Matthew Gray +1
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 tim…
cs.CC2026
Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
Susanna F. de Rezende, David Engström, Yassine Ghannane +2
We study the average-case hardness of establishing that a graph does not have a large clique in both proof and communication complexity. We show exponential lower bounds on the len…
cs.CC2024
Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
Susanna F. de Rezende, Aaron Potechin, Kilian Risse
We prove that Sherali-Adams with polynomially bounded coefficients requires proofs of size to rule out the existence of an -clique in Erdős-Rényi random graphs…