Max
  • Member for 11 years, 2 months
  • Last seen more than a month ago
What are some problems where we know we have an optimal algorithm?
Accepted answer
20 votes

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

View answer
Are there any counterintuitive results in theoretical computer science?
13 votes

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

View answer
Is it possible to test if a computable number is rational or integer?
10 votes

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

View answer
What's new in compiler optimization techniques over last few years?
Accepted answer
8 votes

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

View answer
Can Bencodes Be Described With a Context-Free Grammar?
7 votes

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
Recent fundamental results in algorithms?
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
A protocol for honest compromise
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
Hard-looking algorithmic problems made easy by theorems
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. ...

View answer
What is the quantum computational model?
2 votes

Besides his standard text with Chuang, Michael Nielsen has a series of video lectures on Youtube called Quantum Computing for the Determined which so far gives an overview of the computational model. ...

View answer