Latent Seminar
Search
Search
Dark mode
Light mode
Browse
Tag: cs-DS
37 items with this tag.
Oct 07, 2026
Unique Games and optimal approximation thresholds
cs-CC
cs-DS
Oct 07, 2026
Acceptance probabilities and logarithmic-space derandomization
cs-CC
cs-DS
Oct 07, 2026
Quasipolynomial algorithms for mean-payoff games
cs-CC
cs-DS
Oct 07, 2026
Perfect completeness for two-to-one games
cs-CC
cs-DS
Oct 07, 2026
Independent sets under a three-colorability promise
cs-CC
cs-DS
Oct 07, 2026
Matrix multiplication: square, rectangular, and all-field exponents
cs-CC
cs-DS
Oct 07, 2026
Cubic lower bounds for permanent determinant representations
cs-CC
cs-DS
Oct 07, 2026
Integer multiplication below n log n
cs-CC
cs-DS
Oct 07, 2026
Randomized k-server: competitive ratios and uniform computation
cs-CC
cs-DS
Oct 07, 2026
One-sample matroid prophet inequalities and informed adversaries
cs-CC
cs-DS
Oct 07, 2026
Depth-three circuits beyond the square-root exponent
cs-CC
cs-DS
Oct 07, 2026
Perfect matchings: approximate counting and entropy
cs-CC
cs-DS
Oct 07, 2026
Counting common matroid and integer polymatroid bases
cs-CC
cs-DS
Oct 07, 2026
Contingency tables: exact sampling and relative counting
cs-CC
cs-DS
Oct 07, 2026
Uniform sparsest cut: hardness and semidefinite gaps
cs-CC
cs-DS
Oct 07, 2026
Bin packing: additive error and configuration gaps
cs-CC
cs-DS
Oct 07, 2026
Binary information and Hellinger contraction on the cube
cs-CC
cs-DS
Oct 07, 2026
Exact general-graph matching in almost-linear time
cs-CC
cs-DS
Oct 07, 2026
An almost-linear approximation scheme for edit distance
cs-CC
cs-DS
Oct 07, 2026
Deletion traces: sample lower bounds and uniform reconstruction
cs-CC
cs-DS
Oct 07, 2026
Unit-job scheduling on three identical machines
cs-CC
cs-DS
Oct 07, 2026
Metric k-median: approximation threshold and recovery
cs-CC
cs-DS
Oct 07, 2026
Perfect matching and semidefinite formulation size
cs-CC
cs-DS
Oct 07, 2026
Average sensitivity of polynomial threshold functions
cs-CC
cs-DS
Oct 07, 2026
A factor-two approximation for shortest common superstring
cs-CC
cs-DS
Oct 07, 2026
Exponential state costs for two-way automata
cs-CC
cs-DS
Oct 07, 2026
Exact Fourier transforms below n log n
cs-CC
cs-DS
Oct 07, 2026
Graph switches with prescribed degrees
cs-CC
cs-DS
Oct 07, 2026
A superquadratic sensitivity separation
cs-CC
cs-DS
Oct 07, 2026
The complexity of Weisfeiler–Leman refinement
cs-CC
cs-DS
Oct 07, 2026
Generalized star height at most three
cs-CC
cs-DS
Oct 07, 2026
Homogeneous depth-five matrix products
cs-CC
cs-DS
Oct 07, 2026
A quasilinear PCP theorem for PPAD
cs-CC
cs-DS
Oct 07, 2026
One-tape computation in two-fifths-power space
cs-CC
cs-DS
Oct 07, 2026
Subset Sum: faster time and lower space
cs-CC
cs-DS
Oct 07, 2026
Subpolynomial queries for log-concave sampling
cs-DS
math-PR
Oct 07, 2026
Memory and samples in noiseless Gaussian regression
cs-CC
cs-DS
math-PR