Computational Complexity

concepts · 11 notes linked

Related: Scott Aaronson · Quantum Computing · Algorithm Design · Matrix Multiplication · Algorithms · Finite Automata · Theory Of Computation · Formal Languages

Notes

• A New Algorithm Makes It Faster to Find the Shortest Paths — New algorithm breaks 40-year sorting barrier for shortest-path problems
• Algorithms Illuminated Omnibus Edition (September 2022) — Tim Roughgarden's self-published algorithms textbook series omnibus edition
• Computer Scientists Inch Closer to Major Algorithmic Goal | Quanta Magazine — New algorithm improves group isomorphism speed for hardest p-group class
• How Randomness Improves Algorithms | Quanta Magazine — Why randomness makes hard algorithmic problems tractable
• Matrix multiplication - Wikipedia — Definition, properties, and complexity of matrix multiplication
• New Breakthrough Brings Matrix Multiplication Closer to Ideal | Quanta Magazine — New technique lowers matrix multiplication exponent omega, biggest gain in 14 years
• PHYS771 Quantum Computing Since Democritus — Scott Aaronson course connecting quantum computing to broader intellectual problems
• Scott Aaronson on Philosophical Progress - Machine Intelligence Research Institute — How theoretical CS makes progress on big philosophical questions
• Scott in Rio — 1st lecture — Scott Aaronson lecture on complexity theory foundations and Extended Church-Turing thesis
• The Lawlessness of Large Numbers — Finite Ramsey theory computation far harder than asymptotic bounds
• What is the enlightenment I'm supposed to attain after studying finite automata? — Purpose of finite automata in theory of computation curriculum