Cover Image

Hard CNF Instances for Ideal Proof Systems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hakoniemi, Tuomas, Limaye, Nutan, Tzameret, Iddo
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

Lower Bounds against the Ideal Proof System in Finite Fields
by: Elbaz, Tal, et al.
Published: (2025)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
by: Atserias, Albert, et al.
Published: (2024)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
by: Lu, Jiaqi, et al.
Published: (2025)

New Bounds for the Ideal Proof System in Positive Characteristic
by: Behera, Amik Raj, et al.
Published: (2025)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
by: Behera, Amik Raj, et al.
Published: (2026)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

Symmetric Proofs in the Ideal Proof System
by: Dawar, Anuj, et al.
Published: (2025)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
by: Austrin, Per, et al.
Published: (2024)

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

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
by: Armand, Jules, et al.
Published: (2025)

On Extremal Properties of k-CNF: Capturing Threshold Functions
by: Gurumukhani, Mohit, et al.
Published: (2024)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
by: Yamakami, Tomoyuki
Published: (2017)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
by: de Rezende, Susanna F., et al.
Published: (2026)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
by: Garg, Abhibhav, et al.
Published: (2025)

Compilation and Fast Model Counting beyond CNF
by: de Colnet, Alexis, et al.
Published: (2025)

Compression with wildcards: All models of a Boolean 2-CNF
by: Wild, Marcel
Published: (2012)

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

Proof Systems Based on Structured Circuits
by: Micun, Matthäus, et al.
Published: (2026)

Recursive Jump Operators and Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Ideals, Macaulay Bases, and PCPs
by: Amireddy, Prashanth, et al.
Published: (2025)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

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

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
by: Chavrimootoo, Michael C., et al.
Published: (2026)

Hardness of SetCover Reoptimization
by: Jansen, Klaus, et al.
Published: (2025)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

Distribution-Free Proofs of Proximity
by: Aaronson, Hugo, et al.
Published: (2023)

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

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)

Multi-Prover Interactive Proof Systems with Leakage
by: Asadi, Vahid R., et al.
Published: (2026)

An Overview of the Theory of Instances Computational Complexity
by: Jorge A. Ruiz-Vanoye
Published: (2011)

A Graphical #SAT Algorithm for Formulae with Small Clause Density
by: Laakkonen, Tuomas, et al.
Published: (2022)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

Hardness of clique approximation for monotone circuits
by: Błasiok, Jarosław, et al.
Published: (2025)

Hardness Amplification via Group Theory
by: Nareddy, Tejas, et al.
Published: (2024)

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
by: Gay, William, et al.
Published: (2026)

Higher Hardness Results for the Reconfiguration of Odd Matchings
by: Dorfer, Joseph
Published: (2026)

Hard-to-Sample Distributions from Robust Extractors
by: Byramji, Farzan, et al.
Published: (2026)

Tetris is Hard with Just One Piece Type
by: MIT Hardness Group, et al.
Published: (2026)