36 ms·

Not to sound snarky, but is there any example where theoretical computer science has actually been useful? The results are often like "Here is a proof this will

Not to sound snarky, but is there any example where theoretical computer science has actually been useful? The results are often like "Here is a proof this will be slow if you scale it up enough" -- "Yeah we knew that for 20 years, it doesn't matter"

fragmede 3y ago
Anything at scale. Anything that uses a database. Anything that uses anything smarter than bubblesort to organize results. Anything that uses a tree (or a trie) internally to represent the data and make some sort of order from it. CS isn't just about "hey this thing is slower than this thing", it's also about making things possible in the first place. If you've used Google (or Facebook or Microsoft or Netflix), they're only possible due to deep computer science work. Which videos gets chosen to be stored on the edge cache? Computer science algorithm.
- cubefox 3y ago
  I'm not sure how true this is. A lot of "algorithms" can be tested by using them or by running simulations for reasonable input ranges.
  - bawolff 3y ago
    Well first off, i think there is an argument that creating & simulating algorithms is CS stuff anyways. Second its often (not always) a lot more work to test scalability with benchmarks than it is to theoretically analyze. Especially because people are often worried about both average case and worst case. The input that takes down your site is not the one you expect, and simulating realistic load is difficult. It can also be pretty hard to compare benchmarks. You probably dont want to test every algorithm known to man yourself, but two separate benchmarks on diff hardware and diff conditions cannot be reasonably compared. More abstract analysis can (to an extent anyways)
  - plonk 3y ago
    Don't a lot of these algorithms come from TCS researchers themselves? They may publish about complexity but if that gives some people a better understanding of algorithms and leads to better ones being invented, it's a win.
  - layer8 3y ago
    You wouldn’t come up with the high-permorming algorithms without understanding why they would be high-performing in the first place.
    - cubefox 3y ago
      Well, this did happen in machine learning. There was a theoretical argument that neural networks "should" terribly overfit according to statistical learning theory, since they have very large VC dimension, but they don't. Practice did race way ahead of theory in AI. Another example is the Chinchilla scaling law, which was discovered empirically instead of being derived from first principles.
      - plonk 3y ago
        That's different from complexity though. We actually understand why some algorithms have better complexity and results than others, while we mostly have no idea how intelligence works or even how to define it.
  - fragmede 3y ago
    Now that I've had a chance to think about it, it's not even "at scale". Your smartphone, which makes liberal use of sqlite databases uses a tree data structure to organize and index the information in the db files. When you turn on the screen to your phone or laptop, and see a bunch of icons laid out, it's thanks to computer science algorithm work that you're not waiting minutes or days for all the icons to get loaded from storage organized with a filesystem smarter than FAT, arranged how you like them, and displayed to a screen with millions of pixels. to a screen that
dilawar 3y ago
I liked a few results. . For example, smooth analysis by Spielman showed why so many algorithms works very well in practice even though their worst case complexity is terrible e.g. simplex method. Second, concave-convex optimization shows that you will definitely reach closer to global optimum at each iteration. I guess its comforting to know a reason algo behave the way they do. Sampling theorem is also case in point. Also compressed sensing. Information theory will tell you there is no point trying any harder at compression when you reached epsilon closer to the theoretical limit.
bawolff 3y ago
An obvious one that comes to mind - this problem is np-complete so pragmatically i can stop looking for a fast algo.
- jdthedisciple 3y ago
  Or resort to a SAT solver right away.
nottorp 3y ago
It tends to not matter until it suddenly does and bites your behind. What was that game that took forever to start up because the code for parsing the config files was accidentally quadratic or exponential? Edit: also, the standard library of any programming language tends to have quite a bit of theoretical computer science inside.
- Adverblessly 3y ago
  You're thinking of GTA Online, from a quick DDG search: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/ https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
- fragmede 3y ago
  If you haven't seen it, Accidentally Quadratic has a tumblr documenting those kinds of things. https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/
  - nottorp 3y ago
    Hah, I just realized they host a text blog on ... tumblr. Thought that site was for random images.
