At the risk of my future embarrassment, this page will contain a list of questions for which I have little to no immediate interest in pursuing at the time of their positing, but which also seem conceptually interesting enough to warrant publicly listing in case some reader might point out that it’s a stupidly obvious question or that I have incorrect presuppositions. Both outcomes would be delightful. A most preferred outcome would be that a question is not stupid and in fact ripe for persistent exploration which someone earnestly expresses their interest in pursuing.
Computer Science
In computational complexity theory, is there a formal definition or any reason to formalize the notion of “meta-complexity,” or the nature of the difficulty of generating an more efficient algorithm for a given problem? Is this just P vs. NP? (Am just now explicitly learning).1- This was a good question! It is indeed a thing: a blog on it.
- Have we found superior deterministic machine learning algorithms? If I recall correctly, many algorithms add noise, dropout, etc., but in Boaz and Barak, it is mentioned that for any non-deterministic algorithm, there exists a deterministic algorithm that can be derived from the probabilistic algorithm that is not much worse. 2