Cover Image

Supercritical Tradeoffs for Monotone Circuits

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Göös, Mika, Maystre, Gilbert, Risse, Kilian, Sokolov, Dmitry
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity F.2.2; F.1.3; I.2.3; F.4.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
by: de Rezende, Susanna F., et al.
Published: (2019)

On bounded depth proofs for Tseitin formulas on the grid; revisited
by: Håstad, Johan, et al.
Published: (2022)

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

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

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

Direct Sums for Parity Decision Trees
by: Besselman, Tyler, et al.
Published: (2024)

On the Satisfaction Probabilities of $k$-CNF Formulas
by: Tantau, Till
Published: (2022)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
by: Bodnar, Levente
Published: (2024)

A Rust-to-Lean Verification Pipeline with AI Provers: An Experience Report
by: Klaus, Natalia, et al.
Published: (2026)

Unravelling Abstract Cyclic Proofs into Proofs by Induction
by: Grotenhuis, Lide, et al.
Published: (2026)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

Logics for the Relational Syllogistic
by: Pratt-Hartmann, Ian, et al.
Published: (2008)

OnlineProver: Experience with a Visualisation Tool for Teaching Formal Proofs
by: Perháč, Ján, et al.
Published: (2025)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
by: Rossman, Benjamin
Published: (2024)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
by: van Brügge, Jan
Published: (2024)

A Coq-based Axiomatization of Tarski's Mereogeometry
by: Barlatier, Patrick, et al.
Published: (2025)

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

A Sequent Calculus for General Inductive Definitions
by: Eede, Robbe Van den, et al.
Published: (2026)

SPARQL in N3: SPARQL CONSTRUCT as a rule language for the Semantic Web (Extended Version)
by: Arndt, Dörthe, et al.
Published: (2025)

Mechanized HOL Reasoning in Set Theory
by: Guilloud, Simon, et al.
Published: (2024)

Incomplete Descriptions and Qualified Definiteness
by: Więckowski, Bartosz
Published: (2024)

Term Orders for Optimistic Lambda-Superposition
by: Bentkamp, Alexander, et al.
Published: (2025)

Metric Equational Theories
by: Mardare, Radu, et al.
Published: (2025)

Canonical for Automated Theorem Proving in Lean
by: Norman, Chase, et al.
Published: (2025)

Implementing Dependent Type Theory Inhabitation and Unification
by: Norman, Chase, et al.
Published: (2026)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)

Notes on CSPs and Polymorphisms
by: Brady, Zarathustra
Published: (2022)

FastLEC: Parallel Datapath Equivalence Checking with Hybrid Engines
by: Zhang, Xindi, et al.
Published: (2025)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
by: Saha, Barna, et al.
Published: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
by: Salas, Jesus
Published: (2025)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

Understanding Syllogistic Reasoning in LLMs from Formal and Natural Language Perspectives
by: Poddar, Aheli, et al.
Published: (2025)

A LOCAL View of the Polynomial Hierarchy
by: Reiter, Fabian
Published: (2023)

Search versus Search for Collapsing Electoral Control Types
by: Carleton, Benjamin, et al.
Published: (2022)

Anyone but Him: The Complexity of Precluding an Alternative
by: Hemaspaandra, Edith, et al.
Published: (2005)

Experiments with Choice in Dependently-Typed Higher-Order Logic
by: Ranalter, Daniel, et al.
Published: (2024)

Discernment is all you need
by: Fuenmayor, David
Published: (2026)

Tractable and Intractable Entailment Problems in Separation Logic with Inductively Defined Predicates
by: Echenim, Mnacho, et al.
Published: (2023)

Solving Quantified Modal Logic Problems by Translation to Classical Logics
by: Steen, Alexander, et al.
Published: (2022)