48
$\begingroup$

Complexity theory is a strong secondary interest of mine but it's not my primary research interest, so there is no hope for me to attend all the conferences, read all the blogs, and ensure that the "in" crowd cc: me on every bit of hot news. I try to do some of this but I am wondering what methods will give me the most bang for the buck (or rather time, since time is more of a limiting factor than money in this context). Some methods I have attempted include:

  • Look over STOC/FOCS proceedings. This often means I don't hear about breakthroughs until they're (somewhat) old news, but that's O.K. from my point of view as long as I am likely to catch the news eventually. Are there other proceedings I should be tracking?

  • Subscribe to the Los Alamos ArXiv. How many complexity theorists use this? Are there other preprint servers I should look at?

  • Read blogs. I tried this for a while but have more or less given up because there are too many blogs out there and it seems to be a very inefficient method of staying current.

Anything I've missed? Again my focus is on finding time-efficient methods rather than on doing every conceivable thing to keep abreast.

Edit: Thanks for all the responses; I would accept more than one answer if the software allowed it. My somewhat arbitrary choice is based on the fact that I now recall having heard of the ECCC and the CCC before, but I was completely unaware of the Blog Aggregator.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If you have a subfield you are interested in, google alerts + google scholar alerts can be useful. You can set it up to email you when it finds a paper with some phrase, or citing some paper $\endgroup$
    – Yaroslav Bulatov
    Commented Jan 4, 2011 at 17:43
  • 5
    $\begingroup$ I'd also track CCC (the complexity conference) for complexity theory. I think more and more researchers are starting to use the arxiv, and ECCC is another good choice. They all have RSS feeds (the cs.CC tag for example on the arxiv), so it's easy to slot into a feed reader $\endgroup$
    – Suresh Venkat
    Commented Jan 4, 2011 at 17:45

6 Answers 6

Reset to default
23
$\begingroup$

You could also subscribe to Theory of Computing Blog Aggregator. Though it includes not only complexity theory (CT) updates but the key news on CT, I think, you are guaranteed to obtain.

Improve this answer
$\endgroup$
1
26
$\begingroup$

In addition to ArXiv, you could subscribe to the Electronic Colloquium on Computational Complexity. It gets a lot of traffic from current research, and the email updates you receive are normally a succinct format of paper title/author(s)/abstract, so you won't have to invest much time to see what's just happened.

Improve this answer
$\endgroup$
1
19
$\begingroup$

You could look at the Conference on Computational Complexity. This isn't as prestigious as STOC or FOCS, but it usually has a number of interesting papers. Also, STOC, FOCS, and CCC generally announce the list of accepted papers well before the Proceedings come out, and if you see anything interesting on the list of titles, you can often find it on the web.

Improve this answer
$\endgroup$
14
$\begingroup$

Arxiv is not very useful for computational complexity, although certain subfields such as quantum computing do use it. On the whole, there is no quality control at all, and many of the papers listed as belonging to computational complexity are either incorrect, or only marginally related to the field. ECCC (Electronic Colloquium on Computational Complexity) reports are usually much more germane, and mostly by experts in the area. There are only a few each week, and cover a wide variety of topics. So I recommend looking at new ECCC reports, at least glancing at abstracts, and perhaps reading more if they look interesting.

Another resource you can use is Oded Goldreich's list of ``Papers I find interesting'' or something like that, off his homepage. He gives a summary and discussion of stuff he likes. The additions are irregular, and seem to average one or two a month.

You are also welcome to come to talks at IAS any time. I could add you to the mailing list if you are not already on it....

Russell Impagliazzo

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, Russell. I am on the IAS mailing list and I do come once in a while. $\endgroup$
    – Timothy Chow
    Commented Jan 5, 2011 at 16:17
4
$\begingroup$

Another good source is the page by Oded Goldreich with the list of "recent works that have drawn their (Oded's and other various researchers') attention" and comments to them (works). Incidentaly, this concerns not only mathematicians.

Improve this answer
$\endgroup$
1
$\begingroup$

Oops, sorry! I see that you already have the blogs covered...

Original post:

You could also check out some blogs:

http://blog.computationalcomplexity.org/ is a good example.

These are sort of analogous to some of the math blogs except that the math blogs aren't/can't be as comprehensive for obvious reasons.

Lance and Bill regularly post reviews of all the major conferences and workshops and there is a reasonably comprehensive discussion of all the current complexity results.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.