archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 8
-
Closed forms give exact multi-NUMA VM counts per host
Efficient calculation of available space for multi-NUMA virtual machines
-
Clustering oracles for big graphs need far less memory
Sublinear Spectral Clustering Oracle with Little Memory
-
The paper shows a simple greedy algorithm achieves a competitive ratio equal to the…
Online Algorithms for Geometric Independent Set
-
IPv6 lookup reaches 390M per core by 2D-to-1D interval transformation
PlanB: Efficient Software IPv6 Lookup with Linearized $B^+$-Tree
-
Directed max flow computed in almost m + nF time
Balancing Weights, Directed Sparsification, and Augmenting Paths
-
Algorithm learns k-halfspace polyhedra with margin in near-optimal time
Tight Bounds for Learning Polyhedra with a Margin
-
Registers achieve log P latency despite contention
Fast Concurrent Primitives Despite Contention
-
Pinwheel problem proven NP-hard
NP-Hardness and a PTAS for the Pinwheel Problem
-
Low-dim Max-Cut SDP rounding exceeds 0.87856 ratio
Max Cut with Small-Dimensional SDP Solutions
-
Minecraft blocks let students manipulate graph algorithms
Block-Based Pathfinding: A Minecraft System for Visualizing Graph Algorithms
-
Group isomorphism for key families lands in AC³
Parallel Algorithms for Group Isomorphism via Code Equivalence
-
Dynamic algorithm keeps loop nesting forests current in flow graphs
Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs
-
Swapping argument cuts Lawler-Moore dependence to p_max squared
Lawler-Moore Speedups via Additive Combinatorics
-
Acyclicity testing needs tilde-Omega(n^{2/3}) queries
Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
-
Exact influence spread computed linearly for bounded-pathwidth graphs
Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs
-
Deterministic ratio for generalized TCP ack is Theta(log n)
Online TCP Acknowledgment under General Delays
-
Algorithm matches conjectured O(sqrt(d)) Steinitz bound
Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
-
Bounded alphabets keep RMQ encodings near-optimal in 1D
Encodings for Range Minimum Queries over Bounded Alphabets
-
Faster algorithms check (k,ℓ)-sparsity in subquadratic time
Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
-
Quickselect worst-case limit S has tail rate t log t + O(t log log t)
The Distributional Tail of Worst-Case Quickselect
-
Modified payment rule lifts auto-bidding PoA above the limit of 2
Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising
-
Dynamic LCE queries run in constant parallel time
Longest Common Extension of a Dynamic String in Parallel Constant Time
-
Linear preprocessing enables optimal sorting under partial orders
Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps
-
VC-bounded graphs allow εn² GED approximation in n^{O(d/ε²)} time
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
-
Skyline extraction alone drives multi-criteria graph search
Skyline-First Traversal as a Control Mechanism for Multi-Criteria Graph Search
-
Greedy algorithm reaches 0.4-approx for identical submodular max-min
Submodular Max-Min Allocation under Identical Valuations
-
This paper develops a framework to maintain a breadth-first spanning tree and ordering in…
Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
-
0-1 edge weights for distinct vertex sums are hard by feedback vertex set
The Parameterized Complexity of Vertex-Coloring Edge-Weighting
-
Tighter bound accelerates Ollivier-Ricci curvature on graphs
A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature
-
SDP relaxation recovers accurate BME phylogenies
Phylogenetic Inference under the Balanced Minimum Evolution Criterion via Semidefinite Programming
-
Classical algorithms match short-path quantum speed for CSPs
Dequantizing Short-Path Quantum Algorithms
-
Algorithm achieves constant approximation for uniform decision trees
Constant-Factor Approximation for the Uniform Decision Tree
-
Glauber dynamics mixes in O(n log n) for colorings with (1+δ)Δ colors
Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
-
Traffic distributions determine GFOM dynamics on deterministic matrices
Universality of first-order methods on random and deterministic matrices
-
Faster (1-ε) approx for linear matroid intersection in Õ(nnz + r^ω)
Faster Approximate Linear Matroid Intersection
-
Sparse FHE matmul on GPUs runs up to 3x faster than CPU
GPU Acceleration of Sparse Fully Homomorphic Encrypted DNNs
-
Sparse graphs enable exact clustering of millions of geographic points
Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
-
Surrogate enables exact single-variable comparisons from paid evaluations
Limited Perfect Monotonical Surrogates constructed using low-cost recursive linkage discovery with guaranteed output
-
Bicriteria LP gives O(log m/log log m) approx for parallel min-sum cover
Min-Sum Set Cover on Parallel Machines
-
Wavelet forests add select support with minimal space overhead
Wavelet Forests Revisited
-
Algorithm finds properly colored trees of size 2δ^c +1
Above-Guarantee Algorithm for Properly Colored Spanning Trees
-
Fat-minor-free graphs admit coarsely small balanced separators
Coarse Balanced Separators in Fat-Minor-Free Graphs
-
Algorithm builds custom molecular cages by linking binding patterns
Computational Generation of Substrate-Specific Molecular Cages
-
Sparse pinnings suffice for entropic independence with 1/c loss
Entropic independence via sparse localization
-
Diffusion samplers need Ω(√d) score queries
Query Lower Bounds for Diffusion Sampling
-
O(n^3 log n) algorithm for max independent sets of convex-position disks
Maximum Independent Sets in Disk Graphs with Disks in Convex Position
-
Private coins drop out of DP distribution proofs at moderate privacy
Differentially Private Verification of Distribution Properties
-
Two algorithms approximate temporal star covers with ratio Δ-1
New Approximations for Temporal Vertex Cover on Always Star Temporal Graphs
-
Batch processing speeds customizable route queries
Optimized Customizable Route Planning in Large Road Networks with Batch Processing
-
Glauber mixes polynomially at uniqueness threshold for antiferromagnetic spins
Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for Swendsen-Wang Dynamics