archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 10
-
Hard-core partition function zero-free up to connective-constant threshold
Zero-Freeness of the Hard-Core Model with Bounded Connective Constant
-
Log n probes certify matroid bases with correlations
Stochastic Function Certification with Correlations
-
TreeEval solved in poly time with almost log space
Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
-
Dominating set needs Ω(log n) locality for O(log Δ) non-signaling approx
Non-Signaling Locality Lower Bounds for Dominating Set
-
Randomized hypotheses cut adversarial error by half
Robust Learning with Optimal Error
-
Drone covers line targets at 1.25 ratio for 45-degree view
Online Drone Coverage of Targets on a Line
-
Minimum recoloring to end p-illusion is NP-hard on bipartite DAGs
Eliminating Illusion in Directed Networks
-
Bucket collector speeds large-k ANN search up to 3.8x
BBC: Improving Large-k Approximate Nearest Neighbor Search with a Bucket-based Result Collector
-
Reappearances lower optimal threshold in secretary problem
Some variations of the secretary problem
-
Exact Matching on bipartite graphs solved in O(n^6) time
Bipartite Exact Matching in P
-
Streaming CSPs need Ω(√n/p) space to beat LP threshold
Near-Optimal Space Lower Bounds for Streaming CSPs
-
No quantum advantage for QAOA yields better classical paint shop algorithm
No quantum advantage implies improved bounds and classical algorithms for the binary paint shop problem
-
PLT cache beats frequency cache on expected inference cost
Probabilistic Language Tries: A Unified Framework for Compression, Decision Policies, and Execution Reuse
-
DynamicLogLog cuts memory 33 percent and removes error spikes in distinct counts
DynamicLogLog: Faster, Smaller, and More Accurate Cardinality Estimation
-
Stable roommates solved in 2^O(k) time when crossing distance is k
Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings
-
Merge-models exactly capture bounded twin-width
On merge-models
-
b-Chromatic number hard on some H-free graphs while tight version is easy
Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
-
Bit tricks extract spaced k-mers at 750 MB per second per core
Fast Iteration of Spaced k-mers
-
Bit operations let spaced k-mers match regular speed
Fast Iteration of Spaced k-mers
-
Linear reducible configs give near-linear 4-coloring of planar graphs
The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring
-
Polynomial algorithm solves Geodetic Set on ditrees
Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
-
Direct procedure computes shortest augmenting path length
Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited
-
Shortest secluded paths solvable in polynomial time on unweighted graphs
On the Complexity of Secluded Path Problems
-
Grothendieck constant lower bound raised by 10^{-26}
A Lower Bound for Grothendieck's Constant
-
Permutation move structure built in optimal O(r) time
Optimal-Time Move Structure Construction
-
Worst-case time bounds derived for interval solvers on uncertain nonlinear systems
Computational Complexity Analysis of Interval Methods in Solving Uncertain Nonlinear Systems
-
Kidney exchange algorithm runs in O*(6.855^t) time
A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
-
Randomized test detects dissipation in quantum evolution with time O(1/epsilon)
Optimal detection of dissipation in Lindbladian dynamics
-
Balanced biclique reconfiguration is PSPACE-complete on bipartite graphs
Biclique Reconfiguration in Bipartite Graphs
-
Random 2-CNF has poly OBDDs outside density interval 0.5-1
The Compilability Thresholds of 2-CNF to OBDD
-
Dynamic counters deliver sublinear error for growing stream sketches
Sublime: Sublinear Error & Space for Unbounded Skewed Streams
-
4/3 gap bound holds for metric TSP up to 14 vertices
Extending Exact Integrality Gap Computations for the Metric TSP
-
Algorithm lists all Eulerian trails in O(m + z_T) time
Optimal Enumeration of Eulerian Trails in Directed Graphs
-
Pruning cuts public transit query times by up to 57 percent
Early Pruning for Public Transport Routing
-
Early pruning cuts public transport queries by up to 57%
Early Pruning for Public Transport Routing
-
Buffer-aware Dijkstra speeds transit routing over 2x
Adapting Dijkstra for Buffers and Unlimited Transfers
-
Dijkstra variant beats RAPTOR on transit networks with buffers
Adapting Dijkstra for Buffers and Unlimited Transfers
-
Induced minor exclusions yield polylog bag bounds in decompositions
Induced Minors and Coarse Tree Decompositions
-
Oblivious DP accurate for exp many steps while adaptive fails after constant
Separating Oblivious and Adaptive Differential Privacy under Continual Observation
-
3x3 matrix multiplication over F2 needs at least 20 multiplications
Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
-
3×3 matrix multiplication over F₂ needs at least 20 bilinear operations
Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
-
Shortest monotone paths on simple polytopes are NP-hard
Finding Short Paths on Simple Polytopes
-
Protocol outsources MSM with 300x faster verification
2G2T: Constant-Size, Statistically Sound MSM Outsourcing
-
Egg dropping threshold computed in O(log N) time
An $\mathcal{O}(\log N)$ Time Algorithm for the Generalized Egg Dropping Problem
-
Classical algorithm approximates SYK thermal expectations at any temperature
SYK thermal expectations are classically easy at any temperature
-
FISTA is asymptotically worse than ISTA for l1-PageRank
Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
-
-
Compiler turns standard online algorithms into prediction-aware versions
Online Algorithms with Unreliable Guidance
-
Low-rank Max-3-Cut solved by checking O(n^{2r-1}) candidates
Exploiting Low-Rank Structure in Max-K-Cut Problems
-
Curvature changes flag critical graph edges
On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)