5 ms·

This is only tangentially related, but one thing that I am still kind of hopeful about is analytic combinatorics will free us from the tyranny of asymptotic ana

by antics 1y ago

This is only tangentially related, but one thing that I am still kind of hopeful about is analytic combinatorics will free us from the tyranny of asymptotic analysis. I suppose this is kind of a hot take, and in some ways less relevant than it was (say) 10 years ago, but I believe the theoretical CS community has spent a lot of time analyzing the performance of various algorithms over the years and kind of pointedly not inventing algorithms which accomplish some result at all, even if it is only known to be computable in a pathologically inefficient way. This means a lot of breakthroughs that could have been TCS breakthroughs have been invented, usually worse, by other communities. I am not the only one who thinks so, here[1] is an obscure talk where Michael Mitzenmacher (a well-known CS theory prof at Harvard) makes more or less this specific complaint. One of the nice things about Flajolet/Sedgewick[2] (mentioned in this post) is that it gives a nice set of combinators for (at least it seems to me, in theory) precisely enumerating how many "steps" an algorithm would take given some input. I optimistically imagine a world where we replace the relatively non-specific asymptotic bounds of an algorithm with a very specific quantification of the work an algorithm will take. And that this in turn would free TCS to focus on things that are more germane to the field as a whole. With that all said I'm open to the argument that TCS has fundamentally changed and this is no longer such a big issue. But perusing the various TCS conferences I sense it isn't. [1]: https://www.youtube.com/watch?v=p3anjSAnKBo https://www.youtube.com/watch?v=p3anjSAnKBo [2]: https://algo.inria.fr/flajolet/Publications/book.pdf https://algo.inria.fr/flajolet/Publications/book.pdf

krick 1y ago
> I optimistically imagine a world where we replace the relatively non-specific asymptotic bounds of an algorithm with a very specific quantification of the work an algorithm will take. My understanding is that it's pretty much how it started, but proved to be impractical. Meaning, we absolutely can quantify the work any algorithm will take, but for that we need to define the architecture first, i.e., to specify what is the unit of work, what are operations available to us. And, sure, we can do that for any given task (and we always could), but it's usually too messy to include that in general discussions about algorithms, not specifically concerned with the architecture.
- antics 1y ago
  Yep, That's exactly why we moved to asymptotic analysis. I was just hoping analytic combinatorics would help us move back to something like this.
