Manuel Blum has this extraordinary page on advice to a beginning Ph.D student. Read it slowly though, for there is much to absorb. Update: Let me add this piece of advice by Dijkstra, his Third ...

$ACC^0$ is a natural complexity class. 1) Barrington showed that computation over non-solvable monoids capture $NC^1$ while over solvable monoids capture $ACC^0$. 2) Recently, Hansen and Koucky ...

One of the more practical manifestation of CS is Compiler Construction. In 1965, Knuth started the study of LR parsers. Quickly (in less than a decade), we had LALR parsers which are a subset of ...

I did not know of these until recently. 1) The LU decomposition of a matrix is due to Turing! Considering how fundamental LU decomposition is, this is one contribution that deserves to be highlighted ...

Yes. We do know good lower bounds and we have known them for quite some time now. Jerrum and Snir proved an exponential lower bound over monotone arithmetic circuits for the permanent by 1980. ...

Yes. Stack heights. $\mathsf{SAC^1} = \mathsf{NAuxPDA}(\log n, \log n)$, that is, with $O(\log n)$ space and $O(\log n)$ stack height; this implies $\log n$ configurations and therefore $\log^2(n)$ ...

The first half of this answer is nothing more than an efficient ($\log^4(n)$ to $\log^2(n)$) rephrasing of David's answer in complexity theoretic terms. Context free languages live in the complexity ...

With "appropriate" modifications we can turn these classes into complexity classes; Finite Automata into $NC^1$, CFL into LogCFL, and LBA into PSPACE. It should now be quite clear why we are ...

Check out this paper of McKenzie, Reinhardt, Vinay. We use multiplex-select gates to characterize classes between $NC^1$ and $LOGCFL$, including $L$, $LOGDCFL$ etc. For example, $L = MWidth, Size(log,... View answer 11 votes To go with divide-and-conquer, I would say splice-and-combine. I usually use both words, splice and combine while teaching/explaining DP; but not used splice-and-combine explicitly. Sometimes I have ... View answer Accepted answer 10 votes What you are looking for is likely Leaf Languages. Look at the output of each path of an NP machine and concatenate them into an exponentially long string. We can now talk of the machine accepting the ... View answer 10 votes Eva Tardos proved that the gap is truly exponential by showing that there is a monotone boolean function that has poly size circuits but requires exponential size monotone circuits. Nothing better ... View answer Accepted answer 10 votes Since we don't seem to have any answers, can I make a comment? Suppose we are given$n$bits,$X=x_1,\cdots,x_n$and we have to complement each bit to get$\neg x_1,\cdots, \neg x_n.\$ The only ...

Shortest paths in DAGs are typically problems in NL and many times complete as well. A slightly "larger" class is LOGCFL (of course, we don't know if NL=?LOGCFL) where typical problems solvable with ...

What you ask for should have bad consequences but I cannot think of any immediately. So I have only some pointers to what we know. Check out Viola's On the power of small depth computation The best ...

Yes it is possible. We could use the notion of surface configurations; they were introduced by Cook a long time back. With this it should be quite easy to get a version of pumping lemma out. As to ...

Check out Luis Von Ahn at CMU. He is the original Captcha guy. You will find enough videos like this google techtalk on the subject of Human Computation.

When an optimization problem is known to be hard, it is usual to look at their maximal versions. For example, whereas independent set is NP-Complete, the lex first maximal independent set, which is P-...

Some additional references I remember of that era: 1) Diaconis and Stroock, Geometric bounds for eigenvalues of Markov chains, The Annals of Applied Probability, 1991; but I remember getting my hands ...

@JeffE, Here is a paper that counts min weight cycles in a graph. As far as I remember, it was definitely inspired by Karger's technique/result and it was a fun proof. Hope this helps with the ...