<p>Consider papers published in major theoretical CS conferences during the last 5 year, where the main result is that there exists an algorithm with some time or space complexity to solve some problem. Approximately, what percentage of these algorithms are <a href="https://en.wikipedia.org/wiki/Galactic_algorithm" rel="noreferrer">galactic</a>, in the sense that previously known algorithms are better in all cases where the computation takes less than <span class="math-container">$10^{100}$</span> operations or that they are purely existential results with no known construction? We can assume that a reasonable engineering effort is made to implement the algorithms, but no new significant algorithmic advances are made during the implementation.</p>

CC BY-SA 4.0
2020-03-05T11:20:20.330Z
I suppose the answer would be ~100% if you weight the various papers by runtime. :)
Geoffrey Irving
CC BY-SA 4.0
2020-03-06T22:29:28.200Z
a very good question, but a reasonably correct answer would probably entail quite some laborious work, since the needed data is present only in very implicit form (I am not regularly following SODA, so I cannot tell whether an expert would have a strong gut feeling about this). Is there a more approachable question to ask in this regard, to get at least some insight?
Hermann Gruber
CC BY-SA 4.0
2020-03-07T10:27:04.013Z
I think ultimately, the goal of a more approachable question on this regard would be to  estimate the quantity that I'm asking for, so I think directly asking it is the right thing. However I want to emphasize that I'm interested in all kinds of answers that try to estimate this quantity: gut feelings, answers regarding some subset of the papers, lower bounds, upper bounds, etc., so a valid answer is not necessarily a thorough analysis of a representative sample of the papers.
Laakeri
CC BY-SA 4.0
2020-03-09T20:14:30.660Z
Perhaps you could create an anonymous survey for the authors and hope for their honesty. As long as they are not recorded directly criticizing their own work I'd guess that they have little reason to be dishonest. Possibly not everyone will have thought about it (or it might be hard to answer) so leaving an option for unsure would be good.
Elle Najt
<soft-question><big-picture><application-of-theory>
What percentage of SODA papers are galactic algorithms?
Laakeri
# What percentage of SODA papers are galactic algorithms?

(Asked by: username_0 on 2020-03-03)

Consider papers published in major theoretical CS conferences during the last 5 year, where the main result is that there exists an algorithm with some time or space complexity to solve some problem. Approximately, what percentage of these algorithms are [galactic](https://en.wikipedia.org/wiki/Galactic_algorithm), in the sense that previously known algorithms are better in all cases where the computation takes less than $10^{100}$ operations or that they are purely existential results with no known construction? We can assume that a reasonable engineering effort is made to implement the algorithms, but no new significant algorithmic advances are made during the implementation.

**Tags:** soft-question, big-picture, application-of-theory

> **Comments:**
> **username_1**: I suppose the answer would be ~100% if you weight the various papers by runtime. :)  
> **username_2**: a very good question, but a reasonably correct answer would probably entail quite some laborious work, since the needed data is present only in very implicit form (I am not regularly following SODA, so I cannot tell whether an expert would have a strong gut feeling about this). Is there a more approachable question to ask in this regard, to get at least some insight?  
> **username_0**: I think ultimately, the goal of a more approachable question on this regard would be to  estimate the quantity that I'm asking for, so I think directly asking it is the right thing. However I want to emphasize that I'm interested in all kinds of answers that try to estimate this quantity: gut feelings, answers regarding some subset of the papers, lower bounds, upper bounds, etc., so a valid answer is not necessarily a thorough analysis of a representative sample of the papers.  
> **username_3**: Perhaps you could create an anonymous survey for the authors and hope for their honesty. As long as they are not recorded directly criticizing their own work I'd guess that they have little reason to be dishonest. Possibly not everyone will have thought about it (or it might be hard to answer) so leaving an option for unsure would be good.  

---

## 0 answers

