@AIBert sounds good to me, just saying that answering your question would be a large undertaking. E.g. if you look at the NeurIPS conference call for papers, it mentions 12 general example areas and about 44 example sub-areas. Between just that conference, ICML, and AAAI alone there are several thousand papers published each year. On the theory side, there are the conferences COLT and ALT. Someone's answer discusses NLP-specific conferences.

@Carl-FredrikNybergBrodda completely true, and I purposely worded my comment to avoid claiming otherwise, but apologize if I did a bad job.

Note that "AI research" is a much broader field than machine learning, let alone deep statistical machine learning -- it goes back 70+ years, encompassing many areas a layman might not think of as 'artificial intelligence' (see e.g. the table of contents of "AI: A Modern Approach"). Do you want to narrow the question to statistical "deep" neural-network machine learning?

the set of actions available to them in the hand of poker they play are identical to the case where they both only have k chips - but the payoffs aren't. If the low player loses k chips, they lose the game. If the high player loses k chips, they're still in it.

The confusion is discussed my third bullet point. A learning problem needs not just a hypothesis class but also a loss function. I mention how certain settings have answers, then Student replies that they are aware of those settings and not interested in them, so the question is what settings they are interested in.

We're not allowed to hash the objects (etc), only test equality?

We can always consider codewords where the second half of the bits are all zero, reducing to "the largest code of length $n/2$ with minimum distance $n/4$." I wonder how much better is possible?

Can you clarify if you are looking for something to teach with in the future, or just asking a question that happened to be inspired by a teaching experience?

Surely we can make this rate as slow as we want, by letting $p$ put arbitrarily low weight on many points? For instance, $p = (1-\alpha, \alpha/(N-1), \dots, \alpha/(N-1))$. Now even if we just consider $p_T(1)$, we have $n_T(1) \to 1$ very quickly, but $N_T$ grows toward $N$ arbitrarily slowly as we choose $\alpha$ small enough.

Thank you @TerryTao , this is illuminating! I still struggle distinguishing Qiaochu's proof structure from your halting one. Isn't yours of the form "for all computable $P$, there exists $s_P := (K_P,K_P)$ such that $P(s_p) \neq $Halt$(s_p)$."? The distinction of quantifiers is unclear to me because in both proofs, it seems we get to choose the map $P \mapsto s_P$, and in both we show there exists a global $Q$ that produces a contradiction at any given $(P,s_P)$. I agree Halting involves quining, but Cantor's involves no quining... anyway, I hope I am not being dense and this feedback helps!

You can argue that diagonalization is gratuitous here because we do not need to construct the entire table; we assume for contradiction that there exists a row that computes $f^*$, then show that it does not. (Cantor in some sense requires constructing the entire table before proving the row-wise contradiction.) But then I think we have to admit that diagonalization is gratuitous in the case of the Halting proof as well...

You can argue that this is not self-referential, but neither is Cantor's diagonal argument, right? The $j$th column simply picks out the $j$th digit, it has nothing to do with the interaction of the current row with the object in row $j$.

@TerryTao I think this is a diagonalization proof: In diagonalization, we argue that some function $f^*$ cannot be in a given list of functions, because it disagrees with the $j$th function on the $j$th input (of some list of inputs). Here, if the unbounded halting TMs are $P_1,\dots$, then the $j$th function is $Q_{P_j}$. Then KC cannot be computed by any unbounded halting TM $P_j$, because $Q_{KC}(|P_j|) \neq Q_{P_j}(|P_j|)$.

The Wasserstein distance might be helpful, if $f$ is very nice.

Does there exist a distribution that satisfies this?

"If you put $\theta = p$" --> $\theta = 1$?