archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 2
-
Branchwidth solved in single-exponential time
Fast and Practical Single-Exponential Algorithms for Branchwidth
-
L1 sandwiching enables quasipolynomial PQ learning for DNFs
Iterative Chow Filtering for Learning with Distribution Shift
-
Star graph embeddings get optimal online ratios of 1.5 and 11/9
Online Graph Embedding in Star Graphs
-
NC algorithms compute EF1 allocations for any constant number of agents
Improved Parallel Algorithms for EF1 Allocations
-
DialSort sorts integers by making the histogram the final ordered list
DialSort: Non-Comparative Integer Sorting via the Self-Indexing Principle: Architecture, Implementation, and Substrate-Aware Analysis
-
A data structure answers c-approximate furthest neighbor queries correctly against…
Adversarially Robust Approximate Furthest Neighbor
2 Piths -
FPT algorithms for broadcast independence via treewidth and diameter
On the parameterized complexity of Broadcast Independence and Broadcast Packing
-
Non-log-concave sampling matches log-concave dimension dependence
Complexity of Non-Log-Concave Sampling in Fisher Information
-
k-edge-deficient temporal graphs explored in O(nk log k) time
Exploration of $k$-edge-deficient temporal graphs in linear time
-
Batching PBWT queries enables constant-time haplotype reports
Faster PBWT prefix-array access via batching
-
Two-drone line-segment inspection is strongly NP-hard
Optimizing Line Segment Inspection with Limited-Range Drones
-
Sampling from demand gives 2-approx for robotaxi placement
The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
-
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
-
Recognizing min-1-planar graphs 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 solved in sub-2^m time for bounded-occurrence formulas
New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
-
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