#PDF of Scott Aaronson’s new 116-page survey #paper on P=NP. #complexity
on 02017-01-03Adams #paper that #parsing with derivatives has cubic time #complexity
on 02016-06-26more theorems about #complexity of #optimization
on 02016-01-13interesting, the same David Wolpert who just extended Landauer’s bound to arbitrary computation proved an interesting theorem about the computational #complexity of general #optimization problems
on 02016-01-13“Higher type recursion, ramification and polynomial time”, a #paper showing how to build a type system that restricts you to writing polynomial-time programs. #complexity #pdf
on 02015-10-01“#Levenshtein automata can be simple and fast” and useful for finding potential misspellings (like for a #search-engine, with applications given to #Lucene) in a #trie. #Python with #graphviz: 40 lines of code and good (O(max edit distance) supposedly) worst-case #complexity. #smallisbeautiful #algorithms
on 02015-08-15Another #trading #algorithms #paper by the same authors as the 2011 paper: “Efficient market making via convex optimization, and a connection to online learning (2012)”. Talks about Arrow-Debreu #prediction-markets as a market-based probability estimator and draws a connection to online #machine-learning algorithms, and briefly links to computational #complexity results. The reason the authors are interested in automated market-making seems to be that it is needed to make #prediction markets over complex outcome spaces feasibly liquid.
on 02015-08-13#subsetsum #algorithms in O(u √n) for set of size n computing subset for all target numbers t≤u #complexity
on 02015-08-05#Interview with Scott Aaronson by Luke Muehlhauser about quantum physics, philosophy, #computability and #complexity, and so on. #toread
on 02015-08-05