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
You’re unable to view this Tweet because this account owner limits who can view their Tweets. Learn more
Replying to
I'm excited to see how SOSA turns out! I'm mostly not a theorist anymore but I still like to dabble/watch.
Agreed that simplifying constructions is (also) a value endeavour.