1000x slowdown is bad but not a complete deal breaker. Do you have a sense of what a reasonable achievable factor is? Do you have sense for how long before we get to that achievable factor?
Local compute is preferable where possible. There are cases where computation needs to be performed remotely. For example, when collecting data from remote entities while preserving privacy by allowing each entity to retain ownership of the encryption keys used to protect its data. At Belfort, we are exploring such applications, such as
> For [Dependency resolution] and [Type checking], the worst-case just doesn't occur. ... at least in my career, I've never seen a galactic blow-up.
Both of these problems have been hand crafted and sanded down so as not to get into situations where there's exponential blow up.
> [Scheduling] and [Traveling Salesman] are technically optimization problems. Everyone knows you can tackle those with heuristics, ... We absolutely have tools that can find provably optimal solutions in reasonable time. There's no magic. No quantum computers. Just thinking harder and coming up with better algorithms. ... algorithmic speedup has outpaced hardware gains in the last decades. ...
The tools that can "absolutely find optimal solutions" don't, for even toy problems. Thinking harder helps, sometimes, but barely scratches the surface of most of these problems. Most of the time, thinking harder doesn't magically solve these problems.
> Last but not least: even (5), the archetype of NP-hard problems, is routinely solved at scale.
If this were even remotely true we'd have seen substantial progress in automated theorem proving well before the last couple of years. Notice how there are many math problems succumbing to automated techniques? This isn't because SAT solvers "routinely solve this at scale", it's because LLMs are getting better.
Why do we need type checking in the first place? One reason is to help find bugs. We need to enforce type checking to reduce bugs because reducing programs to SAT to ensure they're bug free is intractable. SAT is solved at scale? Why haven't they made solvers to prove your code is bug free so you don't need type checking in the first place?
I'm not up on scheduling software or research but my bet is that people who actually write schedulers would say that those tools that "absolutely" solve the problem absolutely don't.
The post almost gets it but never quite makes the leap. Taking Turing machines, for example. It's pretty easy to show that the Halting problem is undecidable. It doesn't mean all programs can't be analyzed, it means that there's no general method that will work for all programs. We don't give up on writing programs, we restrict ourselves to programs that we can reason about.
The ensemble, the space of problems we draw from, is specifically chosen so that we can do interesting work. But even that's restrictive and we're trying to constantly push to see what other programs we can analyze that are past our current front of knowledge.
This reads like child going into a supermarket and declaring farming, logistics and food scarcity to be solved because of the abundant availability of goods on the shelf. The world we've made is specifically crafted so that normal use is smooth. The fact you can't see it means you're living in a coddled domain and haven't pushed past it.
> ... I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.
Power law distributions are specializations of the more general Levy stable distributions [0] [1]. Levy stable distributions answer the following question:
Given that the sum of independent and identically distributed random variables that converge to a distribution, what is the distribution they converge to?
If you answered Gaussian, you'd be wrong. The correct answer is Levy stable. There was no condition on finite variance. When variance can be infinite, Levy stable, or power law tail distributions, is the result. When the variance is finite, a Gaussian is the limiting distribution and, consequently, a Gaussian distribution is part of the family of Levy stable distributions.
The stability quality is the reason why the Levy stable (aka power law tail) distributions show up all over the place. If you've ever heard that the reason why the Normal distribution is called "normal", because the sums of (finite variance) random variables converges to a Gaussian, the same reasoning applies to the Levy stable. In some sense, Levy stable distributions are more normal than the normal distribution. My opinion is that infinite variance is hard for people to wrap their heads around, so they reject the premise.
Unfortunately I don't have a good answer for what the article brings up about the Fourier transform, but I'm almost positive that this can be answered with Levy stable distributions in mind. I will say that the distribution is often characterized by it's characteristic function. A short perusal of Wikipedia talks about Levy stable distributions being closed under Fourier transforms, which is what the article is talking about.
OP is considering power laws in the frequency domain.
You are considering power laws in the heavy tail of a distribution.
Different things! But there are confounders that make discussion seem similar:
- questions about moments and convergence (OP: do we have finite energy in the Fourier domain; your comment: do the tails of the distribution fall off fast enough to have finite moments of order 1 or 2)
- questions about averaging (OP: in the time domain; your comment: as an expectation obtained by integrating a distribution, or as a closure property of the stable class of distributions)
1% compounding "positive impact", however that's defined, still leads to a singularity like event. Moore's law-like effects are doubling computing power for fixed cost at 1.5 to 2 years, so it's noticeably fast, especially as we get near the "hockey stick" point, but there are other exponential effects that are happening in tandem, notably solar.
Global energy usage is rising at a yearly rate of about 2.5%. In my view, this is one of the most basic statistics that correlates to improved quality of life.
Regardless of what measure of "progress" you use, if it's compounded, it leads to drastic changes very quickly.
Even a BOM would be helpful. Also understanding the post-processing/cleanup step would be interesting.
reply