Buchumschlag

Solution independence and self-referential instances

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Zhou, Guangyan, Wang, Bin, Wang, Jianxin, Xu, Ke
Format:	Preprint
Veröffentlicht:	2026
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

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

Constructing self-referential instances for the clique problem
von: Li, Jiaqi, et al.
Veröffentlicht: (2026)

Further Explanations on "SAT Requires Exhaustive Search"
von: Dong, Qingxiu, et al.
Veröffentlicht: (2024)

SAT Requires Exhaustive Search
von: Xu, Ke, et al.
Veröffentlicht: (2023)

On the instance optimality of detecting collisions and subgraphs
von: Ben-Eliezer, Omri, et al.
Veröffentlicht: (2023)

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

Downward self-reducibility in the total function polynomial hierarchy
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2025)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
von: de Berg, Mark, et al.
Veröffentlicht: (2025)

More Asymmetry Yields Faster Matrix Multiplication
von: Alman, Josh, et al.
Veröffentlicht: (2024)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
von: Wang, Chengu
Veröffentlicht: (2026)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

Kernelization Complexity of Solution Discovery Problems
von: Grobler, Mario, et al.
Veröffentlicht: (2024)

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

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

Can You Link Up With Treewidth?
von: Curticapean, Radu, et al.
Veröffentlicht: (2024)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
von: Kothari, Pravesh K., et al.
Veröffentlicht: (2025)

A New Information Complexity Measure for Multi-pass Streaming with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

Neighborhood-Aware Graph Labeling Problem
von: Shahverdikondori, Mohammad, et al.
Veröffentlicht: (2026)

Lazy Kronecker Product
von: Song, Zhao
Veröffentlicht: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
von: Jiang, Cheng, et al.
Veröffentlicht: (2026)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
von: Ducoffe, Guillaume
Veröffentlicht: (2026)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
von: Asadi, Vahid R., et al.
Veröffentlicht: (2026)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2026)

Online Orthogonal Vectors Revisited
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2026)

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

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
von: Chen, Xi, et al.
Veröffentlicht: (2026)

Sublinear-query relative-error testing of halfspaces
von: Chen, Xi, et al.
Veröffentlicht: (2026)

Quadratic Speedup for Computing Contraction Fixed Points
von: Chen, Xi, et al.
Veröffentlicht: (2026)

A Space-space Trade-off for Directed st-Connectivity
von: Edenhofer, Roman
Veröffentlicht: (2026)

Asymptotic Rank Speedup Theorems, Revisited
von: Alman, Josh, et al.
Veröffentlicht: (2026)

Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
von: Ganian, Robert, et al.
Veröffentlicht: (2026)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

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

Kernelization Bounds for Constrained Coloring
von: Haviv, Ishay
Veröffentlicht: (2026)

On the Advantage of Adaptivity for Sampling with Cell Probes
von: Byramji, Farzan, et al.
Veröffentlicht: (2026)

Clustering with Locally Bounded Ignorance
von: Garvardt, Jaroslav, et al.
Veröffentlicht: (2026)

Submodular Maximization under Supermodular Constraint: Greedy Guarantees
von: Srivastava, Ajitesh, et al.
Veröffentlicht: (2026)

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
von: Oka, Keigo, et al.
Veröffentlicht: (2026)