:: Library Catalog

Cover Image

Saved in:

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

Similar Items

Universal Hirschberg for Width Bounded Dynamic Programs
by: Nye, Logan
Published: (2025)

Compression Barriers for Autoregressive Transformers
by: Haris, Themistoklis, et al.
Published: (2025)

Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
by: Tran, Tan D., et al.
Published: (2025)

Avoiding Obfuscation with Prover-Estimator Debate
by: Brown-Cohen, Jonah, et al.
Published: (2025)

Sorting by Strip Swaps is NP-Hard
by: Roy, Swapnoneel, et al.
Published: (2025)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
by: Rao, Satish
Published: (2025)

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

Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity
by: Feng, Guhao, et al.
Published: (2023)

No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
by: Kothari, Robin, et al.
Published: (2025)

Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
by: Blum, Avrim, et al.
Published: (2025)

Theoretical limitations of multi-layer Transformer
by: Chen, Lijie, et al.
Published: (2024)

Diversity-aware clustering: Computational Complexity and Approximation Algorithms
by: Thejaswi, Suhas, et al.
Published: (2024)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
by: Chudigiewitsch, Florian, et al.
Published: (2026)

A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
by: Jaffke, Lars, et al.
Published: (2025)

SAT Requires Exhaustive Search
by: Xu, Ke, et al.
Published: (2023)

Finding hardness reductions automatically using SAT solvers
by: Bergold, Helena, et al.
Published: (2024)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
by: Guruswami, Venkatesan, et al.
Published: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
by: Stoian, Mihail
Published: (2024)

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

Subset Balancing and Generalized Subset Sum via Lattices
by: Gao, Yiming, et al.
Published: (2026)

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

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
by: Yoshida, Yuichi, et al.
Published: (2025)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
by: Curticapean, Radu, et al.
Published: (2024)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
by: Firbas, Alexander, et al.
Published: (2024)

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

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
by: Kothari, Pravesh K., et al.
Published: (2025)

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

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
by: Cheng, Kuan, et al.
Published: (2025)

A general framework for finding diverse solutions via network flow and its applications
by: Iwamasa, Yuni, et al.
Published: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
by: Greilhuber, Jakob, et al.
Published: (2026)

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

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
by: Sato, Atsuki, et al.
Published: (2024)

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

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
by: Gaspers, Serge, et al.
Published: (2025)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

The Trichotomy of Regular Property Testing
by: Bathie, Gabriel, et al.
Published: (2025)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)