“IDEA — Nonverbal Algorithm Assembly Instructions”
Sándor P. Fekete, Sebastian Moor, and Sebastian Stiller, IDEA, May 24, 2018
“An O(N) Sorting Algorithm: Machine Learning Sorting”
Hanqing Zhao and Yueban Luo, arXiv, May 11, 2018
The authors propose a new method for sorting a gigantic array of arbitrary values in linear time: Select a fixed number (say 1000) values from the array and sort them. Using these values as a training set, train a three-layer neural network to estimate the position in the sorted array that any given value will occupy. Set up an array of buckets equal in size to the original array. Feed each value in the array into the neural network and put it in the bucket corresponding to the network's prediction of the value's position in the sorted array. A linear-time amount of post-processing can now ensure that every value is in a bucket that is within a fixed distance of its position in the sorted array. Apply insertion sort on the almost-sorted values in the array of buckets to build the actual sorted array. Since insertion sort runs in linear time on almost-sorted arrays, the whole process, including the training of the neural network, takes linear time.
I wouldn't have thought of that one.
Next month in arXiv: Adversarial sorting examples.
An attempt to identify and explain the ethical preconditions for replacing social policies with algorithmic models. It's incomplete, but the questions that are included are relevant and salient, and the cautionary tales and links are thought-provoking.
“Math Can't Solve Everything: Questions We Need to Be Asking Before Deciding an Algorithm Is the Answer”
Jamie Williams and Lena Gunn, Deeplinks, Electronic Frontier Foundation, May 7, 2018
“Every Positive Integer Is a Sum of Three Palindromes”
Javier Cilleruelo, Florian Luca, and Lewis Baxter, arXiv, June 17, 2017
The authors provide an algorithm for finding the palindromic addends but don't include any source code. The algorithm works for any integer base greater than or equal to 5.
For decades now, lazy programmers have relied on ever-faster processors and ever-larger memories to avoid learning about subtle but efficient algorithms and fast data structures with intricate invariants. Now the jig is up.
“Death Notice: Moore's Law. 19 April 1965 — 2 January 2018”
Mark Pesce, The Register, January 24, 2018
The computer science behind microprocessor design has therefore found itself making a rapid U-turn as it learns that its optimization techniques can be weaponized. The huge costs and Meltdown and Spectre — which no one can even guess at today — will make chip designers much more conservative in their performance innovations, as they pause to wonder if every one of those innovations could, at some future point, lead to the kind of chaos that has engulfed us all over the last weeks.
One thing has already become clear: in the short term, performance will go backwards. The steady … improvements every software engineer could rely on to make messy code performant can no longer be guaranteed. …
Going forward, the game changes from “cheaper and faster” to “sleeker and wiser.” Software optimizations — despite their Spectre-like risks — will take the lead over the next decades. …
From here on in, we're going to have to work for it.