Vardi revives paper showing hidden constants make FPRAS for matrix permanent infeasible
luislamb · x · 2026-10-28
Moshe Vardi reshares his 2020 arXiv paper with James E. Newman analyzing an MCMC-based FPRAS for the #P-Complete matrix permanent. Their implementation and runtime analysis show the constant factors hidden by big-Oh notation render the algorithm computationally infeasible in practice — a caution before getting excited about sub-exponential algorithms.
More from Research
- Princeton posts its AI alignment and safety seminar talk videos online — HazanPrinceton · 2026-10-28
- Andrew Critch: scientists' groupthink means AI math progress will surprise them more — AndrewCritchPhD · 2026-10-28
- Mitosis Bench: AI agents find only 32.4% of dividing cells in tumor images — yawnxyz · 2026-10-28
- NEJM AI study: LLMs recommend care costing up to 4.5x more than treating physicians — dvir_a · 2026-10-28
- MASS paper: one model plays the whole agent team to bootstrap recursive self-improvement — idanbeck · 2026-10-28
- First ARC Prize Research Summit held at MIT with Wolfram, Stanley and more — GregKamradt · 2026-10-28