archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 9
-
Noisy k-XOR recovered above n^{k/2}/(D^{k/2-1} δ²) threshold
Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
-
DP mechanism optimizes fairness and welfare for natural data
Tradeoffs in Privacy, Welfare, and Fairness for Facility Location
-
Replicable problems compose with linear total samples
Replicable Composition
-
Min-2-Lin(Z_m) FPT-approximable within ω(m) factor
Optimal FPT-Approximability for Modular Linear Equations
-
Max-Cut stays hard to approximate on 3-colorable graphs
On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
-
OSI sketches fail to give relative-error guarantees
Oblivious Subspace Injection Is Not Enough for Relative Error
-
Discrepancy bounds give faster algorithms for k-constraint ILPs
Algorithms for Standard-form ILP Problems via Koml\'os' Discrepancy Setting
-
Constant-factor packing for balanced star districts
Packing Compact Subgraphs with Applications to Districting
-
Live demos cut algorithm runtimes from years to seconds
Speed Thrills: Visceral Demonstrations That Get Students Excited About Efficient Algorithms
-
Linear space required for single-pass Max-CSP approximation under LP gaps
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
-
Privacy lets algorithms generate any countable language set in the limit
Differentially Private Language Generation and Identification in the Limit
-
Quasi-local Lindbladian mixes Gibbs states in log time with arbitrary fields
Rapid mixing for high-temperature Gibbs states with arbitrary external fields
-
New algorithm computes WEFX and fPO for bivalued goods
Revisiting Fair and Efficient Allocations for Bivalued Goods
-
Color coding counts hypergraphlets faster on (α,β)-nice hypergraphs
Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It
-
Online algorithm admits PCN transactions within O(log B) of optimal
Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
-
Online algorithm admits PCN transactions with O(log B) ratio
Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
-
SPQR-trees yield linear-time detection of snarls and ultrabubbles
Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework
-
Quantum unidirectional tests need n to a power less than 1/2 queries
Quantum Property Testing for Bounded-Degree Directed Graphs
-
Bounded hyperedge contributions yield continuous hypergraph density layers
Density Decomposition on Hypergraphs
-
Batch algorithm updates maximal independent set in O(b log^3 n) work
Parallel Batch-Dynamic Maximal Independent Set
-
State certification hits optimal rates at d squared entanglement
Optimal Quantum State Testing Even with Limited Entanglement
-
Approximate DP matches non-private error rates for language ID and generation
On the Price of Privacy for Language Identification and Generation
-
Polymorphism minion alone decides CSP solvability by consistency hierarchies
Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
-
Quasipoly algorithms learn AC0 from mixing graphical models
Learning $\mathsf{AC}^0$ Under Graphical Models
-
Iterative rounding yields (3^p +1)/2 +ε approx for k-clustering
$k$-Clustering via Iterative Randomized Rounding
-
Quantum state certification uses O(d²/2^{n_q}ε²) samples with n_q-qubit channels
Distributed Quantum Property Testing with Communication Constraints
-
Polynomial-time algorithm finds optimal Thiele committees for interval voters
Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences
-
TSP algorithm achieves space-time product 3.7493^N
Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
-
TSP tradeoff improved to ST below 3.572
Improved space-time tradeoff for TSP via extremal set systems
-
k-juntas and sparse polynomials testable with O(1/ε) queries
Classes Testable with $O(1/\epsilon)$ Queries for Small $\epsilon$ Independent of the Number of Variables
-
Maintain random colorings in dynamic graphs against adaptive foes
Maintaining Random Assignments under Adversarial Dynamics
-
TDDs generalize OBDDs for FPT-size low-treewidth CNFs
A canonical generalization of OBDD
-
k-Inversion is FPT on block graphs
Parameterized algorithms for $k$-Inversion
-
New RECORD solver speeds up hard knapsack problems
Solving Hard Instances from Knapsack and Bounded Knapsack Problems: A new state-of-the-art solver
-
Polynomial algorithms solve AI and ANI bin packing classes
Polynomial and Pseudopolynomial Algorithms for Two Classes of Bin Packing Instances
-
Quotas make dominating set W[1]-hard on degeneracy-2 graphs
Dominating Set with Quotas: Balancing Coverage and Constraints
-
Nonconvex contest objectives still admit stepped optimal prizes
Optimal Contest Beyond Convexity
-
Sparse DAGs approximate distances and flows in any digraph
DAG Projections: Reducing Distance and Flow Problems to DAGs
-
Reordering cuts sparse matrix diagonals by 5.5 times
Packing Entries to Diagonals for Homomorphic Sparse-Matrix Vector Multiplication
-
Reduction turns subset balancing into one infinity-norm SVP instance
Subset Balancing and Generalized Subset Sum via Lattices
-
Poly-time algorithm finds small subspace covering low-doubling sets
An algorithmic Polynomial Freiman-Ruzsa theorem
-
Testability in p-degenerate graphs requires non-fragmentable forbidden structures
A characterization of one-sided error testable graph properties in bounded degeneracy graphs
-
Every string gets O(χ(w)) representation via substring equations
String Representation in Suffixient Set Size Space
-
Reinforcement makes quantum search scale as ln D
Noise tolerance via reinforcement in the quantum search problem
-
SVD recovers nearest neighbors from noisy data up to σ ~ k^{-1/4}
SVD Provably Denoises Nearest Neighbor Data
-
Sinkhorn-Knopp converges in O(log n
On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport
-
Algorithms color matroid intersections with ratios only depending on k
Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
-
Directed flow-cut gap at most n to the 1/3 power
Improved Upper Bounds for the Directed Flow-Cut Gap
-
Real instances reveal which dynamic greedy set cover algorithms win
Engineering Algorithms for Dynamic Greedy Set Cover
-
Private signals beat public ones in unreliable pricing
Optimal Pricing with Unreliable Signals