archive
Every paper Pith has read. Search by title, abstract, or pith.
390 papers in cs.DS · page 1
-
Hybrid sketches match best space bounds for dynamic graph connectivity
Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
-
Min-1-planarity testing is NP-hard
Min-1-Planarity is NP-Hard
-
LP rounding yields (1+2/e) approx for weighted segment hitting
Hitting Axis-Parallel Segments with Weighted Points
-
Branch-width of matrix-represented matroids decided in O(n² + n^ω) time
Branch-width of represented matroids in matrix multiplication time
-
zSort introduces an adaptive sorting algorithm using z-score partitioning to deliver…
zSort: Stable Distribution Sort using Z-Score Partitioning
-
Random order cuts passes for matroid submodular maximization
Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
-
Sparsifier keeps expected matching size with local k-edge budget
Stochastic Matching via Local Sparsification
-
Score matching yields polynomial sample bounds for polynomial families
Finite Sample Bounds for Learning with Score Matching
-
O(n log h) prep yields O(1) leaf-to-ancestor min queries
Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
-
Parity-SAT algorithms break 2^m barrier for bounded occurrences
New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
-
Regional networks cut fulfillment delays
Improved Speed via Regional Fulfillment
-
Symmetric Boolean CSP non-redundancy classified up to O(n^3)
Non-Redundancy of Low-Arity Symmetric Boolean CSPs
-
Valiant learnability equals poly-size query compression
What is Learnable in Valiant's Theory of the Learnable?
-
Dithered Hadamard matches dense rotation quantization error
Provable Quantization with Randomized Hadamard Transform
-
Min-max optimization needs exponentially many queries
Min-Max Optimization Requires Exponentially Many Queries
-
O(n^{3/2}) subgraph yields 2-approx arborescences after one fault
Low-Cost Arborescence Under Edge Faults
-
fcBK algorithm cuts min-cut time to O(m|C|)
Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm
-
Singleton Arc Consistency tightens MAP-MRF relaxations
Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency
-
Correlation Clustering gets poly kernels from bounded fuzzy degeneracy
Clustering with Locally Bounded Ignorance
-
Twin cover bounds conflict-free vertex colors to chi plus t
Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
-
Approx matching and vertex cover solved in O(log n / log² log n) rounds
Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
-
Graph doubling maps ultrabubbles to weak superbubbles in linear time
The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles
-
Electricity fairness reduced to k-times bin packing
Time and Supply Fairness in Electricity Distribution using $k$-times bin packing
-
Thin trees work for near-min cuts in k-connected graphs
Thin Trees for Near Minimum Cuts
-
Tight query bounds set for non-Hermitian QSP simulation
Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing
-
Sampler matches smooth-case rate for composite log-concave densities
A proximal gradient algorithm for composite log-concave sampling
-
BFS width plus few backward arcs yields FPT for PAFP
Layer-Based Width for PAFP
-
Bivariate QSP gives optimal simulation of non-Hermitian Hamiltonians
Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing
-
Surrogate collapses frontier to budget and size for polynomial allocation
Adaptive Multi-Round Allocation with Stochastic Arrivals
-
Ulam similarity admits O(n/sqrt(log n)) LSH distortion
On the LSH Distortion of Ulam and Cayley Similarities
-
k-path temporal graphs allow FPT reachability via label shifts
Maximizing Reachability via Shifting of Temporal Paths
-
Vertex connectivity augmentation is FPT in λ and k
Connectivity augmentation is fixed-parameter tractable
-
Diffusion reward alignment reduces to linear tilts or proximal oracles
The tractability landscape of diffusion alignment: regularization, rewards, and computational primitives
-
k-d trees reduce nearest neighbor search to random guessing in high dimensions
Performance bounds for nearest neighbor search with k-d trees
-
Generalized doubling gives optimal O(2^k) ratio for k-set chasing
Chasing Small Sets Optimally Against Adaptive Adversaries
-
Modularity shows overlap gap on stochastic block model
The stochastic block model has the overlap graph property for modularity
-
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
-
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