:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Brown-Cohen, Jonah, Irving, Geoffrey, Piliouras, Georgios
Format:	Preprint
Published:	2025
Subjects:	Artificial Intelligence Computational Complexity Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2506.13609
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Debate is efficient with your time
by: Brown-Cohen, Jonah, et al.
Published: (2026)

Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
by: Tran, Tan D., 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)

$\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression
by: Nye, Logan
Published: (2025)

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
by: Kontogiannis, Andreas, et al.
Published: (2026)

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

Compression Barriers for Autoregressive Transformers
by: Haris, Themistoklis, 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)

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

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

Algorithms and Hardness for Estimating Statistical Similarity
by: Bhattacharyya, Arnab, et al.
Published: (2025)

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

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries
by: Chen, Mark, et al.
Published: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
by: Dakhno, Grigorii, et al.
Published: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
by: Bringmann, Karl, et al.
Published: (2024)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Optimality of Frequency Moment Estimation
by: Braverman, Mark, et al.
Published: (2024)

Dequantization and Hardness of Spectral Sum Estimation
by: Edenhofer, Roman, et al.
Published: (2025)

Stable Algorithms Lower Bounds for Estimation
by: Yu, Xifan, et al.
Published: (2026)

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)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

Precoloring extension with demands on paths
by: Das, Arun Kumar, et al.
Published: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
by: Maalouly, Nicolas El, et al.
Published: (2025)

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
by: Dhar, Anubhav, et al.
Published: (2025)

Scheduling Problems with Constrained Rejections
by: Davies, Sami, et al.
Published: (2025)

Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
by: Uhlmann, Jeffrey
Published: (2025)