IdeaWell

Project ideas from Hacker News discussions.

Subquadratic 3SUM and Subcubic APSP

Original Article

Hacker News Discussion

📝 Discussion Summary (Click to expand)

1. Theoretical surprise – breaking long‑standing conjectures
Commenters were stunned that an algorithm could beat the (n^2) barrier for 3SUM, APSP and Exact Triangle, problems that were widely believed to require quadratic time.

“Nobody thought this was possible. … 3sum hard was colloquially considered to be ≥ n². It's an absolutely unbelievable result! … the result itself is extremely surprising!” – wrsh07

“3SUM is (was?) one of the key conjectures in fine‑grained complexity … most did not think a subquadratic algorithm was possible. Similar for APSP.” – remywang

2. Practical relevance – “galactic algorithm” concerns
Many noted that an exponent improvement from 2 to ≈1.9992 is only asymptotically better and may never be useful on realistic input sizes, echoing the notion of a galactic algorithm.

“A galactic algorithm is an algorithm with record‑breaking theoretical (asymptotic) performance, but which is not used due to practical constraints … https://en.wikipedia.org/wiki/Galactic_algorithm” – itishappy

“Yes because now it opens the door for future algorithms to chip away at that exponent … in the past it may have seemed that an exponent of 2 was the floor.” – blovescoffee

3. AI/LLMs in mathematical discovery – excitement vs. skepticism
The discussion highlighted contrasting views on whether language models should be used for proving theorems versus helping with data‑driven tasks, and whether the mathematical community should embrace AI‑assisted breakthroughs.

“As a former mathematician, I'm kind of over them using the LLM for math. we know it works. I want them pointed at ‘data construction’, like being libraries, theories and experiments.” – vatsachak

“As a non‑mathematician who sometimes works on mathematical problems, I find this really puzzling. Why aren't mathematicians excited about the frontiers being unlocked by AI? The ability to discover more of the mathematical universe more readily?” – jey

🚀 Project Ideas

Generating project ideas…

LeanProofValidator

Summary

  • Automatically translates LLM‑generated math proofs into Lean 4 code and checks them with the Lean proof assistant, giving instant feedback on correctness.
  • Core value proposition: eliminates the manual effort of formalizing AI‑discovered results, accelerating verification and trust in LLM‑assisted mathematics.

Details

Key Value
Target Audience Researchers and mathematicians using LLMs for theorem proving
Core Feature LLM‑to‑Lean translation pipeline + automated Lean 4 proof checking
Tech Stack Python, Lean 4 Docker image, LLM API (Anthropic/OpenAI), FastAPI backend, React UI
Difficulty Medium
Monetization Revenue-ready: subscription per validation credit (e.g., $0.01 per 1k tokens checked)

Notes

  • HN commenters praised Claude’s Lean verification; a tool that automates this would be welcomed by those excited about AI‑assisted math but wary of manual formalization.
  • Enables rapid iteration: generate a conjecture with an LLM, get a Lean proof, and instantly see if it holds, fostering tighter loops between discovery and verification.

AlgoImpactAnalyzer

Summary

  • Provides interactive simulations that estimate the practical crossover size where a theoretically sub‑quadratic algorithm beats classic O(n²) methods, factoring in hidden constants and memory usage.
  • Core value proposition: helps theorists determine whether a “galactic” algorithm (e.g., the new 3SUM breakthrough) has real‑world relevance before investing implementation effort.

Details

Key Value
Target Audience Algorithm designers, complexity theorists, practitioners evaluating novel algorithms
Core Feature Parameter‑driven runtime simulator that plots predicted performance vs. input size for user‑provided algorithms
Tech Stack Python (NumPy, SciPy), JupyterLite/Wasm for in‑browser plots, optional Rust backend for high‑speed kernels
Difficulty Medium
Monetization Hobby (free open‑source tool with optional donation)

Notes

  • Discussion questioned if the new 1.9992 exponent is practically useful; this tool would let users plug in the algorithm’s constants and see the actual break‑even point.
  • Encourages evidence‑based debate on HN about the impact of asymptotic breakthroughs, moving beyond speculation.

LLMResearchHub

Summary

  • A collaborative notebook platform that integrates LLM prompting, code execution, and version‑controlled sharing for math and CS research, with one‑click export to Lean or LaTeX.
  • Core value proposition: streamlines the end‑to‑end workflow from AI‑generated idea to verifiable proof, making teamwork on LLM‑assisted discoveries frictionless.

Details

Key Value
Target Audience Academic researchers, independent scientists, and research groups experimenting with LLMs for theory
Core Feature Real‑time collaborative notebooks with LLM chat, code cells (Python/Lean), and Git‑backed version control
Tech Stack React/TypeScript frontend, Node.js/Express backend, WebSocket sync, PostgreSQL, Lean 4 container service, LLM API
Difficulty High
Monetization Revenue-ready: tiered team plans ($15/user/month for private projects, free tier for public open‑source work)

Notes

  • Commenters expressed both excitement and skepticism about LLMs in math; a hub that captures the full provenance of AI‑generated work would address reproducibility concerns.
  • By enabling easy sharing of LLM‑generated conjectures and their Lean proofs, the platform could become a focal point for future HN discussions on AI‑driven theory.

Read Later