:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	de Rezende, Susanna F., Engström, David, Ghannane, Yassine, Janett, Duri Andrea, Riazanov, Artur
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2605.10941
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
by: de Rezende, Susanna F., et al.
Published: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
by: de Rezende, Susanna F., et al.
Published: (2024)

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
by: de Rezende, Susanna F., et al.
Published: (2024)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
by: Riazanov, Artur, et al.
Published: (2025)

Better Boosting of Communication Oracles, or Not
by: Harms, Nathaniel, et al.
Published: (2024)

Equality is Far Weaker than Constant-Cost Communication
by: Göös, Mika, et al.
Published: (2025)

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

The Proof Analysis Problem
by: Arteche, Noel, et al.
Published: (2025)

Top-Down Lower Bounds for Depth-Four Circuits
by: Göös, Mika, et al.
Published: (2023)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
by: Fu, Cheng-Hao, et al.
Published: (2025)

Hard Clique Formulas for Resolution
by: Atserias, Albert
Published: (2026)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
by: Dalirrooyfard, Mina, et al.
Published: (2025)

Optimal Proof Systems for Complex Sets are Hard to Find
by: Egidy, Fabian, et al.
Published: (2024)

Structure-Aware Encodings of Argumentation Properties for Clique-width
by: Mahmood, Yasir, et al.
Published: (2025)

A Note on the Complexity of Directed Clique
by: Gutowski, Grzegorz, et al.
Published: (2026)

KRW Composition Theorems via Lifting
by: de Rezende, Susanna F., et al.
Published: (2020)

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
by: Chew, Leroy, et al.
Published: (2024)

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
by: Ren, Hanlin, et al.
Published: (2025)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

A Brief Introduction to Quantum Query Complexity
by: Hamoudi, Yassine
Published: (2025)

Proving Unsatisfiability with Hitting Formulas
by: Filmus, Yuval, et al.
Published: (2023)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

It's Hard to HAC with Average Linkage!
by: Bateni, MohammadHossein, et al.
Published: (2024)

Hardness of the Binary Covering Radius Problem in Large $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2026)

From Proof Complexity to Circuit Complexity via Interactive Protocols
by: Arteche, Noel, et al.
Published: (2024)

Proof Complexity and Feasible Interpolation
by: Tabatabai, Amirhossein Akbar
Published: (2025)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
by: S., Karthik C., et al.
Published: (2021)

New Techniques for Constructing Rare-Case Hard Functions
by: Nareddy, Tejas, et al.
Published: (2024)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

Average-Case Complexity of Quantum Stabilizer Decoding
by: Khesin, Andrey Boris, et al.
Published: (2025)

On optimal distinguishers for Planted Clique
by: Nagda, Ansh, et al.
Published: (2025)

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
by: Fischer, Nick, et al.
Published: (2025)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
by: Chukhin, Nikolai, et al.
Published: (2024)