archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 11
-
New conditions rule out more pairs from optimal preorders
Partial Optimality in the Preordering Problem
-
S-Hamiltonian cycles NP-complete only for certain even sets
The S-Hamiltonian Cycle Problem
-
Natural privacy filters are free only for totally ordered mechanism families
Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity
-
Poly-time algorithm achieves near-optimal flow-expander overhead
Expander Decomposition with Almost Optimal Overhead
-
Subexponential noise yields poly-log log-concave sampling accuracy
High-accuracy log-concave sampling with stochastic queries
-
Min-max connected multiway cut is hard on treewidth-2 graphs
Min-Max Connected Multiway Cut
-
String index of size O(δ log n/δ) built in one streaming pass
Compressed Index with Construction in Compressed Space
-
Linear-time method tightens RNA designability bounds
Probabilistic RNA Designability via Interpretable Ensemble Approximation and Dynamic Decomposition
-
Neural net learns facility location with provable guarantees
Learning to Approximate Uniform Facility Location via Graph Neural Networks
-
Monoid structure fixes space for out-of-order product
Out-of-Order Membership in Regular Languages
-
Poly-time algorithm recovers regressor from unknown-truncated data
Linear Regression with Unknown Truncation Beyond Gaussian Features
-
Temporal graphs admit linear MSO checking via bounded derivative width
Model checking with temporal graphs and their derivative
-
Binary strings listed with fixed time and fixed extra memory
Gray Codes With Constant Delay and Constant Auxiliary Space
-
Local generators keep update cost constant as system grows
Bounded Local Generator Classes for Deterministic State Evolution
-
Adaptive filter tightens private PCA error on low-coherence matrices
Adaptive Power Iteration Method for Differentially Private PCA
-
Truncation bounds average move query time to optimal
Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations
-
Common subgraph without isolates is NP-hard but FPT by h
Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
-
Polynomial partitioning yields short labels for semialgebraic graphs
Implicit representations via the polynomial method
-
Trade-off gives optimal random access on grammar-compressed strings
Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
-
This paper defines a 'certified' shortcut in directed graphs: for every added edge (u,v)…
Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
-
Local inspection fails to decide dominating sets in random graphs
Self-referential instances of the dominating set problem are irreducible
-
Sparse coverage functions get poly(t,k,log n) discrepancy
Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
-
Shift-tree maintains dynamic edge colorings with tight recourse
Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
-
Average sensitivity converts offline approximations to small-loss online regret
From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
-
Two presorts enable O(n sqrt(log n)) quadtree construction
The Presort Hierarchy for Geometric Problems
-
Hybrid algorithm tightens submodular k-matroid bound to 0.819k
Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
-
FPT (3+ε) approx for fair sum of radii with outliers
FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
-
Weighted sampling approximates makespan in sublinear time
Minimizing Makespan in Sublinear Time via Weighted Random Sampling
-
Maximal tree mining stays hard even at height 2
The Complexity of Maximal/Closed Frequent Tree Mining for Bounded Height Trees
-
M-convex sets yield finite O(d log d) regret for online inverse optimization
Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
-
Bounded TDM-treewidth solves graphic IPs in polynomial time
Totally $\Delta$-Modular Tree Decompositions of Graphic Matrices for Integer Programming
-
Limited capacity forces LLMs to hallucinate non-facts
Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
-
Continuous spectral independence gives spectral gap for Glauber dynamics
Sampling Sphere Packings with Continuum Glauber Dynamics
-
Pathwidth three forces exponential ascents in local search
All ascents exponential from valued constraint graphs of pathwidth three
-
Free expander walks build explicit codes matching GV bound
Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
-
Any stabilizer code can support universal fault-tolerant computation
Stabilizer Code-Generic Universal Fault-Tolerant Quantum Computation
-
Priority queue supports updates and overflow for NIC timers
A Grouped Sorting Queue Supporting Dynamic Updates for Timer Management in High-Speed Network Interface Cards
-
Torus Puzzle solved in O(mn log max(m,n)) rotations
An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle
-
Torus puzzle solved in O(mn log max(m,n)) rotations
An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle
-
Deterministic algorithms match free-probability matrix bounds
Derandomizing Matrix Concentration Inequalities from Free Probability
-
ETH rules out fast approximation for counting permutation patterns
Inapproximability of Counting Permutation Patterns
-
Poly(d,k) algorithm learns heavy-tailed mixtures without separation
Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
-
MDDs speed up signature Gröbner bases via compact monomial diagrams
A data structure for monomial ideals with applications to signature Gr\"obner bases
-
Polynomial-time variance for WMC on structured d-DNNFs
Variance Computation for Weighted Model Counting with Knowledge Compilation Approach
-
Sparse kernels factor forest proximities exactly
Revisiting Forest Proximities via Sparse Leaf-Incidence Kernels
-
Iterative algorithm yields optimal deterministic Lp coresets
Deterministic Coreset for Lp Subspace
-
Deterministic algo finds log-sized guards for near-full area visibility
A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem
-
Gaussian approximation yields fast mixing for Ising models with one negative outlier
Fast mixing in Ising models with a negative spectral outlier via Gaussian approximation
-
GPU data structure speeds hypergraph triad counting up to 473x
ESCHER: Efficient and Scalable Hypergraph Evolution Representation with Application to Triad Counting
-
Two passes achieve near-1/2 Max-DICUT approximation in sublinear space
Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes