archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 4
-
Threshold policy achieves 4/3 guarantee for unknown supply
Online Allocation with Unknown Shared Supply
-
PQ and TDS learning models are equivalent for distribution-free Boolean classes
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
-
PQ learning reduces to TDS learning for any Boolean concept class
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
-
Dynamic programming speeds ranked choice model estimation
Modern column generation for estimating single- and multi-purchase ranked list choice models
-
Accelerated method reaches 0.827-approx for log coverage rewards
Accelerated Relax-and-Round for Concave Coverage Problems
-
O(log m) approximation for multi-interface coverage
Polylogarithmic Approximation for Covering and Connecting Multi-Interface Networks
-
Deletion-only forest sums maintained in O(log* n) time
Fast decremental tree sums in forests
-
Sum-of-radii clustering with k centers is W[2]-hard
On the Parameterized Approximability of (Mergeable) Sum of Radii Clustering
-
ILP computes exact optima for shortest-path network design
Designing Capacitated Subnetworks for Shortest Path Routing
-
Bilateral treewidth makes QBF evaluation fixed-parameter tractable
Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
-
Contrastive pairs identify concepts under any finite noise
Contrastive Identification and Generation in the Limit
-
Randomized bidding strategies achieve matching upper and lower bounds on consistency as a…
The Pareto Frontier of Randomized Learning-Augmented Online Bidding
-
Matching bounds close gap for randomized online bidding
The Pareto Frontier of Randomized Learning-Augmented Online Bidding
-
Two Hadamard transforms match uniform rotations for quantization
Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven
-
Label correcting algorithms find nondominated temporal paths without monotonicity
Label Correcting Algorithms for the Multiobjective Temporal Shortest Path Problem
-
Glauber annealing converges to ε KL error in O(n^5 β²/ε) steps for Ising
Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms
-
Poly-time scheme approximates dyadic codings of LLM outputs
An Additive Approximation Scheme for Generating Dyadic Codings for the Outputs of an LLM
-
Online algorithms hit exact limit for independent sets in dense hypergraphs
Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
-
Attention coresets shrink to sqrt(d) exp(rho) size
Nearly Optimal Attention Coresets
-
Balanced separator for minor-free graphs improved to O(h sqrt(log h) sqrt n)
A Separator for Minor-Free Graphs Beyond the Flow Barrier
-
Balanced separators shrink to O(h sqrt(log h) sqrt(n)) for minor-free graphs
A Separator for Minor-Free Graphs Beyond the Flow Barrier
-
Hypergraph routing of code blocks takes Θ(d_C log N_L) depth
Block Permutation Routing on Ramanujan Hypergraphs for Fault-Tolerant Quantum Computing
-
Surface-code blocks route in Θ(d_C log N_L) steps
Block Permutation Routing on Ramanujan Hypergraphs for Fault-Tolerant Quantum Computing
-
Algorithms compute shortest unique substrings in O(n log σ/√log n) time
Faster Algorithms for Shortest Unique or Absent Substrings
-
Deterministic structure matches randomized Online Orthogonal Vectors
Online Orthogonal Vectors Revisited
-
Beam search achieves quadratic error decay in random subset sum
Inverse Quadratic Decay in Random Subset Sum
-
Beam search on meshes yields quadratic error decay for subset sum
Inverse Quadratic Decay in Random Subset Sum
-
Pruning hits tight 1-1/e bound for monotone submodular selection
Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation
-
One-pass linear-time algorithm for suffixient arrays
Constructing Suffixient Arrays Revisited
-
Refined segments speed up iterative PBWT queries
Faster Iterative $\phi$ Queries on the Positional BWT
-
Zonotope containment gets O(√d) approximation algorithm
Nearly-Tight Bounds for Zonotope Containment and Beyond
-
Algorithm finds matroid basis in n^{3/7} parallel rounds
An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
-
Sparse FFT reaches O(sqrt(N) log k) expected time with deterministic safety
Deterministic Sparse FFT via Keyed Multi-View Gating with $O(\sqrt{N} \log k)$ Expected Time
-
No online algorithm finds common induced subgraphs beyond 2 log n
Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
-
Parallel algorithms cut depth below sqrt(n) for reachability on dense digraphs
Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
-
Randomized algorithm approximates TV distance of product mixtures
On Computing Total Variation Distance Between Mixtures of Product Distributions
-
Two open problems proven XNLP-complete in scheduling and graphs
The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
-
Algorithm samples SK model with negligible TVD error below beta 1/2
Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
-
Algorithm samples SK model with negligible TVD error up to β=1/2
Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
-
Quantum estimator nears optimal complexity for Tsallis entropy
Quantum Multi-Level Estimation of Functionals of Discrete Distributions
-
Optimal polytree found in O((2+ε)^n) time for constant in-degree
Exact and Approximate Algorithms for Polytree Learning
-
Vertex pruning counts balanced bicliques 636 times faster
Counting Small Balanced (p,q)-bicliques in Signed Bipartite Graphs
-
O(n²) algorithm finds optimal diameter partitions for every size
An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
-
MPC with limited machines needs higher local exponents for superlinear tasks
On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
-
Low-dimensional embeddings violate half of triplet constraints
Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
-
Decomposition enables O(log n + k) visibility queries in O(n^{2+ε}) space
Visibility Queries in Simple Polygons
-
Dynamic data structures answer long-path queries in polylog time
Dynamic Detours
-
Poisson process matches tight submodular approximation
A Poisson Process for Submodular Maximization
-
Similarity merges bound the possible ranks of any chosen subset
Ranking with Partitioning
-
Ramanujan hypergraphs route qubits in log N steps
Permutation Routing on Ramanujan Hypergraphs with Applications to Neutral Atom Quantum Architectures