archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 5
-
Ramanujan hypergraphs route qubits in log N steps
Permutation Routing on Ramanujan Hypergraphs with Applications to Neutral Atom Quantum Architectures
-
O(k^33) kernel for deleting to proper interval graphs or trees
A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees
-
Standard DFS and BFS recognize several graph classes
On the power of standard DFS and BFS
-
Many quantum Hamiltonians sparsify to far fewer terms
Many Hamiltonians Are Sparsifiable
-
Self-referential instances force near-full input scan for dominating set
Solution independence and self-referential instances
-
2-fault replacement paths reduce to single-source ones
Undirected Replacement Paths: Dual Fault Reduces to Single Source
-
Eigenvalue method cuts Monte Carlo paths from 1M to 10
Fast Monte-Carlo
-
Triangulation flip chain mixes in Õ(n²) time
Faster Mixing for Triangulations via Transport Flows
-
Dual HNSW graphs enable fast search for any Lp metric
U-HNSW: An Efficient Graph-based Solution to ANNS Under Universal Lp Metrics
-
The paper gives a linear-time algorithm to find a central vertex in 1/2-hyperbolic graphs…
A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
-
Derandomization yields first poly-time randomized k-server algorithm
Randomized $k$-server in polynomial time
-
Alpha-orderings unify two algorithms for symmetric submodular minimization
A Unified Approach to Minimizing Symmetric Submodular Functions
-
New embedding gives kernel queries tilde O(d + epsilon Delta^2 + 1/epsilon^3)
New Bounds for Kernel Sums via Fast Spherical Embeddings
-
Deterministic maximal matching reaches n^{1/2+o(1)} amortized updates
A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
-
Farthest-point Voronoi speeds rectangle disk queries
Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
-
Near-linear algorithm finds well-spread perfect matchings in cubic graphs
A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
-
Unlearning in offline bandits achieves provable performance after deletion
Unlearning Offline Stochastic Multi-Armed Bandits
-
Minimum span in upward-planar drawings is NP-hard for trees
Upward-Planar Drawings with Bounded Span
-
Perturbed knapsack threshold keeps SOS rank at O(sqrt n log n)
On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
-
Three-layer hashing solves set matching in linear time
Set Parameterized Matching via Multi-Layer Hashing
-
Condensed network equals max flow over time value
Brief announcement: A special case of maximum flow over time with network changes
-
Approximation speeds up only 20% of key algorithms
The Impact of Approximation on Algorithmic Progress
-
Matroid basis costs quadratic queries in size-sensitive model
Matroid Algorithms Under Size-Sensitive Independence Oracles
-
Matrix product states match nondeterministic decision diagrams
From Tensor Networks to Tractable Circuits, and back
-
Dual clique covers let graph algorithms run faster and use less memory
Succinct Graph Representations and Algorithmic Applications
-
Santa Claus needs sqrt n rounds for any approximation
Distributed Santa Claus via Global Rounding
-
Simpler method cuts replacement path covering size to Õ(f L^{f+o(1)})
Simpler and Improved Replacement Path Coverings
-
Optimal Hamiltonian learning works without short-time control
Heisenberg-limited Hamiltonian learning without short-time control
-
Two-graph model splits feasibility from movement in path discovery
Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
-
Lovász swaps reduce Schur-convex spread measures on lattice profiles
Variational and Majorization Principles in Lattice Reduction
-
Polynomial algorithm solves temporal schedule completion
Temporal Routing in Static Networks: The Schedule Completion Problem
-
Poly-time algorithm finds min walks for timed demands in static graphs
Temporal Routing in Static Networks: The Schedule Completion Problem
-
Max-APD taxon subsets found in poly time for scanwidth-2 networks
Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
-
Odd girth threshold unlocks O(n^ε) online coloring for any ε
Online Coloring for Graphs of Large Odd Girth
-
Hypergraph Laplacian systems solved in almost-linear time
Solving Hypergraph Laplacian Systems in Almost-Linear Time
-
56-addition scheme multiplies 3x3 matrices at rank 23
An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication
-
2/3-approx algorithm for equal-capacity bottleneck knapsacks
Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
-
Smallest suffixient set updated in polyloglog time per letter
Smallest suffixient set maintenance in near-real-time
-
Algorithm computes (k+2)-edge components in digraphs in subquadratic time
Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
-
Tighter bound lets ℓ=1/(2eε)
A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm
-
Minimum temporal arcs for requests: n
Designing sparse temporal graphs satisfying connectivity requirements
-
Distance-oracle link yields first deterministic diameter tradeoffs
New Diameter Approximations via Distance Oracle Techniques
-
Algorithm boosts balanced biclique approximation to n/(log n)^3
Improved Approximation Algorithm for Maximum Balanced Biclique
-
Monotone embeddings cut distortion to O(log squared n) for online points
Online Monotone Metric Embeddings
-
Monotone distance decreases yield O(log² n) online HST embeddings
Online Monotone Metric Embeddings
-
O(kn²) program selects optimal diversity subsets on lines
Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases
-
Revenue learners converge for any distribution but at arbitrarily slow rates
On the Learning Curves of Revenue Maximization
-
Quantum channel certification shows strict hierarchy in query costs
Strict Hierarchy for Quantum Channel Certification to Unitary
-
The paper develops differentially private approximation algorithms for positive linear…
Solving Positive Linear Programs with Differential Privacy
-
Emulators stretch by heaviest edges with size O(n^{1+1/k})
Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs