No article text was recorded for this version.
precision-complexity tradeoff
Version 2 of 21,108 papers1,301 conceptsfrozen 2026-10-04
Papers in this version
- Blog: Lower bounds for approximation schemes for Closest String
- Blog: Approximating Partition Functions in Constant Time
- Blog: Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings
- Blog: Approximating Semidefinite Programs in Sublinear Time
- Blog: On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets
- Blog: Entrywise Approximate Laplacian Solving
- Blog: The power of local search for clustering
- Blog: Polynomial Precision Dependence Solutions to Alignment Research Center Matrix Completion Problems
- Blog: Learning Halfspaces and Neural Networks with Random Initialization
- Blog: Tight Bounds for the Subspace Sketch Problem with Applications
- Blog: Deterministic Heavy Hitters with Sublinear Query Time
- Blog: Fast Approximate CoSimRanks via Random Projections
- Blog: High dimensional online calibration in polynomial time
- Blog: High-dimensional approximate r-nets
- Blog: Polynomial-Sized Topological Approximations Using The Permutahedron
- Blog: A Minimum Discounted Reward Hamilton-Jacobi Formulation for Computing Reachable Sets
- Blog: On Estimating Maximum Matching Size in Graph Streams
- Blog: Estimating the longest increasing sequence in polylogarithmic time
- Blog: Sublinear time spectral density estimation
- Blog: Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees
- Blog: From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces
- Blog: Tracking p-adic precision
- Blog: Reduced basis method and domain decomposition for elliptic problems in networks and complex parametrized geometries
- Blog: A Scalable CUR Matrix Decomposition Algorithm: Lower Time Complexity and Tighter Bound
- Blog: MAPEL: Achieving global optimality for a non-convex wireless power control problem
- Blog: On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks
- Blog: Exponential-Time Approximation of Hard Problems
- Blog: Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- Blog: Geometric Bipartite Matching is in NC
- Blog: Moments, Random Walks, and Limits for Spectrum Approximation
- Blog: Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
- Blog: SimBa: An Efficient Tool for Approximating Rips-filtration Persistence via Simplicial Batch Collapse
- Blog: Pandora Box Problem with Nonobligatory Inspection: Hardness and Improved Approximation Algorithms
- Blog: A Fast Algorithm for Reconstructing Motion-Compensated Blocks in Compressed Domain
- Blog: A Tight (3/2 + ε)-Approximation Algorithm for Demand Strip Packing
- Blog: On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
- Blog: Almost Linear Constant-Factor Sketching for 𝓁1 and Logistic Regression
- Blog: Quantitative combinatorial geometry for continuous parameters
- Blog: Mini-Buckets: A General Scheme for Generating Approximations in Automated
- Blog: An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model
- Blog: A conservative aggressive subspace tracker
- Blog: Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent
- Blog: Complexity Analysis of the Lasso Regularization Path
- Blog: Competitive Equilibrium for Chores: from Dual Eisenberg-Gale to a Fast, Greedy, LP-based Algorithm
- Blog: Faster Algorithms for Testing under Conditional Sampling
- Blog: Compositional Synthesis of Finite State Abstractions
- Blog: An Analytical Solution for Probabilistic Guarantees of Reservation Based Soft Real-Time Systems
- Blog: Tree Approximation for Belief Updating
- Blog: Accuracy vs. Efficiency Trade-offs in Optical Flow Algorithms
- Blog: Towards Optimal Running Times for Optimal Transport
- Blog: Efficient approximation schemes for uniform-cost clustering problems in planar graphs
- Blog: Learning to Sample from Censored Markov Random Fields
- Blog: Statistical process discovery
- Blog: Unconstrained Submodular Maximization with Constant Adaptive Complexity
- Blog: A neuro-symbolic framework for answering conjunctive queries
- Blog: Fine Grained Lower Bounds for Multidimensional Knapsack
- Blog: Reliever: Relieving the Burden of Costly Model Fits for Changepoint Detection
- Blog: Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm
- Blog: A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions
- Blog: Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time
Showing 60 of 1,108 papers.
History & citation
Current · Permanent link
- Tunable Tradeoffs Between Runtime and Approximation Quality merged into this direction (52% overlap)
- Tunable Hierarchical Low-Rank Matrix Approximations merged into this direction (50% overlap)
Cite this direction
Latest version (a living page):
@misc{lacuna_precision_complexity_tradeoff_c3abbb46,
title = {precision-complexity tradeoff},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/precision-complexity-tradeoff/rdr_c3abbb46db0d4b599290d96f9023b9d9},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}This exact version (version 2, frozen text):
@misc{lacuna_precision_complexity_tradeoff_c3abbb46_v2,
title = {precision-complexity tradeoff},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/precision-complexity-tradeoff/rdr_c3abbb46db0d4b599290d96f9023b9d9/v/2},
note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}