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!
Conversation
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
This Tweet was deleted by the Tweet author. Learn more
This Tweet was deleted by the Tweet author. Learn more
I think I'm confused here. Quick googling suggests that tic tacs are, like, small turns on a skateboard? What's the connection to repeating a skateboard trick?
This Tweet was deleted by the Tweet author. Learn more
Ahhhh, so you might tictac because you were unsteady on the landing or something like that. Got it! (Shows what I know about skateboarding...)
This is actually pretty nice, since the outcome is probably a significant advance in skateboarding skills?
This Tweet was deleted by the Tweet author. Learn more
Thanks! This is a fun example; the more I think about it the more the psychology feels like it's similar.