Aaron Sterling had the nice suggestion (in comments here) for site promotion at FOCS: his idea was:

a poster with a few "best questions" in large print on it: representatives of

  1. community wiki,
  2. a reference request where a top expert swooped in and resolved the issue, and
  3. an open problem such as an NP-reduction where answerers solved it on the spot

Any nominations ? One per answer, and specify which category: in each case, also pick an answer if none was accepted. If we can get some nominations within a week I can mock up a poster and stick it at the registration desk.

Update: Great suggestions all. Any thoughts on the best way to lay these out on a poster ? One idea would be to orient the poster in landscape mode and have three columns, with 1/2 questions/answers in each.

Update 2: For logistical reasons, I had to can the poster idea. but I thought I'd use a variant of what Joshua was suggesting, which was to use a single sheet for each question, with the question on the front and the answer on the back. I can generate a number of copies for different questions, and try to slip them into people's registration bags :).

Here's an example of what I'm thinking. Tell me what you think. AND SOON :)

Update 3: New version with only answer hints. Thoughts ?

Update 4: I'm in Las Vegas now, and successfully got a sheet inserted in each registration packet, as well as scattering copies of the sheets on registration desks. I hope this will encourage more people to visit.

An additional suggestion, while I'm at it. There should be one example of an answer by a "name to conjure with," e.g., Noam Nisan's accepted answer to this question: cstheory.stackexchange.com/questions/314/… – Aaron Sterling Oct 9 '10 at 2:01
Here's an example of a situation where a big name (Noam Nissan) made a reference request which was answered by a littler name (myself): cstheory.stackexchange.com/questions/317/… . I suspect that Noam didn't find that paper himself because the words "internal regret" weren't in the abstract. I could answer it only because I went to grad school with the people who wrote it. – Warren Schudy Oct 9 '10 at 14:15
How about mentioning several unsolved technical questions, too? Glancing at highest voted questions, unshuffling a string and the product of many degree-1 polynomials are the most voted among unsolved non-community-wiki questions (and I like both questions very much). – Tsuyoshi Ito Oct 9 '10 at 21:04
another nice idea...I like both those questions myself.. – Suresh Venkat Oct 9 '10 at 21:20
I have just realized that it can be a little risky because they might be solved before the poster stating them as unsolved is used. But hopefully it is not a big problem (it may be even better: “This question, written as unsolved on the poster, was solved just two days ago!”). – Tsuyoshi Ito Oct 9 '10 at 23:59
I'd suggest we add a category for questions that are really interesting and should be more well known. If people like that idea, I'd nominate cstheory.stackexchange.com/questions/871/… and cstheory.stackexchange.com/questions/2025/…, but they don't really fit any of the current categories. – Joshua Grochow Oct 11 '10 at 3:59
Along the lines @Joshua suggested, cstheory.stackexchange.com/questions/1699/… is a great question that deserves to be better known, and might interest FOCS regulars. – András Salamon Oct 13 '10 at 4:35
@Andras - but there's no answer. – Suresh Venkat Oct 13 '10 at 4:47
@Suresh: that's why I suggested it in a comment, it would be an example of an open question (doesn't fit into your 3 categories). – András Salamon Oct 13 '10 at 4:53
ah ok. i get it. – Suresh Venkat Oct 13 '10 at 5:02
@Suresh: Just saw your PDF. Very nice. I think maybe you should not have the answers. Maybe just a quick hint or something. This will make people actually come to cstheory looking for the answers. For example, for open problems you can mention that it is open. For yes/no questions, you could state the answer "yes" or "no" and ask the reader to visit cstheory for the full answer. (You can also mention who answered the question.) So for example, for Tsuyoshi's question about P, PH, etc., the answer would be "Yes," and it could say "answered by Scott Aaronson, Ravi Boppana and Joshua Grochow" – Robin Kothari Oct 21 '10 at 14:22
I could do the 'questions answered. in theory' tag line – Suresh Venkat Oct 21 '10 at 16:38
Looking good, and intriguing... – András Salamon Oct 21 '10 at 17:53
@Suresh Great work. Looks really well. – Joe Fitzsimons Oct 22 '10 at 18:55
I just wanted to thank Joshua, Aaron and others for helping out with this. I was told that many people would pull the little sheets out of their registration packets and start discussing the questions. So it was a success in that sense. – Suresh Venkat Oct 25 '10 at 7:39

