Buchumschlag

Nine lower bound conjectures on streaming approximation algorithms for CSPs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Singer, Noah G.
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Sketching approximations and LP approximations for finite CSPs are related
von: Singer, Noah G., et al.
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Streaming approximation resistance of every ordering CSP
von: Singer, Noah G., et al.
Veröffentlicht: (2021)

Clifford testing: algorithms and lower bounds
von: Hinsche, Marcel, et al.
Veröffentlicht: (2025)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
von: Fei, Yumou
Veröffentlicht: (2025)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
von: Jonsson, Peter, et al.
Veröffentlicht: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2026)

Streaming Complexity Separations for Dense and Sparse Graphs
von: Liu, Yang P., et al.
Veröffentlicht: (2026)

Simple approximation algorithms for Polyamorous Scheduling
von: Biktairov, Yuriy, et al.
Veröffentlicht: (2024)

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

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
von: Yang, Yang
Veröffentlicht: (2024)

Maximization of Approximately Submodular Functions
von: Horel, Thibaut, et al.
Veröffentlicht: (2024)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

Optimal lower bounds for quantum state tomography
von: Scharnhorst, Thilo, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Sensitivity Lower Bounds for Approximaiton Algorithms
von: Fleming, Noah, et al.
Veröffentlicht: (2024)

On approximability of the Permanent of PSD matrices
von: Ebrahimnejad, Farzam, et al.
Veröffentlicht: (2024)

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

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

A note on approximating the average degree of bounded arboricity graphs
von: Eden, Talya, et al.
Veröffentlicht: (2026)

On the complexity and approximability of Bounded access Lempel Ziv coding
von: Cicalese, Ferdinando, et al.
Veröffentlicht: (2024)

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
von: Allcock, Jonathan, et al.
Veröffentlicht: (2024)

MAX BISECTION might be harder to approximate than MAX CUT
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
von: Umans, Chris, et al.
Veröffentlicht: (2025)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
von: Björklund, Andreas, et al.
Veröffentlicht: (2025)

An unconditional lower bound for the active-set method on the hypercube
von: Disser, Yann, et al.
Veröffentlicht: (2025)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
von: Dell, Holger, et al.
Veröffentlicht: (2022)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
von: Yang, Yang
Veröffentlicht: (2025)

A tight quasi-polynomial bound for Global Label Min-Cut
von: Jaffke, Lars, et al.
Veröffentlicht: (2022)

An unconditional lower bound for the active-set method in convex quadratic maximization
von: Bach, Eleon, et al.
Veröffentlicht: (2025)

Second Price Matching with Complete Allocation and Degree Constraints
von: Pinchasi, Rom, et al.
Veröffentlicht: (2025)

Hardness of Dynamic Core and Truss Decompositions
von: Couto, Yan S., et al.
Veröffentlicht: (2025)

Fast and simple multiplication of bounded twin-width matrices
von: Kozma, László, et al.
Veröffentlicht: (2026)