:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Jonsson, Peter, Lagerkvist, Victor, de Vlas, Jorke M., Wahlström, Magnus
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	https://arxiv.org/abs/2508.16389
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
by: Kim, Eun Jung, et al.
Published: (2022)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
by: Fei, Yumou
Published: (2025)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Sketching approximations and LP approximations for finite CSPs are related
by: Singer, Noah G., et al.
Published: (2025)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
by: Sharma, Amatya, et al.
Published: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
by: Sharma, Amatya, et al.
Published: (2026)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

CSPs with Few Alien Constraints
by: Jonsson, Peter, et al.
Published: (2024)

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

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

Emit As You Go: Enumerating Edges of a Spanning Tree
by: Casel, Katrin, et al.
Published: (2025)

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

TwinArray Sort: An Ultrarapid Conditional Non-Comparison Based Sorting Algorithm
by: Amini, Amin
Published: (2024)

Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
by: Benedek, Márton, et al.
Published: (2023)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
by: Frei, Fabian, et al.
Published: (2025)

Inapproximability of Maximum Diameter Clustering for Few Clusters
by: Fleischmann, Henry, et al.
Published: (2023)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
by: Frei, Fabian, et al.
Published: (2024)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Gray Codes With Constant Delay and Constant Auxiliary Space
by: Amarilli, Antoine, et al.
Published: (2026)

Resilient functions: Optimized, simplified, and generalized
by: Ivanov, Peter, et al.
Published: (2024)

Breadth-First Search Trees with Many or Few Leaves
by: Beisegel, Jesse, et al.
Published: (2026)

Removable Online Knapsack and Advice
by: Böckenhauer, Hans-Joachim, et al.
Published: (2020)

Beyond Bits: An Introduction to Computation over the Reals
by: Miltzow, Tillmann
Published: (2026)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

Parameterized Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2025)

Optimal FPT-Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2026)

Representative set statements for delta-matroids and the Mader delta-matroid
by: Wahlström, Magnus
Published: (2023)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
by: de Berg, Mark, et al.
Published: (2025)

Most Juntas Saturate the Hardcore Lemma
by: Kumar, Vinayak M.
Published: (2025)

Linear Hashing Is Optimal
by: Jaber, Michael, et al.
Published: (2025)

On the Advantage of Adaptivity for Sampling with Cell Probes
by: Byramji, Farzan, et al.
Published: (2026)

Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
by: Tani, Seiichiro
Published: (2019)

Distributed Triangle Detection is Hard in Few Rounds
by: Assadi, Sepehr, et al.
Published: (2025)

Fast Compressed-Domain N-Point Discrete Fourier Transform: The "Twiddless" FFT Algorithm
by: Queiroz, Saulo
Published: (2025)

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
by: Allcock, Jonathan, et al.
Published: (2024)