16 Answers 16

I nominate Problems that can be used to show polynomial time hardness results. It's an interesting compilation and even a future reference for problems that people are ready to believe are hard.


A very popular question in Category 1 is Algorithms from the Book?

It is a soft question with a long list of great examples (currently 67 answers). It is sure to bring some visitors for this list alone.

This question certainly attracted a lot of attention. However, the quality of answers at cstheory.stackexchange.com/questions/1168/… or even cstheory.stackexchange.com/questions/174/… seems higher to me. – András Salamon Oct 13 '10 at 4:46

I also like the question on Max cut with negative edge weights, which is a very accessible question with a quite subtle reduction given by Peter Shor.


I think Laurent Bienvenu's answer to “Truly random number generator: Turing computable?” is one of the best examples of category 2 on the site. (Silly request: if you end up using it, perhaps you could edit out his reference to my name. I almost didn't nominate it for that reason, but decided I had to, because the answer was so good.)

I added the title of the question you linked to. I hope you do not mind. – Tsuyoshi Ito Oct 9 '10 at 18:58
I second this nomination. I was delighted to receive such a detailed and knowledgeable answer! – Joseph O'Rourke Oct 13 '10 at 23:49

For Category Three, I'd like to nominate the Magic is Turing Complete question. It's a little (by which I mean very) dorky, but reading it made me smile and smile, because of how enthusiastic everyone was.

Plus, extra points for the poster title "Magic is Turing Complete." :-)

