:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Austrin, Per, Håstad, Johan, Martinsson, Björn
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2511.21450
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
by: Martinsson, Björn
Published: (2024)

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

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

A logarithmic approximation of linearly ordered colourings
by: Håstad, Johan, et al.
Published: (2024)

Equations over Finite Monoids with Infinite Promises
by: Larrauri, Alberto, et al.
Published: (2025)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
by: Asimi, Kristina, et al.
Published: (2024)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

Discrete Homotopy and Promise Constraint Satisfaction Problem
by: Beikmohammadi, Arash, et al.
Published: (2025)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
by: MIT Hardness Group, et al.
Published: (2024)

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

Optimal Inapproximability of Promise Equations over Finite Groups
by: Butti, Silvia, et al.
Published: (2024)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

A parallel framework for graphical optimal transport
by: Fan, Jiaojiao, et al.
Published: (2024)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

Mittag-Leffler type theorems for Helson zeta-functions
by: Andersson, Johan
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

A Liouville Theorem and $C^α$-Estimate for Calabi-Yau Cones
by: Klemmensen, Johan Jacoby
Published: (2025)

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

Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
by: Schleich, Philipp, et al.
Published: (2024)

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
by: Ketkov, Sergey S., et al.
Published: (2025)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
by: Colli, Giordano
Published: (2025)

Arithmetic Circuits with Division
by: Sacher, Silas Cato
Published: (2025)

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
by: Nkosi, Thami
Published: (2025)

The Line Traveling Salesman and Repairman Problem with Collaboration
by: Golak, Julian, et al.
Published: (2025)

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

Lifting for Arbitrary Gadgets
by: Iyer, Siddharth
Published: (2025)

PLS-completeness of string permutations
by: Scheder, Dominik, et al.
Published: (2025)

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
by: Chattopadhyay, Arkadev, et al.
Published: (2025)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
by: Krokhin, Andrei, et al.
Published: (2025)

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

Nonogram: Complexity of Inference and Phase Transition Behavior
by: Foote, Aaron, et al.
Published: (2025)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
by: Mukhopadhyay, Partha, et al.
Published: (2025)

Geometry Matters in Planar Storyplans
by: Dobler, Alexander, et al.
Published: (2025)

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

Order Retrieval in Compact Storage Systems
by: Fliedner, Malte, et al.
Published: (2025)

On the Complexity of Claw-Free Vertex Splitting
by: Abu-Khzam, Faisal N., et al.
Published: (2025)

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

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
by: Hörsch, Florian, et al.
Published: (2025)