13
$\begingroup$

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, 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.

Improve this question
$\endgroup$
4
  • $\begingroup$ I suppose the answer would be ~100% if you weight the various papers by runtime. :) $\endgroup$
    – Geoffrey Irving
    Mar 5, 2020 at 11:20
  • $\begingroup$ 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? $\endgroup$
    – Hermann Gruber
    Mar 6, 2020 at 22:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Laakeri
    Mar 7, 2020 at 10:27
  • 2
    $\begingroup$ 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. $\endgroup$
    – Elle Najt
    Mar 9, 2020 at 20:14

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy