archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 3
-
FPT schemes give (1+ε) approximations for min-sum radii and diameters
FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
-
Language generators bound total mistakes by log of class size
Mistake-Bounded Language Generation
-
Exponential bound proven for LCP sufficient-matrix handicaps
Handicap reduction for linear complementarity problems
-
CPU radix sort reaches 6x bandwidth efficiency on large datasets
FractalSortCPU: Bandwidth-Efficient Compressed Radix Sort on CPU
-
CPU radix sort cuts bandwidth use by 6x on large data
FractalSortCPU: Bandwidth-Efficient Compressed Radix Sort on CPU
-
Label-private convex optimization now scales as sqrt(K) excess risk
Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
-
New algorithm tightens 2-vertex-connectivity approximation to 95/72 + ε
An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
-
Algorithm tightens GMSSC approximation to 4.509
A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
-
Dynamic rank updates now scale with rank r
Dynamic Rank, Basis, and Matching
-
Online Steiner forest achieves constant ratio with O(log n) recourse
Online Steiner Forest with Recourse
-
Streaming max-cut needs linear space in dense graphs
Streaming Complexity Separations for Dense and Sparse Graphs
-
GenusSink makes Sinkhorn near-linear on planar graphs
Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
-
Near-linear Sinkhorn for geodesic transport on bounded-genus graphs
Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
-
Fast sketching accelerates power method for low-rank approximations
Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
-
Engine combines DP routines to test Boolean graph properties on bounded treewidth
TreeWidzard: An Engine for Width-Based Dynamic Programming and Automated Theorem Proving
-
Canonization and pruning verify Reed conjecture up to pathwidth 5
State Canonization and Early Pruning in Width-Based Automated Theorem Proving
-
Greedy recolors O(1/sqrt(Delta)) edges per insertion on forests
Dynamic Edge Coloring of Forests
-
Small subsets approximate the global ranking median
A Scalable and Unified Framework to Weighted Rank Aggregation
-
Deterministic algorithm finds high-order element or factors N
Deterministically finding an element of large order in $\mathbb{Z}_N^*$
-
Min-cost flows fit in subquadratic streaming space
Computing Flows in Subquadratic Space
-
ALiBi bias equals average of random block masks
Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases
-
Deterministic algorithms cannot optimize both time and I/O for convex hull
The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
-
Deterministic algorithms cannot hit both time and I/O optima for convex hulls
The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
-
Neural predictions warm-start exact LAP solvers for 2x speedups
Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
-
Weighted graphs get nearly equitable colorings with O(Δ) colors
Equitable Colorings of Vertex-Weighted Graphs
-
Algorithm finds induced diamonds in Õ(n^{2.425}/t^{0.25}) time
Witness-Sensitive Detection of Induced Diamonds
-
Simpler algorithm solves node-weighted triangles in MM(n) time
Node-Weighted Triangles: Faster and Simpler
-
Online factorization matches offline error up to logs
Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
-
Evacuation ratio bounded by 4+2√2 with majority reliable agents
Search and evacuation with a near majority of faulty agents
-
Bounded Gaussian surface area allows non-negative L1 approximations
A Note on Non-Negative $L_1$-Approximating Polynomials
-
Planarizing gadgets do not exist for (k,l)-tight graphs
Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
-
Vertex cover local search runs in ℓ^{f(k)} n time
Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
-
Greedy yields curvature ratio for any submodular function
Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
-
Lettericity word and decoder retrieval solved in polynomial time
Towards Settling the Complexity of the Lettericity Problem
-
Subquadratic algorithm for shortest tours of disjoint polygons
Touring a Sequence of Orthogonal Polygons
-
Shortest tours for disjoint orthogonal polygons in subquadratic time
Touring a Sequence of Orthogonal Polygons
-
Algorithm computes Hermite form of relation lattices at matrix mult cost
Computing bases in Hermite normal form of lattices of integer relations
-
One pass computes (Δ-1)-coloring for large-degree graphs
Beyond Brooks: $(\Delta-1)$-Coloring in Semi-Streaming
-
Deterministic streaming colors with O(Δ) colors in O(sqrt(log Δ)) passes
Faster Deterministic Streaming Vertex Coloring
-
Coordinated robot motion is FPT on polygon discretizations
Coordinated Motion Planning is FPT on Discretized Simple Polygons
-
Algorithm retrieves minimal points for imprecise Pareto fronts
Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
-
Adding loops to quantum walk composition matches prior search bounds
Loop Composition in Quantum Algorithms
-
Frugal algorithm achieves zero regret at O(log T) movement
Convex Optimization with Nested Evolving Feasible Sets
-
Bidding profiles close gap for randomized online bidding
Optimal Learning-Augmented Algorithm for Online Bidding
-
Backreference regex matching needs n to the 2k power
On the Complexity of the Matching Problem of Regular Expressions with Backreferences
-
EPTAS for ConstrainedMinCut on everywhere-dense graphs
EPTAS for Hard Graph Cut Problems for Dense Graphs
-
Oracle answers connectivity after k failures in O(k) time
Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
-
Deterministic Monotone Min-Plus Product hits O(n^{2.686}) time
Deterministic Monotone Min-Plus Product and Convolution
-
This paper proves that removing points with the largest K-nearest-neighbor distances…
Simple KNN-Based Outlier Detection Achieves Robust Clustering
-
Node-arrival stream yields sublinear-space estimate of clustering cost
Estimating Correlation Clustering Cost in Node-Arrival Stream