+1. Very dorky, but very awesome nonetheless. (I don't know anything about MTG, but it looks really complex from the discussion.) – Robin Kothari Oct 9 '10 at 22:25
If you use this question, I recommend importing the newer, cleaner solution from Take3Cards. – Jeffε Oct 10 '10 at 7:41
As I commented to the question, the question is not about the Turing completeness of the game in the usual sense. I find the title of the question rather misleading. – Tsuyoshi Ito Oct 10 '10 at 11:26
@JeffE: where is the new clean soln ? – Suresh Venkat Oct 21 '10 at 8:48

For the converse of category 2 (that is, asked by an expert, answered by a graduate student): Ryan Williams' Which interesting theorems in TCS rely on the Axiom of Choice?, or maybe just the core question:

What is the most striking example in TCS that you know where [the axiom of choice is] required?

With Janne Korhonen's answer.

This was a really nice example. – András Salamon Oct 12 '10 at 9:02

A category 1 (community wiki) example with great, non-obvious answers is "Examples of the price of abstraction?"

This question also has a title that is intriguing. This might motivate people to look at the page just to find out what it is about. A shorter link: http://tinyurl.com/price-abstraction or http://cstheory.stackexchange.com/questions/608


I nominate Tsuyoshi's A decision problem which is not known to be in PH but will be in P if P=NP. The problem can be stated very concisely, as is needed since you wont have much space on a poster. Moreover, the question looks easy at first sight, but isn't really, making the reader start thinking on this. Whether or not the reader solves the problem, he/she will feel curious to know what the posted answers are and will come here to read the answers.

This probably falls in category 2, but it wasn't really a ref request.

Thanks for nomination. Honestly speaking, this is a little embarrassing because the question as is stated turned out to be very easy if you think about it in the right way…. But because many people seem to like the question (which I am happy about), I do not mind if the question is put on a poster. – Tsuyoshi Ito Oct 9 '10 at 18:50
@Tsuyoshi: But MANY hard things are easy if you "just" think about them the right way! – Daniel Apon Oct 14 '10 at 0:06
@Daniel: Fair enough. In fact, it may be arrogant of me to wish that my question had been harder than it turned out to be. At least I am happy that I received three answers from each of which I learned a new thing, and also I am happy that some people liked both the question and the answers. – Tsuyoshi Ito Oct 14 '10 at 1:16

Scott Aaronson's Circuit lower bounds over arbitrary sets of gates. Unfortunately both the question and the [accepted] answer are probably too long to play well on a poster. Maybe just the first two paragraphs (+ the next sentence) of the question, and some excerpt from the answer, though I'm having difficulty deciding what to excerpt. Maybe @András Salamon would like to provide a shorter version more suitable for a poster?

I'd be happy to compress Scott's question and the answers for a poster, if this is seen as suitable (it might be a bit too specialized). It certainly qualifies as useful for me personally -- trying to answer the question helped me to turn a few fragments into a more solid understanding. – András Salamon Oct 12 '10 at 8:59
andras, can you do the compression (see the format I proposed in the latest update) – Suresh Venkat Oct 21 '10 at 8:42
@Suresh: Hope the version I emailed you is appropriate. – András Salamon Oct 21 '10 at 13:14

A category 3 example is David Eppstein's question about Positive topological ordering. This was not only solved (19 days later), but generated a lot of interesting discussion and at least two follow-up questions by other people:


I really like the Multiplicative Version of 3SUM question: given a set of numbers, are there numbers $a$, $b$, $c$ in the set such that $ab=c$? It is very easy to understand, and just ever-so-slightly different from the infamous 3SUM problem that many know already.


Another question in category 2 is this one: Does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable?

Unfortunately it is not something that a general TCS person cares about (or understands). But it was answered by a top expert in the field, and indeed the OP mentioned that the OP had learnt the material after reading the same expert's lecture notes on the topic.


Regarding the layout of such a poster: I actually prefer ad campaigns consisting of several small posters, each in the same style but with different contents. Each time you see a new poster you think how clever it is, rather than just thinking "Oh, there's that same poster again that I've seen 5 times already."

I don't know if this is feasible or not given the physical layout of FOCS, since there's probably only one registration table and not really other opportunities to put up flyers. But even if you just have one pile of flyers spread out a little so people can see that there are in fact several distinct ones, that could work.

If so, then I'd suggest one question per page. The question big and bold, near the top (maybe use landscape layout), and the answer(s) in smaller text--probably necessary because the answer's tend to be longer--maybe with the most exciting/relevant part of the answer also in bold.

Oh, and of course, "cstheory.stackexchange.com" (perhaps plus a tag line, which doesn't have to be the same on each page) at the bottom. Doesn't have to be too large: once you hook 'em with the interesting Q&A, hopefully they'll be interested enough to find out what the flyer is about, regardless of how large or spiffy the URL is.

that's an interesting idea. so then make a number of these and even just tile them ? btw I have approval from the local organizers for a display – Suresh Venkat Oct 13 '10 at 18:22
+1: Great idea. Some people will be motivated to go around looking for all the posters to make sure they read all the questions. This might even generate discussion among the participants during coffee breaks. – Robin Kothari Oct 13 '10 at 19:21

An example from Category 3: Is it NP-hard to play international draughts correctly?


If this question will end up having a nice collection of the best questions from the site, then I recommend this question in category 1 (or 0).

I like the idea of self-reference :), but seriously, I do not think that it works because it is a meta question. Advertising that there are interesting questions about the website will not make people visit the website. – Tsuyoshi Ito Oct 9 '10 at 18:55
I thought that we would also include the answers, which would hopefully be a perfect summary of the best questions. – domotorp Oct 10 '10 at 6:19
I am not sure about that. I do not know the supposed size of the poster, but I was thinking of a letter-size paper, which is clearly too small to include any answers. – Tsuyoshi Ito Oct 10 '10 at 15:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .