An APSP algorithm using detour-vertex predictions achieves O(n^{2.83} + ηn) time by adapting a co-nondeterministic Exact Triangle algorithm to recover from prediction mistakes.
On Approximability of Satisfiable k-CSPs: IV , year =
5 Pith papers cite this work, alongside 2 external citations. Polarity classification is still indexing.
5
Pith papers citing it
2
external citations · external index
citation-role summary
background 1
citation-polarity summary
years
2026 5verdicts
UNVERDICTED 5roles
background 1polarities
background 1representative citing papers
Protocol learns k-local Lindbladians to ε accuracy with Õ(n^{2k}/ε²) samples and projects to valid generators; improves to log n under sparsity assumptions.
For n-qubit stabilizer states the optimal sample complexity of approximate cloning is Θ(n), matching the complexity of learning.
Gives an approximation algorithm for satisfiable instances of generalized linear equation CSPs over finite groups that is optimal for certain S, while the predicate remains approximation resistant on almost-satisfiable instances.
An Õ(Ω(n²)) lower bound for read-once parity branching programs is obtained by reducing to algebraic circuit lower bounds for an explicit function.
citing papers explorer
-
Warm-Starting All-Pairs Shortest Paths with Predictions
An APSP algorithm using detour-vertex predictions achieves O(n^{2.83} + ηn) time by adapting a co-nondeterministic Exact Triangle algorithm to recover from prediction mistakes.
-
Robust Structure Learning of $k$-local Lindbladians
Protocol learns k-local Lindbladians to ε accuracy with Õ(n^{2k}/ε²) samples and projects to valid generators; improves to log n under sparsity assumptions.
-
Cloning is as Hard as Learning for Stabilizer States
For n-qubit stabilizer states the optimal sample complexity of approximate cloning is Θ(n), matching the complexity of learning.
-
Optimal Inapproximability of Generalized Linear Equations over a Finite Group
Gives an approximation algorithm for satisfiable instances of generalized linear equation CSPs over finite groups that is optimal for certain S, while the predicate remains approximation resistant on almost-satisfiable instances.
-
A Lower Bound for Read-Once Parity Branching Programs
An Õ(Ω(n²)) lower bound for read-once parity branching programs is obtained by reducing to algebraic circuit lower bounds for an explicit function.