16
$\begingroup$

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.

$\endgroup$
26
  • $\begingroup$ 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/… $\endgroup$ Oct 9, 2010 at 2:01
  • 4
    $\begingroup$ 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. $\endgroup$ Oct 9, 2010 at 14:15
  • 8
    $\begingroup$ 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). $\endgroup$ Oct 9, 2010 at 21:04
  • $\begingroup$ another nice idea...I like both those questions myself.. $\endgroup$ Oct 9, 2010 at 21:20
  • $\begingroup$ 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!”). $\endgroup$ Oct 9, 2010 at 23:59
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 11, 2010 at 3:59
  • $\begingroup$ 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. $\endgroup$ Oct 13, 2010 at 4:35
  • $\begingroup$ @Andras - but there's no answer. $\endgroup$ Oct 13, 2010 at 4:47
  • $\begingroup$ @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). $\endgroup$ Oct 13, 2010 at 4:53
  • $\begingroup$ ah ok. i get it. $\endgroup$ Oct 13, 2010 at 5:02
  • $\begingroup$ @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" $\endgroup$ Oct 21, 2010 at 14:22
  • 2
    $\begingroup$ I could do the 'questions answered. in theory' tag line $\endgroup$ Oct 21, 2010 at 16:38
  • 2
    $\begingroup$ Looking good, and intriguing... $\endgroup$ Oct 21, 2010 at 17:53
  • 1
    $\begingroup$ @Suresh Great work. Looks really well. $\endgroup$ Oct 22, 2010 at 18:55
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 25, 2010 at 7:39

16 Answers 16

15
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
1
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ I added the title of the question you linked to. I hope you do not mind. $\endgroup$ Oct 9, 2010 at 18:58
  • $\begingroup$ I second this nomination. I was delighted to receive such a detailed and knowledgeable answer! $\endgroup$ Oct 13, 2010 at 23:49
6
$\begingroup$

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." :-)

$\endgroup$
5
  • $\begingroup$ +1. Very dorky, but very awesome nonetheless. (I don't know anything about MTG, but it looks really complex from the discussion.) $\endgroup$ Oct 9, 2010 at 22:25
  • $\begingroup$ If you use this question, I recommend importing the newer, cleaner solution from Take3Cards. $\endgroup$
    – Jeffε
    Oct 10, 2010 at 7:41
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 10, 2010 at 11:26
  • $\begingroup$ @JeffE: where is the new clean soln ? $\endgroup$ Oct 21, 2010 at 8:48
  • $\begingroup$ @Suresh: draw3cards.com/questions/2851/is-magic-turing-complete/… $\endgroup$
    – Jeffε
    Oct 23, 2010 at 21:04
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This was a really nice example. $\endgroup$ Oct 12, 2010 at 9:02
6
$\begingroup$

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 Examples of the price of abstraction?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 9, 2010 at 18:50
  • $\begingroup$ @Tsuyoshi: But MANY hard things are easy if you "just" think about them the right way! $\endgroup$ Oct 14, 2010 at 0:06
  • $\begingroup$ @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. $\endgroup$ Oct 14, 2010 at 1:16
5
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 12, 2010 at 8:59
  • $\begingroup$ andras, can you do the compression (see the format I proposed in the latest update) $\endgroup$ Oct 21, 2010 at 8:42
  • $\begingroup$ @Suresh: Hope the version I emailed you is appropriate. $\endgroup$ Oct 21, 2010 at 13:14
5
$\begingroup$

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:

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Collecting together some of the comments suggesting open questions (including those by Tsuyoshi and Joshua):

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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 $\endgroup$ Oct 13, 2010 at 18:22
  • 1
    $\begingroup$ +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. $\endgroup$ Oct 13, 2010 at 19:21
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 9, 2010 at 18:55
  • $\begingroup$ I thought that we would also include the answers, which would hopefully be a perfect summary of the best questions. $\endgroup$
    – domotorp
    Oct 10, 2010 at 6:19
  • $\begingroup$ 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. $\endgroup$ Oct 10, 2010 at 15:02

You must log in to answer this question.

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