Skip to content
#

derandomization

Star

Here are 2 public repositories matching this topic...

Swapnil-jain / threesum-derand

Star 2

Deterministic 3SUM in O(n^1.995782) and APSP / (min,+) / all-edges Exact Triangle in O(n^2.995943), improving Alman–Vassilevska Williams: proofs, certificates, Lean 4 checks, and a list of closed ideas to avoid duplicate work

algorithms graph-algorithms matrix-multiplication theoretical-computer-science interval-arithmetic formal-verification apsp open-problems fast-matrix-multiplication 3sum complexity-theory mathlib lean4 min-plus-product all-pairs-shortest-paths fine-grained-complexity subquadratic exact-triangle derandomization
  • Updated Oct 11, 2026
  • Lean

Swapnil-jain / subsetsum-derand

Star 1

Deterministic Subset Sum faster than meet-in-the-middle: 2^{0.4986298 n}, derandomising Ye–Li and OpenAI's 2^{0.49n} construction. Proofs, interval certificates, Lean 4 checks, and closed ideas. Preprint, not peer reviewed.

algorithms theoretical-computer-science interval-arithmetic formal-verification meet-in-the-middle knapsack subset-sum open-problems complexity-theory mathlib lean4 fine-grained-complexity derandomization exponential-time-algorithms
  • Updated Oct 11, 2026
  • Lean

Add this topic to your repo

To associate your repository with the derandomization topic, visit your repo's landing page and select "manage topics."

Learn more