Cover Image

Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Blum, Avrim, Hsu, Daniel, Rashtchian, Cyrus, Saless, Donya
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Artificial Intelligence Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Regularized Robustly Reliable Learners and Instance Targeted Attacks
by: Blum, Avrim, et al.
Published: (2024)

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

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

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
by: Fei, Yumou
Published: (2025)

Improved Algorithm for Permutation Testing
by: Zhang, Xiaojin
Published: (2020)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
by: Esmer, Barış Can, et al.
Published: (2022)

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

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

Parameterized Algorithms for Editing to Uniform Cluster Graph
by: Gaikwad, Ajinkya, et al.
Published: (2024)

From Amortized to Worst Case Delay in Enumeration Algorithms
by: Capelli, Florent, et al.
Published: (2021)

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

Frontier Space-Time Algorithms Using Only Full Memory
by: Chmel, Petr, et al.
Published: (2026)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
by: Gaikwad, Ajinkya, et al.
Published: (2025)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
by: Buhrman, Harry, et al.
Published: (2025)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

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

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
by: Stoian, Mihail
Published: (2024)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
by: Arvind, V., et al.
Published: (2023)

Generalized Graph Packing Problems Parameterized by Treewidth
by: Esmer, Barış Can, et al.
Published: (2025)

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

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)

Colouring $(P_r+P_s)$-Free Graphs
by: Klimošová, Tereza, et al.
Published: (2018)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

On Optimal Testing of Linearity
by: Arora, Vipul, et al.
Published: (2024)

Streaming Zero-Knowledge Proofs
by: Cormode, Graham, et al.
Published: (2023)

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

Testing Properties of Edge Distributions
by: Fei, Yumou
Published: (2026)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

Computational Complexity in Property Testing
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

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

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
by: Frei, Fabian, et al.
Published: (2025)

Exact Algorithms for Distance to Unique Vertex Cover
by: Fioravantes, Foivos, et al.
Published: (2025)

Hardness and Algorithmic Results for Roman \{3\}-Domination
by: Reddy, Sangam Balchandar
Published: (2025)

Testing noisy low-degree polynomials for sparsity
by: Bao, Yiqiao, et al.
Published: (2025)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)