archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 7
-
Turnstile algorithms on poly-length streams reduce to linear sketches
Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
-
Non-redundancy sets single-pass streaming space for CSPs
Characterizing Streaming Decidability of CSPs via Non-Redundancy
-
Non-redundancy sets single-pass space for CSP satisfiability
Characterizing Streaming Decidability of CSPs via Non-Redundancy
-
The paper gives a simple (2+ε)-approximation algorithm for the knapsack interdiction…
A simple $(2+\epsilon)$-approximation for knapsack interdiction
-
Efficient sampler for hardcore model on bipartite graphs up to λ ≲ 1/√Δ
Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
-
Exact kernel exponent pinned for rainbow-free coloring
Kernelization Bounds for Constrained Coloring
-
The paper introduces an algorithm that generates random graphs with prescribed expected…
Efficient generation of expected-degree graphs via edge-arrivals
-
GNN edge probabilities cut Ford-Fulkerson augmentations
Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability
-
Wildcard LCE techniques yield continuous time-memory tradeoffs for palindromes
On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches
-
Quasipolynomial classical algorithm for high-temp SYK expectations
A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations
-
Local search algorithms for constraints extend to dynamic settings with constant steps per
Dynamic Construction of the Lov\'asz Local Lemma
-
Isabelle/HOL library encodes primal-dual proofs for algorithms
Formal Primal-Dual Algorithm Analysis
-
Linear-time algorithm yields 4-approx binary tree for any input tree
Designing Approximate Binary Trees for Trees
-
Dynamic algorithm maintains O(Δ/lnΔ) coloring in triangle-free graphs
Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
-
Weighted angle sums define a metric on strings at all scales
A weighted angle distance on strings
-
Polynomial-time algorithm for cluster vertex deletion on chordal graphs
Cluster Vertex Deletion on Chordal Graphs
-
One-pass streaming approximates optimal decision tree splits
Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams
-
Blossom VI runs almost linearly on matching instances
Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
-
Greedy routing takes log n steps in 1D insertion graph
Greedy Routing in a Sequentially Grown One-Dimensional Random Graph
-
Bidirectional reduction ties suffix random access to function inversion
Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
-
Quadratic DP finds exact TTP tours on path metrics
Effective Traveling for Metric Instances of the Traveling Thief Problem
-
Reduced component max-leaf bridges clique-width and bandwidth
Moderately beyond clique-width: reduced component max-leaf and related parameters
-
CRT sparse FFT can require quadratic work under common moduli
Safety-Certified CRT Sparse FFT: $\Omega(k^2)$ Lower Bound and $O(N \log N)$ Worst-Case
-
Random walker meeting times on graphs solved in O(N^4) time
Meeting times on graphs in near-cubic time
-
Capacitated Vertex Cover needs k^{Omega(k)} time under ETH
Parameterized Capacitated Vertex Cover Revisited
-
Linear space now suffices for O(sqrt(n/w)) path mode queries
Faster Linear-Space Data Structures for Path Frequency Queries
-
EFX allocations fail for three agents and eight goods
A Counterexample to EFX $n \ge 3$ Agents, $m \ge n + 5$ Items, Submodular Valuations via SAT-Solving
-
SAT solver finds EFX counterexample for three agents and eight goods
A Counterexample to EFX $n \ge 3$ Agents, $m \ge n + 5$ Items, Submodular Valuations via SAT-Solving
-
Tensoring one-coordinate coverings isolates small balanced subgraphs in vector-labeled dig
Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
-
Reentrant flow shops reduce exactly to parallel machines with arrivals
Flow Shop Scheduling with Stochastic Reentry
-
Lazy recursion accelerates surreal arithmetic
Surreal Arithmetic, Lazily
-
ZKP kernels reformulated to run 10x faster on TPUs
Enabling AI ASICs for Zero Knowledge Proof
-
Network caching is FPT parameterized by number of caches
Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches
-
Theta(n) noisy quartets suffice to reconstruct phylogenetic trees
Optimal Phylogenetic Reconstruction from Sampled Quartets
-
Low-degree testing bounds imply recovery hardness via contiguity
Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
-
Negative momentum converges convex-concave min-max problems
Negative Momentum for Convex-Concave Optimization
-
Exact grid-point matching runs in n to the 1.5 power time
Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
-
Flipped indexing delivers 6.5x lower GPU query latency with dynamic updates
FliX: Flipped-Indexing for Scalable GPU Queries and Updates
-
Parallel pruning classifies new orthogonal arrays
Parallelizing the branch-and-bound with isomorphism pruning algorithm for classifying orthogonal arrays
-
Journey planners run up to 4x faster despite delays
Fast and Memory Efficient Multimodal Journey Planning with Delays
-
Delay-aware planners gain 1.9-4.2x speed boost
Fast and Memory Efficient Multimodal Journey Planning with Delays
-
Richardson iteration bounds backward error by 1/k on PSD systems
Towards Universal Convergence of Backward Error in Linear System Solvers
-
4-approx for fair k-center, constants for k-median and k-means
Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
-
2-Visits is NP-complete even with duplicate deadlines
Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
-
Trading algorithm hits tight 3.523 competitive ratio
Online Trading as a Secretary Problem Variant
-
QBF hard for constant-size backdoors to SAT classes
Backdoors for Quantified Boolean Formulas
-
The paper tightens the one-way communication complexity of finding all k-edit occurrences…
The Communication Complexity of Pattern Matching with Edits Revisited
-
Random k-ary chains decompress with e^{c sqrt n} size factor
The decompressed tree size of $k$-ary chains
-
Local reflections suffice for quadratic speedup in quantum search
Quantum Search without Global Diffusion
-
Constant-depth circuits prepare polylog-weight Dicke states
Super-Constant Weight Dicke States in Constant Depth Without Fanout