3 papers
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.CC2026
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…
cs.CC2025
Lower Bounds for CSP Hierarchies Through Ideal Reduction
Jonas Conneryd, Yassine Ghannane, Shuo Pang
We present a generic way to obtain level lower bounds for (promise) CSP hierarchies from degree lower bounds for algebraic proof systems. More specifically, we show that pseudo-red…