In the algorithms-y parts of theoretical computer science, we have this activity called log shaving.
The weirdest thing about it is that I can't think of directly analogous activities in other fields that I know well (e.g., programming). Maybe someone has suggestions?
Conversation
For the unfamiliar, log shaving is taking an algorithm that has some ugly (sub-)logarithmic factors in its asymptotic complexity (e.g., time required) and getting rid of them.
Getting an algorithm down from O(n log n (log log n)^2) to just O(n log n) time is classic log shaving.
1
1
The term often has a sort of humorous or even self-deprecating component to it: "I'll submit this paper as soon as I'm done log shaving."
It's not necessarily derisive though: "This paper has some crazy log shaving in it" can be a complement from the right person.
1
I think it's pretty uncontroversial to say that log shaving is usually only appealing to True Theorists(TM). Usually, shaving these small log factors has (at best) no real world impact.
Remember log (log 10^100) ≈ 5. There are fewer than 10^100 atoms in the observable universe.
1
1
Even worse, log shaving usually involves much more complicated techniques. It's not uncommon that the final, fully shaved algorithm is too complicated and slow (for realistic input sizes) to be useful.
But: the techniques involved are often really beautiful!
1
One of the main motivations I've seen for log shaving is meeting a lower bound: we know that an algorithm always requires n log n time, so it's not satisfying to have the best algorithm known (which acts as an upper bound) take O(n log n (log log n)^2) time. 😅
1
In summary, log shaving often*:
- Has little practical impact even on useful problems
- Involves adventures into deep and profound ideas
- Provides marvelous satisfaction by "closing the book" on a problem
* I'm speaking in generalities, exceptions abound, no warranty implied.
1
1
In case you can't tell, log shaving is mostly not to my taste. I can pick up a factor of 5 in all kinds of practical ways: watch the cache! rewrite loops to be friendly to the auto-vectorizer!
Realizing this a big part of realizing that I'm not a True Theorist(TM).
1
2
On the other hand, I've seen all kinds of lovely techniques come out of log shaving endeavors. Simple algorithms are often plain, and a clean-shaven one is often full of deep mathematical connections.
I think that log shaving often meaningfully advances TCS as a field.
2
Does anyone know of activities in other fields that are analogous to log shaving, in the sense that they involve the key factors I mentioned?
Quote Tweet
In summary, log shaving often*:
- Has little practical impact even on useful problems
- Involves adventures into deep and profound ideas
- Provides marvelous satisfaction by "closing the book" on a problem
* I'm speaking in generalities, exceptions abound, no warranty implied.
Show this thread
1
I can't think of examples in non-theory domains that I know well, like programming/software engineering.
I think the closest thing in programming is being an "architecture astronaut", but I've never seen that used in a non-derogatory way. I also don't think it's profound.