:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Chew, Leroy, de Colnet, Alexis, Slivovsky, Friedrich, Szeider, Stefan
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2402.00542
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Towards Uniform Certification in QBF
by: Chew, Leroy, et al.
Published: (2022)

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

Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
by: Beyersdorff, Olaf, et al.
Published: (2021)

Proofdoors and Efficiency of CDCL Solvers
by: Singh, Sunidhi, et al.
Published: (2026)

Counting and Sampling Traces in Regular Languages
by: de Colnet, Alexis, et al.
Published: (2025)

Better Extension Variables in DQBF via Independence
by: Chew, Leroy, et al.
Published: (2025)

Extending CDCL to disjunctions of parity equations
by: Beame, Paul, et al.
Published: (2026)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
by: Samar, Sahil, et al.
Published: (2026)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
by: Zhang, Tianwei, et al.
Published: (2024)

Model Counting for Dependency Quantified Boolean Formulas
by: Fung, Long-Hin, et al.
Published: (2025)

Explaining Decisions in ML Models: a Parameterized Complexity Analysis
by: Ordyniak, Sebastian, et al.
Published: (2024)

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

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

Exponential Separation Between Powers of Regular and General Resolution Over Parities
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2024)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
by: Byramji, Farzan, et al.
Published: (2025)

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

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

Parity Tests with Ties
by: Kupfer, Ron
Published: (2026)

Hard QBFs for Merge Resolution
by: Beyersdorff, Olaf, et al.
Published: (2020)

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
by: Khadiev, Kamil, et al.
Published: (2017)

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

Transcendental Encoding conjecture
by: Keshavan, Anand Kumar, et al.
Published: (2025)

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)

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

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)

Are Depth-2 Regular Expressions Hard to Intersect?
by: Ascone, Rocco, et al.
Published: (2025)

Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)

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)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
by: Ramya, C., et al.
Published: (2025)

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

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

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

Compression of Voxelized Vector Field Data by Boxes is Hard
by: Zhang, Simon
Published: (2025)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
by: Casteigts, Arnaud, et al.
Published: (2026)

Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated
by: Gretta, Lucas, et al.
Published: (2026)