archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 1
-
Derivative bound yields linear sampling for regularized classification
Optimal Dimension-Free Sampling for Regularized Classification
-
Partition oracles for minor-free graphs use poly(d/ε) log n bits
Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
-
Quantum sampling algorithm needs just one ancilla qubit
Ancilla-Efficient QSAMPLE Preparation for Reversible Markov Chains
-
Threshold algorithms exceed half welfare in class-fair matching
Beyond the Half-Approximation: Fair and Efficient Online Class Matching
-
Scanwidth makes budgeted PD tractable on networks
Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth
-
Optimal fair top-k aggregator and 2-approx full ranking given
Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking
-
Algorithms keep preemptions constant per job using predictions
Learning-Augmented Online Scheduling with Parsimonious Preemption
-
Entropy testing needs fewer samples than closeness testing
Entropy Equivalence Testing
-
Semi-sample testers resist online erasures for Reed-Muller codes
Optimal Testing of Reed-Muller Codes with an Online Adversary
-
Min-Sum-Radii stays W[1]-hard for k plus cost on bipartite graphs
On the Parameterized Complexity of Min-Sum-Radii
-
Heavy hitter detector enables deeper private random forests
Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees
-
Timed precursor lifts secretary success above 50 percent
The Secretary Problem with a Stochastic Precursor
-
Generalized Dijkstra solves many path problems under one condition
A Coalgebraic Dijkstra Algorithm
-
PSD permanents have optimal deterministic approx e^{(γ+o(1))n}
Optimal $e^{(\gamma+o(1))n}$-Approximation of the Permanent of Positive Semidefinite Matrices
-
Min sum set cover cost at most tau log of hyperedges
Minimum Sum Set Cover: Structures and Algorithm
-
Optimal mean estimators must have sensitivity Omega(eta + sqrt(eta d/n))
Robust Statistical Estimators with Bounded Empirical Sensitivity
-
Randomized cake cutting needs Omega(n log n) queries
An $\Omega(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
-
Linear-time algorithm finds EGZ zero-sum subsequence
Finding a Solution to the Erd\H{o}s-Ginzburg-Ziv Theorem in Linear Time
-
Asymptotic rank of cw_2 drops below 3.931
Asymptotic Rank Speedup Theorems, Revisited
-
Generalized Thresholding Mechanism tests DP mechanisms near-optimally
Near-Optimal Generalized Private Testing
4 Piths -
Presents new structural results and pairwise improper-learning frameworks for…
Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals
-
Integer decompositions solve clock skew exactly without floats
Space-Time Trade-off in Integer Linear Scaling Rounded to the Nearest Integer through Multiplicative and Additive Decomposition
-
Integer decompositions deliver exact nearest-integer scaling
Space-Time Trade-off in Integer Linear Scaling Rounded to the Nearest Integer through Multiplicative and Additive Decomposition
-
Local edge knowledge speeds up distributed matching and covering
Distributed Stochastic Graph Algorithms
-
Dynamic programming computes exact Banzhaf values for kNN
Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification
-
n by n toroidal grid has treewidth exactly 2n-1
Treewidth of the $n \times n$ toroidal grid
-
Sparse preservers keep reachability after two graph failures
Creating Robust and Fair Graph Structures for Connectivity and Clustering
-
Cactus graphs allow O(n^3) circuits for quantum hashing
Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity Graph
-
O(n^5) algorithm for broadcast domination
An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination
-
Bootstrapping any solver yields fair kidney exchange mechanisms
Optimizing for Fairness in Generalized Kidney Exchange: Theory and Computations
-
Block-sphere quantizer lowers MSE and inner-product error
Block-Sphere Vector Quantization
-
One decomposition certifies multiple thresholds in prophet inequality
Threshold Rules for the Classical Prophet Inequality
-
Deterministic methods give single-exponential time for co-path problems
Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
-
O(kl) vertex kernel for exact l-component connectivity
Linear Kernels for $l$-Exact Component Order Connectivity
-
Fixed convex cuts allow poly-time hypercube volume approx
Deterministic Volume Estimation of Truncated Hypercubes
-
Digraph coloring stays hard to approximate even on tournaments
Hardness and Approximation for Coloring Digraphs
-
Planar MDS algorithms lift to genus g with 3α+1 ratio
Meta-Theorems for Cuttable Distributed Problems
-
1-PLS of cost p yields t-PLS of cost p/t up to log n
Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
5 Piths -
First Õ(log^{1.5} n) algorithm for graph label selection
An Approximation Algorithm for Graph Label Selection
-
Linear hashing matches random hashing on second-order max load
A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing
-
Quantum algorithm beats Grover bound using depth-d states
An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
-
Interconnection trees NP-complete to find but fast with few parts
Complexity of Finding and Enumerating Interconnection Trees
-
-
Interference-free morphisms preserve occurrence counts under iteration
On Occurrence-Preserving Morphisms
-
Unique Games admit tolerant testers with sublinear queries
Tolerant Testing for Unique Games
-
Parse indexing selects safe pseudo-MEMs without choosing k
Parse indexing for discarding short pseudo-MEMs safely
-
Parse index picks safe pseudo-MEMs after any filter
Parse indexing for discarding short pseudo-MEMs safely
-
Klein model turns hyperbolic subgradient cuts into exact central cuts
One-Shot Klein Cutting Planes for Lipschitz Geodesically Convex Optimization in Hyperbolic Space
-
Spanning-tree sampling estimates balance rate in uncertain signed graphs
Finding the Balance Rate of Uncertain Signed Graphs
-
L2 CVP distance to log-unit lattice converges to π sqrt(n)/(2 sqrt(6))
Module Lattice Security (Part III): Structured CVP Distance on the Log-Unit Lattice