pravus 3y ago
> is there any example where theoretical computer science has actually been useful? Anything requiring extremely optimized algorithms will generally start in academia and work its way outward as the techniques are adopted in commercial software. Sorting and compression algorithms are two examples that come to mind. Even games development which has a history of non-academic roots now borrows heavily from academic research to refine things like culling algorithms or optimized computational methods for specialized physics calculations.
- cubefox 3y ago
  Ah yes, I heard somewhere that Brian Karis at Epic was partially relying on prior work by an academic when he developed virtualized geometry for Unreal Engine 5. (I can't remember the name of the researcher though.)

fragmede 3y ago

Anything at scale. Anything that uses a database. Anything that uses anything smarter than bubblesort to organize results. Anything that uses a tree (or a trie) internally to represent the data and make some sort of order from it. CS isn't just about "hey this thing is slower than this thing", it's also about making things possible in the first place. If you've used Google (or Facebook or Microsoft or Netflix), they're only possible due to deep computer science work. Which videos gets chosen to be stored on the edge cache? Computer science algorithm.

cubefox 3y ago
I'm not sure how true this is. A lot of "algorithms" can be tested by using them or by running simulations for reasonable input ranges.
- bawolff 3y ago
  Well first off, i think there is an argument that creating & simulating algorithms is CS stuff anyways. Second its often (not always) a lot more work to test scalability with benchmarks than it is to theoretically analyze. Especially because people are often worried about both average case and worst case. The input that takes down your site is not the one you expect, and simulating realistic load is difficult. It can also be pretty hard to compare benchmarks. You probably dont want to test every algorithm known to man yourself, but two separate benchmarks on diff hardware and diff conditions cannot be reasonably compared. More abstract analysis can (to an extent anyways)
- plonk 3y ago
  Don't a lot of these algorithms come from TCS researchers themselves? They may publish about complexity but if that gives some people a better understanding of algorithms and leads to better ones being invented, it's a win.
- layer8 3y ago
  You wouldn’t come up with the high-permorming algorithms without understanding why they would be high-performing in the first place.
  - cubefox 3y ago
    Well, this did happen in machine learning. There was a theoretical argument that neural networks "should" terribly overfit according to statistical learning theory, since they have very large VC dimension, but they don't. Practice did race way ahead of theory in AI. Another example is the Chinchilla scaling law, which was discovered empirically instead of being derived from first principles.
    - plonk 3y ago
      That's different from complexity though. We actually understand why some algorithms have better complexity and results than others, while we mostly have no idea how intelligence works or even how to define it.
- fragmede 3y ago
  Now that I've had a chance to think about it, it's not even "at scale". Your smartphone, which makes liberal use of sqlite databases uses a tree data structure to organize and index the information in the db files. When you turn on the screen to your phone or laptop, and see a bunch of icons laid out, it's thanks to computer science algorithm work that you're not waiting minutes or days for all the icons to get loaded from storage organized with a filesystem smarter than FAT, arranged how you like them, and displayed to a screen with millions of pixels. to a screen that

dilawar 3y ago

I liked a few results. . For example, smooth analysis by Spielman showed why so many algorithms works very well in practice even though their worst case complexity is terrible e.g. simplex method. Second, concave-convex optimization shows that you will definitely reach closer to global optimum at each iteration. I guess its comforting to know a reason algo behave the way they do. Sampling theorem is also case in point. Also compressed sensing. Information theory will tell you there is no point trying any harder at compression when you reached epsilon closer to the theoretical limit.

bawolff 3y ago

An obvious one that comes to mind - this problem is np-complete so pragmatically i can stop looking for a fast algo.

jdthedisciple 3y ago
Or resort to a SAT solver right away.

nottorp 3y ago

It tends to not matter until it suddenly does and bites your behind. What was that game that took forever to start up because the code for parsing the config files was accidentally quadratic or exponential? Edit: also, the standard library of any programming language tends to have quite a bit of theoretical computer science inside.

Adverblessly 3y ago
You're thinking of GTA Online, from a quick DDG search: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/ https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
fragmede 3y ago
If you haven't seen it, Accidentally Quadratic has a tumblr documenting those kinds of things. https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/
- nottorp 3y ago
  Hah, I just realized they host a text blog on ... tumblr. Thought that site was for random images.

pravus 3y ago

> is there any example where theoretical computer science has actually been useful? Anything requiring extremely optimized algorithms will generally start in academia and work its way outward as the techniques are adopted in commercial software. Sorting and compression algorithms are two examples that come to mind. Even games development which has a history of non-academic roots now borrows heavily from academic research to refine things like culling algorithms or optimized computational methods for specialized physics calculations.

cubefox 3y ago
Ah yes, I heard somewhere that Brian Karis at Epic was partially relying on prior work by an academic when he developed virtualized geometry for Unreal Engine 5. (I can't remember the name of the researcher though.)