From the 1 of 4 linked papers with an AI index.
4 papers
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…
The Proof Analysis Problem
Noel Arteche, Albert Atserias, Susanna F. de Rezende +1
Atserias and Müller (JACM, 2020) proved that for every unsatisfiable CNF formula , the formula , stating " has small Resolution refutations", does…
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…
Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
Susanna F. de Rezende, David Engström, Yassine Ghannane +1
We prove superpolynomial length lower bounds for the semantic tree-like Frege refutation system with bounded line size. Concretely, for any function $n^{2-\varepsilon} \leq s(n) \l…