Any algorithm which takes linear time and has to read its whole input must be asymptotically optimal. Similarly, as Raphael comments, any algorithm whose runtime is of the same order as output size is ...

As Philip said, Rice's theorem is a good example: one's intuition before studying computability is that there must surely be something we can compute about computations. It turns out that we can only ...

Assuming a real is given as a sequence of rational approximations with the error bounded by some known computable function which tends to zero (all such approximations are equivalent, and correspond ...

I'm not sure how novel it is, or if it's too much on the applied side for your interest, but Hoopl shows how a control/data flow optimization can be modularised, with propagation of facts about ...

The language of valid Bencoded values is not context-free—and nor is just the language of Bencoded strings. Let $L$ be the set of valid Bencoded values, and let $L'$ be the intersection of $... View answer 5 votes Cache-oblivious algorithms were first conceived of (according to Wikipedia) in 1996. An algorithm is cache-oblivious if it uses caches in an optimal way, without knowing the size of the cache (which ... View answer Accepted answer 4 votes There's a trivial protocol whose expected value is the correct mean: everybody announces their preference, and one is chosen at random. No player (acting alone) can do better than to announce their ... View answer 2 votes Finding min-cuts. Given a weighted graph and two vertices$((V, E), s, t)$, find$E' \subset E$such that$s$and$t$are not connected in$(V, E')$, such that the total weight of$E'\$ is maximised. ...