:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Yang, Yang
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	https://arxiv.org/abs/2403.11320
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
by: Yang, Yang
Published: (2025)

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

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

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

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

Deterministic factorization of constant-depth algebraic circuits in subexponential time
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)

On the complexity of global Roman domination problem in graphs
by: Reddy, Sangam Balchandar, et al.
Published: (2026)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
by: Prunet, Thibault, et al.
Published: (2023)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
by: Li, Tiange, et al.
Published: (2026)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

The communication complexity of distributed estimation
by: Gopalan, Parikshit, et al.
Published: (2025)

Parameterized complexity of reconfiguration of atoms
by: Cooper, Alexandre, et al.
Published: (2021)

An alignment problem
by: McDaniel, Emma L., et al.
Published: (2024)

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

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
by: Dell, Holger, et al.
Published: (2022)

On the complexity and approximability of Bounded access Lempel Ziv coding
by: Cicalese, Ferdinando, et al.
Published: (2024)

On girth and the parameterized complexity of token sliding and token jumping
by: Bartier, Valentin, et al.
Published: (2020)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
by: Ducoffe, Guillaume
Published: (2026)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
by: Enright, Jessica, et al.
Published: (2020)

The complexity of testing all properties of planar graphs, and the role of isomorphism
by: Basu, Sabyasachi, et al.
Published: (2021)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
by: Michel, Lukas, et al.
Published: (2023)

Time complexity of the Analyst's Traveling Salesman algorithm
by: Ramirez, Anthony, et al.
Published: (2022)

A lossless a priori splitting rule for split-delivery routing problems
by: Jones, Bo, et al.
Published: (2025)

Constructing self-referential instances for the clique problem
by: Li, Jiaqi, et al.
Published: (2026)

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

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
by: Dumas, Maël, et al.
Published: (2022)

Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
by: Bendotti, Pascale, et al.
Published: (2024)

Fast decision tree learning solves hard coding-theoretic problems
by: Koch, Caleb, et al.
Published: (2024)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
by: Scheder, Dominik, et al.
Published: (2025)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
by: Liu, Wei, et al.
Published: (2024)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

Fast and simple multiplication of bounded twin-width matrices
by: Kozma, László, et al.
Published: (2026)

Sublinear-query relative-error testing of halfspaces
by: Chen, Xi, et al.
Published: (2026)

Halfspaces are hard to test with relative error
by: Chen, Xi, et al.
Published: (2025)

Fast quantum algorithm for differential equations
by: Bagherimehrab, Mohsen, et al.
Published: (2023)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
by: Chen, Zherui, et al.
Published: (2024)