Here are the best papers at STOC and FOCS in the last few years, as best as I could gather. What picture does that paint of research activity in core theoretical computer science? Crypto, approximation, and hardness of approximation are progressing swiftly, but also error-correcting codes. Structural space complexity continues strong. (Some outliers: discrete math, game theory, and the paper on faster integer multiplication.)

Are those the areas where new ideas are emerging, where things are happening, and therefore where one might consider hiring? I'm just considering the core here, not the exploding areas of interdisciplinary research.

ACM STOC 2010

"QIP=PSPACE," and "An Improved LP-based Approximation for Steiner Tree."

ACM STOC 2009

"A Constructive Proof of the Lovasz Local Lemma", and "Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem".

ACM STOC 2008

"Optimal Hierarchical Decompositions for Congestion Minimization in Networks", and "Algorithms and Inapproximability Results for Every CSP?".

ACM STOC 2007

"Faster Integer Multiplication", and "Towards 3-Query Locally Decodable Codes of Subexponential Length".

ACM STOC 2006

"The PCP Theorem via Gap Amplification".

ACM STOC 2005

"Undirected ST-connectivity in log-space".

ACM STOC 2004

"Expander Flows, Geometric Embeddings, and Graph Partitionings", and "Multi-linear formulas for permanent and determinant are of super-polynomial size".

IEEE FOCS 2010

"Subexponential Algorithms for Unique Games and Related problems".

IEEE FOCS 2009

Best Paper Award: none?

IEEE FOCS 2008

"Two Query PCP with Sub-Constant Error"

IEEE FOCS 2007

"Space-Efficient Identity Based Encryption without Pairings"

IEEE FOCS 2006

"Settling the Complexity of 2-Player Nash-Equilibrium"

IEEE FOCS 2005

"The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into L1", and "Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time".

IEEE FOCS 2004

“Hardness of Approximating the Shortest Vector Problem in Lattices”, and “Cryptography in NC0”.

Of course, one may conjecture that these are simply the areas which have more political power at the moment, and can flex the right muscles to get their own members the awards.

ReplyDeleteOn the question whether to focus hiring in such areas, one may answer "Why not? It's beneficial for an institution to hire people in politically influential areas."

-mihai

Hello Claire, a mildly self-serving comment: I think arithmetic circuit complexity is another area which has made good progress recently. We have seen progress on lower bounds (you already have one such paper in your list), on polynomial identity testing, with both conditional results ("hardness versus randomness") and unconditional results (for restricted classes of circuit); we have seen progress on depth reduction ("the chasm at depth four").

ReplyDeleteIn algorithms, a field that I do not know that well, it seems that we have also had interesting results on "non-approximation" algorithms (exact exponential time algorithms, fixed parameter tractability...).

But for some reason these topics do not seem to be so well represented at STOC and FOCS.

Now I suppose that the readers of this blog will follow suit by listing their favourite results in (or even out of!) their area of expertise.

At least we will learn in what areas your readers work.

PK.

Hi Claire,

ReplyDeleteI think the list raises some interesting questions. I definitely see

a lack of efficient algorithms papers in the list.

I don't think the list sais much about relative quality between

fields. How can you, say, compare an algorithms with a crypto paper.

Some of the awards are for problems that may be a bit contrived to

outsiders, so it often boils down to "these famous people like the

problem/result". This means that not only do you need a star to solve

the problem, you also need famous stars to support it, and it is

particularly useful if you have strong supporters on the PC. Fields

that have already captured previous best paper awards, are more

likely to feel that their best papers deserve the award. Finally,

it helps with a unified field that knows to pick and rally

behind their best paper, proclaiming victory in blogs long before the

PC gets to the decision.

One issue for non-approximation algorithms is that we have too

many important but unrelated problems dividing the field into

pockets.

An excellent example of a non-award-winning algorithms paper is from

STOC'03 (the first best paper award year):

[DI] Camil Demetrescu, Giuseppe F. Italiano: A new approach to

dynamic all pairs shortest paths. STOC 2003:159-166.

The paper showed that we can update the all-pairs shortest path matrix in

near-quadratic time, which is the best one can hope for. There had been plenty

of previous work with weaker results, e.g., the previous best was

n^2.5 in unweighted graphs whereas DI is for arbitrary weights.

Note that shortest paths computations is something that come up many

places in real computing.

The paper introduced a new approach to shortest paths, considering

much less potential shortest paths than Dijkstra. This lead to their

strong theoretical result for the dynamic case. They also found it to

work very well in practice for the non-dynamic static case. For the

static case, they had no theory result, but at this years' FOCS, the

DI-algorithm was proved to be optimal on random graphs:

Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick: All-Pairs

Shortest Paths in O(n2) Time with High Probability. FOCS 2010:

663-672.

Now take the current champinion of the complexity folks:

http://blog.computationalcomplexity.org/2010/11/breakthrough-circuit-lower-bound.html

As far as I understand this, we already know that there are things we cannot

do with mod_p gates for primes p, and now Ryan can prove limits to what

we can do with mod_6 gates, not that we have either type of gate on a real

computer, but Ryan has the support of Dick, Scott,

Luca, and Reingold, so surely he will get awarded.

One thing I like from the blog praise of Ryan is "doesn't use deep

mathematical techniques but rather puts together a series of known

tools in amazingly clever ways". Cleverness often leads to

breakthroughs in algorithms, but an algorithms paper would surely

be critized for lack of new fundamental techniques.

Contrasting the above mod_6 result, at STOC'06, Patrascu and I were

the first to prove a separation on the query efficiency with a

polynomial versus a near-linear space. Near-linear space is what we

need to store large data sets, so understanding its limits should be

fairly relevant to computing. I don't think anyone understanding the

result would dispute that it is as strong as can be within its field,

but you need strong supporters in the PC understanding and

appreciating the result. Otherwise you are simply not on the radar for

best paper.

So back to Claire's question. I think best paper is very much a

question of politics. Areas like efficient algorithms may be pretty

bad if you want best paper awards, but they can be very satisfying if

you want to do something of relevance to computing.

Best, Mikkel

Mikkel, Pascal and Mihai, I do not think that anything can be inferred from the absence of a field from the list. It does not mean that the field is not thriving. But for an area to be present, it needs, not only advocates etc., but also exciting advances. So I think that the presence of a field is meaningful.

ReplyDelete