I think Lance's choices from the past are pretty comprehensive, although I might add a couple more from the lower bounds department which for some reason are not well-known:

John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant: On Time Versus Space. J. ACM 24(2): 332-337 (1977)

 

Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Preliminary Version) FOCS 1983: 429-438

The first paper shows that $TIME[t] \subseteq SPACE[t/\log t]$ (so, $SPACE[t]$ is not contained in $TIME[o(t \log t)]$). This result has since been generalized (from Turing machines) to all the "modern" models of computation. (For references, look at citations on Google scholar.)

The second paper shows that for multitape Turing machines, $NTIME[n] \neq TIME[n]$. This is really the only generic separation of nondeterministic and deterministic time that we know. It is not known whether this result extends to more modern models of computation. Perhaps one reason why these results are not better known is that many seem to believe that their approaches are a dead end, more or less. (There's some mathematical evidence for that: the techniques do break down if you try to push them any further, but it's always possible these techniques could be combined with something new.)

As for the last 6 years... I'll have to think about my choices for the "best papers" since then. Expect an update to this answer later. I think the following work over the last six years should be among those that everyone should know about. That doesn't mean that I think they're "best", it just means I am trying to answer the original question. It's a very biased list.

• Irit Dinur's combinatorial proof of the PCP theorem

• Omer Reingold's logspace algorithm for st-connectivity

• Ketan Mulmuley's geometric complexity theory program

• Subhash Khot's Unique Games Conjecture and what it entails (this was initiated earlier than 6 years ago but it has become much more important in the last 6 years)

• Russell Impagliazzo and Valentine Kabanets' "Derandomizing polynomial identity testing means proving circuit lower bounds"

• Lance Fortnow et al.'s time-space lower bounds for SAT (this is excluding all work that I have personally done on this, you can decide for yourself if you should know about that)

I left out a bunch of very important things because the list is 6 items. Sorry.

I think Lance's choices from the past are pretty comprehensive, although I might add a couple more from the lower bounds department which for some reason are not well-known:

John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant: On Time Versus Space. J. ACM 24(2): 332-337 (1977)

Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Preliminary Version) FOCS 1983: 429-438

The first paper shows that $TIME[t] \subseteq SPACE[t/\log t]$ (so, $SPACE[t]$ is not contained in $TIME[o(t \log t)]$). This result has since been generalized (from Turing machines) to all the "modern" models of computation. (For references, look at citations on Google scholar.)

The second paper shows that for multitape Turing machines, $NTIME[n] \neq TIME[n]$. This is really the only generic separation of nondeterministic and deterministic time that we know. It is not known whether this result extends to more modern models of computation. Perhaps one reason why these results are not better known is that many seem to believe that their approaches are a dead end, more or less. (There's some mathematical evidence for that: the techniques do break down if you try to push them any further, but it's always possible these techniques could be combined with something new.)

As for the last 6 years... I'll have to think about my choices for the "best papers" since then. Expect an update to this answer later. I think the following work over the last six years should be among those that everyone should know about. That doesn't mean that I think they're "best", it just means I am trying to answer the original question. It's a very biased list.

• Irit Dinur's combinatorial proof of the PCP theorem

• Omer Reingold's logspace algorithm for st-connectivity

• Ketan Mulmuley's geometric complexity theory program

• Subhash Khot's Unique Games Conjecture and what it entails (this was initiated earlier than 6 years ago but it has become much more important in the last 6 years)

• Russell Impagliazzo and Valentine Kabanets' "Derandomizing polynomial identity testing means proving circuit lower bounds"

• Lance Fortnow et al.'s time-space lower bounds for SAT (this is excluding all work that I have personally done on this, you can decide for yourself if you should know about that)

I left out a bunch of very important things because the list is 6 items. Sorry.

I think Lance's choices from the past are pretty comprehensive, although I might add a couple more from the lower bounds department which for some reason are not well-known:

John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant: On Time Versus Space. J. ACM 24(2): 332-337 (1977)

Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Preliminary Version) FOCS 1983: 429-438

The first paper shows that $TIME[t] \subseteq SPACE[t/\log t]$ (so, $SPACE[t]$ is not contained in $TIME[o(t \log t)]$). This result has since been generalized (from Turing machines) to all the "modern" models of computation. (For references, look at citations on Google scholar.)

The second paper shows that for multitape Turing machines, $NTIME[n] \neq TIME[n]$. This is really the only generic separation of nondeterministic and deterministic time that we know. It is not known whether this result extends to more modern models of computation. Perhaps one reason why these results are not better known is that many seem to believe that their approaches are a dead end, more or less. (There's some mathematical evidence for that: the techniques do break down if you try to push them any further, but it's always possible these techniques could be combined with something new.)

As for the last 6 years, I'll have to think about my choices for the "best 6 papers" since then. Expect an update to this answer later.

I think Lance's choices from the past are pretty comprehensive, although I might add a couple more from the lower bounds department which for some reason are not well-known:

John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant: On Time Versus Space. J. ACM 24(2): 332-337 (1977)

Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Preliminary Version) FOCS 1983: 429-438

The first paper shows that $TIME[t] \subseteq SPACE[t/\log t]$ (so, $SPACE[t]$ is not contained in $TIME[o(t \log t)]$). This result has since been generalized (from Turing machines) to all the "modern" models of computation. (For references, look at citations on Google scholar.)

The second paper shows that for multitape Turing machines, $NTIME[n] \neq TIME[n]$. This is really the only generic separation of nondeterministic and deterministic time that we know. It is not known whether this result extends to more modern models of computation. Perhaps one reason why these results are not better known is that many seem to believe that their approaches are a dead end, more or less. (There's some mathematical evidence for that: the techniques do break down if you try to push them any further, but it's always possible these techniques could be combined with something new.)

As for the last 6 years... I'll have to think about my choices for the "best papers" since then. Expect an update to this answer later. I think the following work over the last six years should be among those that everyone should know about. That doesn't mean that I think they're "best", it just means I am trying to answer the original question. It's a very biased list.

• Irit Dinur's combinatorial proof of the PCP theorem

• Omer Reingold's logspace algorithm for st-connectivity

• Ketan Mulmuley's geometric complexity theory program

• Subhash Khot's Unique Games Conjecture and what it entails (this was initiated earlier than 6 years ago but it has become much more important in the last 6 years)

• Russell Impagliazzo and Valentine Kabanets' "Derandomizing polynomial identity testing means proving circuit lower bounds"

• Lance Fortnow et al.'s time-space lower bounds for SAT (this is excluding all work that I have personally done on this, you can decide for yourself if you should know about that)

I left out a bunch of very important things because the list is 6 items. Sorry.