Deterministic factorization of constant-depth algebraic circuits in subexponential time
FOCS 2025
Deterministic factorization of constant-depth algebraic circuits in subexponential time
16:52
Breaking a Long-Standing Barrier: 2-ε Approximation for Steiner Forest
FOCS 2025
Breaking a Long-Standing Barrier: 2-ε Approximation for Steiner Forest
19:56
Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
FOCS 2025
Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
25:55
Optimal Smoothed Analysis of the Simplex Method
FOCS 2025
Optimal Smoothed Analysis of the Simplex Method
17:38
Adaptivity Gaps for Stochastic Probing with Subadditive Functions
FOCS 2025
Adaptivity Gaps for Stochastic Probing with Subadditive Functions
19:41
Overcomplete Tensor Decomposition via Koszul-Young Flattenings
FOCS 2025
Overcomplete Tensor Decomposition via Koszul-Young Flattenings
24:56
Exponential improvements to the average-case hardness of BosonSampling
FOCS 2025
Exponential improvements to the average-case hardness of BosonSampling
21:19
Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
FOCS 2025
Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
18:53
An Improved Greedy Approximation for (Metric) $k$-Means
FOCS 2025
An Improved Greedy Approximation for (Metric) $k$-Means
21:14
Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations
FOCS 2025
Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations
17:31
On the Impossibility of SNARGs with Short CRS
FOCS 2025
On the Impossibility of SNARGs with Short CRS
17:02
High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich
FOCS 2025
High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich
20:47
How Global Calibration Strengthens Multiaccuracy
FOCS 2025
How Global Calibration Strengthens Multiaccuracy
25:27
Computational-Statistical Tradeoffs from NP-hardness
FOCS 2025
Computational-Statistical Tradeoffs from NP-hardness
17:42
A distillation–teleportation protocol for fault-tolerant QRAM
FOCS 2025
A distillation–teleportation protocol for fault-tolerant QRAM
24:39
Computing the Polytope Diameter is Even Harder than NP-hard
FOCS 2025
Computing the Polytope Diameter is Even Harder than NP-hard
27:40
Shortest Paths on Convex Polyhedral Surfaces
FOCS 2025
Shortest Paths on Convex Polyhedral Surfaces
21:25
Instance-Optimal Uniformity Testing and Tracking
FOCS 2025
Instance-Optimal Uniformity Testing and Tracking
19:12
Quasipolynomial bounds for the corners theorem
FOCS 2025
Quasipolynomial bounds for the corners theorem
18:45
A Little Clairvoyance Is All You Need
FOCS 2025
A Little Clairvoyance Is All You Need
23:05
Adversarially robust quantum state learning and testing
FOCS 2025
Adversarially robust quantum state learning and testing
25:56
The Proof Analysis Problem
FOCS 2025
The Proof Analysis Problem
21:33
Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade
FOCS 2025
Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade
24:09
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
FOCS 2025
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
19:42
Robust Learning of Multi-index Models via Iterative Subspace Approximation
FOCS 2025
Robust Learning of Multi-index Models via Iterative Subspace Approximation
16:48
Edge-weighted Matching in the Dark
FOCS 2025
Edge-weighted Matching in the Dark
17:23
Efficiently Batching Unambiguous Interactive Proofs
FOCS 2025
Efficiently Batching Unambiguous Interactive Proofs
20:24
Distributed Triangle Detection is Hard in Few Rounds
FOCS 2025
Distributed Triangle Detection is Hard in Few Rounds
25:02
Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics
FOCS 2025
Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics
16:36
Lower Bounds for Non-adaptive Local Computation Algorithms
FOCS 2025
Lower Bounds for Non-adaptive Local Computation Algorithms
20:56
Faster logconcave sampling from a cold start in high dimension
FOCS 2025
Faster logconcave sampling from a cold start in high dimension
37:36
Dynamic Treewidth in Logarithmic Time
FOCS 2025
Dynamic Treewidth in Logarithmic Time
23:58
The Power of Recursive Embeddings for $\ell_p$ Metrics
FOCS 2025
The Power of Recursive Embeddings for $\ell_p$ Metrics
23:32
Optimal 4-Approximation for the Correlated Pandora’s Problem
FOCS 2025
Optimal 4-Approximation for the Correlated Pandora’s Problem
17:28
Weighted k-Path and Other Problems in Almost O*(2^k) Deterministic Time
FOCS 2025
Weighted k-Path and Other Problems in Almost O*(2^k) Deterministic Time
30:01