qsort 1y ago
I'm not a researcher, so start with the default assumption that I don't know what I'm talking about, but I had the same impression when studying those topics, asymptotic analysis is kind of broken. For example, we assume that arbitrary arithmetic takes constant time. Good. Except that if you take that seriously, then P=PSPACE. So we might say that bit operations on fixed registers are constant time. But nobody does that because then arithmetic is O(lg n) and it's too much trouble to keep track of everything (and if you do, then hashtables aren't O(1) any longer!) If we are more sophisticated we might take a transidchotomous model, but that's really weird and we have results like sorting in less than n lg n time. Not to mention that the mathematical foundations get a bit shaky with more than one variable. I think the hard problem underneath is that it's hard to define a computational model that (a) can be reasoned about and isn't extremely weird, (b) has solid mathematical foundations, (c) is reasonably predictive of real world performance, and (d) is not linked to a specific architecture. Asymptotic analysis is kind of a compromise. It can be formulated in very elementary terms, it makes mathematical sense and if you plot the performance of a sorting algorithm on a chart it kind of looks like the graph of n log n if you squint a bit. Knuth does something similar to what you're suggesting IIRC, albeit without the analytic combinatorics machinery. For some programs he derives a precise expression as a function of the size of input that describes how many operations of each kind the underlying machine will perform. In numerical analysis there is a similar concept, e.g. evaluating a polynomial with Horner has the same asymptotic complexity as the naive method, but we say it's better because it takes exactly the optimal amount of floating point operations (and, in practice, because it uses fused multiply-adds, but that's another story...) A research program along those lines would be certainly fascinating, but the combination of "needs to be reasonably predictive" and "needs to be portable" is a tough nut to crack.
- antics 1y ago
  Yep, I mentioned this elsewhere in the threads—Knuth does do this quite a bit in TAOCP. I think in a lot of ways we've ended up completely full circle, in that we are now counting FLOPs. This time though I think we have very little hope for something as nice and pretty as asymptotics. At least ones that are useful.
- Tainnor 1y ago
PollardsRho 1y ago
I don't think it's controversial to say that asymptotic analysis has flaws: the conclusions you draw from it only hold in the limit of larger inputs, and sometims "larger" means "larger than anything you'd be able to run it on." Perhaps as Moore's law dies we'll be increasingly able to talk more about specific problem sizes in a way that won't become obsolete immediately. I suppose my question is why you think TCS people would do this analysis and development better than non-TCS people. Once you leave the warm cocoon of big-O, the actual practical value of an algorithm depends hugely on specific hardware details. Similarly, once you stop dealing with worst-case or naive average-case complexity, you have to try and define a data distribution relevant for specific real-world problems. My (relatively uninformed) sense is that the skill set required to, say, implement transformer attention customizing to the specific hierarchical memory layout of NVIDIA datacenter GPUs, or evaluate evolutionary optimization algorithms on a specific real-world problem domain, isn't necessarily something you gain in TCS itself. When you can connect theory to the real world, it's fantastic, but my sense is that such connections are often desired and rarely found. At the very least, I'd expect that to often be a response to applied CS and not coming first from TCS: it's observed empirically that the simplex algorithm works well in practice, and then that encourages people to revisit the asymptotic analysis and refine it. I'd worry that TCS work trying to project onto applications from the blackboard would lead to less rigorous presentations and a lot of work that's only good on paper.
- LegionMammal978 1y ago
  Average-case complexity can be a fickle beast. As you say, the simplex algorithm for LP is great in practice, so it's rarely problematic to use. But meanwhile, people also say, "Modern SAT/SMT solvers are great, they can solve huge problems!" Yet when I try using one, I usually run into exponential runtimes very quickly, especially for unsatisfiable instances. Overall, it's annoying to tell whether an NP-hard problem is always really hard, or if ~all practical instances can be solved with a clever heuristic. It doesn't help that most problems receive little attention (e.g., to find solvable special cases) after being labeled NP-hard.
  - aleph_minus_one 1y ago
openasocket 1y ago
> One of the nice things about Flajolet/Sedgewick[2] (mentioned in this post) is that it gives a nice set of combinators for (at least it seems to me, in theory) precisely enumerating how many "steps" an algorithm would take given some input. I optimistically imagine a world where we replace the relatively non-specific asymptotic bounds of an algorithm with a very specific quantification of the work an algorithm will take. And that this in turn would free TCS to focus on things that are more germane to the field as a whole. Check out the Art of Computer Programming, by Knuth. He writes all of the algorithms in a hypothetical machine code called MIX (MMIX in later editions). He does go through algorithmic analysis to the degree you describe, showing exactly how many cycles a particular routine may take to complete, based on different variables. This is actually fairly complex even for simple programs. Consider the simple case of computing the maximum in a list: let current_max := 0 for x in array_of_numbers { if x > current_max { current_max = x; } } return current_max; Anyone can tell you this runs in O(N) time. But exactly how many cycles would this take? Ignoring the architectural details, you would need to know how often the condition "x > current_max" is true. If the list of numbers is in ascending order, this will be true every time, if it is in descending order it will only be true once. The difference in the number of cycles between those two cases is significant. I believe Knuth works through this example, and shows that, for a randomly-ordered array, this would be true around log_2(n) times.
- antics 1y ago
  I actually have read a chunk of the relevant TAOCP, but didn't mention it because the comment was already kind of long. I remarked to a friend the other day that it's kind of funny that we've a little bit come full circle on asymptotic analysis in that we are now counting FLOPs, and it is not a little bit like what Knuth does here. :)
  - ogogmad 1y ago
    I think this needs the use of a CAS (Computer Algebra System, like Mathematica) to calculate the runtime of some code relative to different choices of computer architecture. Then it looks practical. Could even be added to IDEs. But without the help of a CAS, few people would attempt this, because it would be too tedious to do by hand.
thomasahle 1y ago
> I optimistically imagine a world where we replace the relatively non-specific asymptotic bounds of an algorithm with a very specific quantification of the work an algorithm will take. I think you're getting this backwards. The (good) point you and Mitzenmacher are making is that our analysis standards are _too strict_, and hence we avoid good algorithms that are just too hard to analyze. If we instead require exact combinatorics, e.g., using Flajolet/Sedgewick, that will be _even harder_ than if we _just_ try to do asymptotic analysis. Remember that asymptotics are a way to _approximate_ the exact number of steps. It's supposed to make it _easier_ for you.
- antics 1y ago
  Oh I think there is no real doubt that this is true, it's why analytic combinatorics did not succeed in replacing asymptotic analysis. I just wish it had. If it was tractable in a similar set of areas I think a lot of things would be quite a bit better.
ww520 1y ago
Coincidentally I just did an asymptotic complexity analysis yesterday (something I rarely do). It seemed right since it's by the book but I wasn't sure. After running the extensive benchmarks on the algorithm, I was so happy to find the results matched the asymptotic prediction. The lesson is verify, verify, and always verify. [1] Algorithm, https://github.com/williamw520/toposort/blob/master/Algorithm.md https://github.com/williamw520/toposort/blob/master/Algorith... [2] Benchmarks, https://github.com/williamw520/toposort/blob/master/README.md#benchmark-runs https://github.com/williamw520/toposort/blob/master/README.m...
DevelopingElk 1y ago
In cryptography it is common to get exact estimates for the number of bit operations required to break a cipher. Asymptomatic analysis is great in some circumstances. It for example explains why quicksort is faster than bubble sort for large inputs. Beyond that you want some empirical results.
svat 1y ago
In fact in these slides from a 2011/2012 talk, Sedgewick talks about exactly this, even going as far as to draw a contrast between "TCS" and "analysis of algorithms" (the "scientific method"): https://sedgewick.io/talks/#algorithms-for-the-masses https://sedgewick.io/talks/#algorithms-for-the-masses = https://sedgewick.io/wp-content/uploads/2022/03/2011-12AlgsMasses.pdf#page=17 https://sedgewick.io/wp-content/uploads/2022/03/2011-12AlgsM... onwards. (Also touched upon briefly in https://sedgewick.io/talks/#lasting-legacy-of-flajolet https://sedgewick.io/talks/#lasting-legacy-of-flajolet = https://sedgewick.io/wp-content/uploads/2022/03/2013-14FlajoletLegacy.pdf https://sedgewick.io/wp-content/uploads/2022/03/2013-14Flajo...) His point is exactly that, often researchers care only about worst-case analysis and asymptotics, which is not necessarily a useful scientific analysis of how long an algorithm is expected to take on a machine as a function of the input size (which was the original motivation for Knuth etc to develop the field). The same authors (but ordered as Sedgewick and Flajolet!) also have a book called An Introduction to the Analysis of Algorithms; there's a course website at https://aofa.cs.princeton.edu/home/ https://aofa.cs.princeton.edu/home/ and videos on Coursera (https://www.coursera.org/learn/analysis-of-algorithms https://www.coursera.org/learn/analysis-of-algorithms) — it is advanced mathematics but less advanced than the Analytic Combinatorics book.

by antics 1y ago

krick 1y ago

> I optimistically imagine a world where we replace the relatively non-specific asymptotic bounds of an algorithm with a very specific quantification of the work an algorithm will take. My understanding is that it's pretty much how it started, but proved to be impractical. Meaning, we absolutely can quantify the work any algorithm will take, but for that we need to define the architecture first, i.e., to specify what is the unit of work, what are operations available to us. And, sure, we can do that for any given task (and we always could), but it's usually too messy to include that in general discussions about algorithms, not specifically concerned with the architecture.

antics 1y ago
Yep, That's exactly why we moved to asymptotic analysis. I was just hoping analytic combinatorics would help us move back to something like this.

qsort 1y ago

I'm not a researcher, so start with the default assumption that I don't know what I'm talking about, but I had the same impression when studying those topics, asymptotic analysis is kind of broken. For example, we assume that arbitrary arithmetic takes constant time. Good. Except that if you take that seriously, then P=PSPACE. So we might say that bit operations on fixed registers are constant time. But nobody does that because then arithmetic is O(lg n) and it's too much trouble to keep track of everything (and if you do, then hashtables aren't O(1) any longer!) If we are more sophisticated we might take a transidchotomous model, but that's really weird and we have results like sorting in less than n lg n time. Not to mention that the mathematical foundations get a bit shaky with more than one variable. I think the hard problem underneath is that it's hard to define a computational model that (a) can be reasoned about and isn't extremely weird, (b) has solid mathematical foundations, (c) is reasonably predictive of real world performance, and (d) is not linked to a specific architecture. Asymptotic analysis is kind of a compromise. It can be formulated in very elementary terms, it makes mathematical sense and if you plot the performance of a sorting algorithm on a chart it kind of looks like the graph of n log n if you squint a bit. Knuth does something similar to what you're suggesting IIRC, albeit without the analytic combinatorics machinery. For some programs he derives a precise expression as a function of the size of input that describes how many operations of each kind the underlying machine will perform. In numerical analysis there is a similar concept, e.g. evaluating a polynomial with Horner has the same asymptotic complexity as the naive method, but we say it's better because it takes exactly the optimal amount of floating point operations (and, in practice, because it uses fused multiply-adds, but that's another story...) A research program along those lines would be certainly fascinating, but the combination of "needs to be reasonably predictive" and "needs to be portable" is a tough nut to crack.

antics 1y ago
Yep, I mentioned this elsewhere in the threads—Knuth does do this quite a bit in TAOCP. I think in a lot of ways we've ended up completely full circle, in that we are now counting FLOPs. This time though I think we have very little hope for something as nice and pretty as asymptotics. At least ones that are useful.
Tainnor 1y ago

PollardsRho 1y ago

I don't think it's controversial to say that asymptotic analysis has flaws: the conclusions you draw from it only hold in the limit of larger inputs, and sometims "larger" means "larger than anything you'd be able to run it on." Perhaps as Moore's law dies we'll be increasingly able to talk more about specific problem sizes in a way that won't become obsolete immediately. I suppose my question is why you think TCS people would do this analysis and development better than non-TCS people. Once you leave the warm cocoon of big-O, the actual practical value of an algorithm depends hugely on specific hardware details. Similarly, once you stop dealing with worst-case or naive average-case complexity, you have to try and define a data distribution relevant for specific real-world problems. My (relatively uninformed) sense is that the skill set required to, say, implement transformer attention customizing to the specific hierarchical memory layout of NVIDIA datacenter GPUs, or evaluate evolutionary optimization algorithms on a specific real-world problem domain, isn't necessarily something you gain in TCS itself. When you can connect theory to the real world, it's fantastic, but my sense is that such connections are often desired and rarely found. At the very least, I'd expect that to often be a response to applied CS and not coming first from TCS: it's observed empirically that the simplex algorithm works well in practice, and then that encourages people to revisit the asymptotic analysis and refine it. I'd worry that TCS work trying to project onto applications from the blackboard would lead to less rigorous presentations and a lot of work that's only good on paper.

LegionMammal978 1y ago
Average-case complexity can be a fickle beast. As you say, the simplex algorithm for LP is great in practice, so it's rarely problematic to use. But meanwhile, people also say, "Modern SAT/SMT solvers are great, they can solve huge problems!" Yet when I try using one, I usually run into exponential runtimes very quickly, especially for unsatisfiable instances. Overall, it's annoying to tell whether an NP-hard problem is always really hard, or if ~all practical instances can be solved with a clever heuristic. It doesn't help that most problems receive little attention (e.g., to find solvable special cases) after being labeled NP-hard.
- aleph_minus_one 1y ago

openasocket 1y ago

> One of the nice things about Flajolet/Sedgewick[2] (mentioned in this post) is that it gives a nice set of combinators for (at least it seems to me, in theory) precisely enumerating how many "steps" an algorithm would take given some input. I optimistically imagine a world where we replace the relatively non-specific asymptotic bounds of an algorithm with a very specific quantification of the work an algorithm will take. And that this in turn would free TCS to focus on things that are more germane to the field as a whole. Check out the Art of Computer Programming, by Knuth. He writes all of the algorithms in a hypothetical machine code called MIX (MMIX in later editions). He does go through algorithmic analysis to the degree you describe, showing exactly how many cycles a particular routine may take to complete, based on different variables. This is actually fairly complex even for simple programs. Consider the simple case of computing the maximum in a list: let current_max := 0 for x in array_of_numbers { if x > current_max { current_max = x; } } return current_max; Anyone can tell you this runs in O(N) time. But exactly how many cycles would this take? Ignoring the architectural details, you would need to know how often the condition "x > current_max" is true. If the list of numbers is in ascending order, this will be true every time, if it is in descending order it will only be true once. The difference in the number of cycles between those two cases is significant. I believe Knuth works through this example, and shows that, for a randomly-ordered array, this would be true around log_2(n) times.

antics 1y ago
I actually have read a chunk of the relevant TAOCP, but didn't mention it because the comment was already kind of long. I remarked to a friend the other day that it's kind of funny that we've a little bit come full circle on asymptotic analysis in that we are now counting FLOPs, and it is not a little bit like what Knuth does here. :)
- ogogmad 1y ago
  I think this needs the use of a CAS (Computer Algebra System, like Mathematica) to calculate the runtime of some code relative to different choices of computer architecture. Then it looks practical. Could even be added to IDEs. But without the help of a CAS, few people would attempt this, because it would be too tedious to do by hand.

thomasahle 1y ago

> I optimistically imagine a world where we replace the relatively non-specific asymptotic bounds of an algorithm with a very specific quantification of the work an algorithm will take. I think you're getting this backwards. The (good) point you and Mitzenmacher are making is that our analysis standards are _too strict_, and hence we avoid good algorithms that are just too hard to analyze. If we instead require exact combinatorics, e.g., using Flajolet/Sedgewick, that will be _even harder_ than if we _just_ try to do asymptotic analysis. Remember that asymptotics are a way to _approximate_ the exact number of steps. It's supposed to make it _easier_ for you.

antics 1y ago
Oh I think there is no real doubt that this is true, it's why analytic combinatorics did not succeed in replacing asymptotic analysis. I just wish it had. If it was tractable in a similar set of areas I think a lot of things would be quite a bit better.

ww520 1y ago

Coincidentally I just did an asymptotic complexity analysis yesterday (something I rarely do). It seemed right since it's by the book but I wasn't sure. After running the extensive benchmarks on the algorithm, I was so happy to find the results matched the asymptotic prediction. The lesson is verify, verify, and always verify. [1] Algorithm, https://github.com/williamw520/toposort/blob/master/Algorithm.md https://github.com/williamw520/toposort/blob/master/Algorith... [2] Benchmarks, https://github.com/williamw520/toposort/blob/master/README.md#benchmark-runs https://github.com/williamw520/toposort/blob/master/README.m...

DevelopingElk 1y ago

In cryptography it is common to get exact estimates for the number of bit operations required to break a cipher. Asymptomatic analysis is great in some circumstances. It for example explains why quicksort is faster than bubble sort for large inputs. Beyond that you want some empirical results.

svat 1y ago

In fact in these slides from a 2011/2012 talk, Sedgewick talks about exactly this, even going as far as to draw a contrast between "TCS" and "analysis of algorithms" (the "scientific method"): https://sedgewick.io/talks/#algorithms-for-the-masses https://sedgewick.io/talks/#algorithms-for-the-masses = https://sedgewick.io/wp-content/uploads/2022/03/2011-12AlgsMasses.pdf#page=17 https://sedgewick.io/wp-content/uploads/2022/03/2011-12AlgsM... onwards. (Also touched upon briefly in https://sedgewick.io/talks/#lasting-legacy-of-flajolet https://sedgewick.io/talks/#lasting-legacy-of-flajolet = https://sedgewick.io/wp-content/uploads/2022/03/2013-14FlajoletLegacy.pdf https://sedgewick.io/wp-content/uploads/2022/03/2013-14Flajo...) His point is exactly that, often researchers care only about worst-case analysis and asymptotics, which is not necessarily a useful scientific analysis of how long an algorithm is expected to take on a machine as a function of the input size (which was the original motivation for Knuth etc to develop the field). The same authors (but ordered as Sedgewick and Flajolet!) also have a book called An Introduction to the Analysis of Algorithms; there's a course website at https://aofa.cs.princeton.edu/home/ https://aofa.cs.princeton.edu/home/ and videos on Coursera (https://www.coursera.org/learn/analysis-of-algorithms https://www.coursera.org/learn/analysis-of-algorithms) — it is advanced mathematics but less advanced than the Analytic Combinatorics book.