Theory Fest—Should You Go?

Boaz Barak and Michael Mitzenmacher are well known for many great results. They are currently working not on a theory paper, but on a joint “experiment” called Theory Fest.

Today Ken and I want to discuss their upcoming experiment and spur you to consider attending it.

There are many pros and some cons in attending the new Theory Fest this June 19-23. One pro is where it is being held—Montreal—and another is the great collection of papers that will appear at the STOC 2017 part of the Fest. But the main ‘pro’ is that Boaz and Mike plan on doing some special events to make the Fest more than just a usual conference on theory.

The main ‘con’ is that you need to register soon here, so do not forget to do that.

## Possible New Activities

We humbly offer some suggestions to spice up the week:

${\bullet}$ A Bug-a-thon: Many conferences have hack-a-thons these days. A theory version could be a P=NP debugging contest. Prior to the Fest anyone claiming to have solved P vs NP must submit a paper along with a \$100 fee– -Canadian. At the Fest teams of “debuggers” would get the papers and have a fixed time—say three hours—to find a bug in as many papers as they can. The team that debugs the most claims wins the entrance fees.

Note that submissions can be “stealth”—you know your paper is wrong, but the bugs are very hard to find.

${\bullet}$ Present a Paper: People submit a deck for a ten minute talk. Then randomly each is assigned a deck and they must give a talk based only on the deck. There will be an audience vote and the best presenter will win a trophy.

Note there are two theory issues. The random assignment must be random but fixed-point free—-no one can get their own deck. Also since going last seems to give an unfair advantage, we suggest that each person gets the deck only ten minutes before their talk. Thus all presenters would have the same time to prepare for their talk.

${\bullet}$ Silent Auction For Co-authorship: We will set up a series of tables. On each table is a one page abstract of a paper. You get to bid as in a standard silent auction. The winner at each table becomes a co-author and pays their bid to STOC. The money could go to a student travel fund.

${\bullet}$ The A vs B Debate: Theory is divide into A and B at least in many conferences. We will put together a blue ribbon panel and have them discuss: Is A more important than B? We will ask that the panel be as snippy as possible—a great evening idea while all drink some free beer.

${\bullet }$ Betting: We will have a variety of topics from P=NP to quantum computation where various bets can be made.

${\bullet}$ Cantal Complexity: The Fest will mark the 40th anniversary of Donald Knuth’s famous paper, “The Complexity of Songs.” Evening sessions at a pub will provide unprecedented opportunity for applied research in this core area. Ken’s research, which he began with Dexter Kozen and others at the ICALP 1982 musicfest, eventually led to this.

${\bullet}$ Lemmas For Sale: In an Ebay-like manner a lemma can be sold. We all have small insights that we will never publish, but they might be useful for others.

${\bullet}$ Zoo Excursion: This is not to the Montreal zoo—which is rather far—but to the Complexity Zoo which is housed elsewhere in Canada. Participants will take a virtual tour of all 535 classes. The prize for “collapsing” any two of them will be an instant STOC 2017 publication. In case of collapsing more than two, or actually finding a new separation of any pair of them, see under “Bug-a-thon” above.

${\bullet}$ Write It Up: This is a service-oriented activity. Many results never have been written up formally and submitted to journals. Often the reason is that the author(s) are busy with new research. This would be a list of such papers and an attempt to get students or others to write up the paper. This has actually happen many times already in an informal manner. So organizing it might be fun. We could use money to get people to sign up—or give a free registration to next years conference— for example.

## Open Problems

GLL plans on gavel-to-gavel coverage of the Fest: we hope to have helpers that will allow us to make at least one post per day about the Fest. Anyone interested in being a helper should contact us here.

This will be especially appreciated because Ken will be traveling to a different conference in a voivodeship that abuts an oblast and two voblasts.

April 21, 2017 4:23 am

Another “con”: LCC and LICS will take place in the same time, not too far away (Reykjavik).

2. April 21, 2017 10:29 am

Thank you so much for writing this. As much as I’d like to take credit to what I hope and expect will be a great event, TheoryFest is organized by many people, and in particular Sanjeev Arora chairs the organizing committee, Valerie King is the PC chair, Hamed Hatami and Pierre McKenzie are the local chairs while Tim Roughgarden and Avrim Blum chaired the committees for keynotes/tutorials and workshops respectively.

I hope many people come and also provide feedback so this can become a great and beneficial tradition.

• April 21, 2017 10:31 am

P.s. There are many others I didn’t list,see
http://acm-stoc.org/stoc2017/
but in particular many thanks are due to Paul Beame who has done everything from helping select invited talks to working on the website.

3. April 21, 2017 5:05 pm

Thanks to Boaz, Michael and all the other people involves in this year’s Theory Fest! It promises to be a very interesting event and I am glad to see that it will also have some representation from Theory B. Pity about the clash with LICS and its seven co-located workshops in Reykjavik, but so be it.

In my, admittedly biased, opinion as former president of the EATCS, there is another Theory Fest that has been running for many years, namely ICALP. I hope that the two events can learn something from one another. The presidents of the EATCS and the chairs of SIGACT have been cooperating for some time, as the chair of SIGACT is an appointed member of the EATCS Council. I like to think that further cooperation, and exchange of information and experiences will benefit the TCS community as a whole.

April 21, 2017 6:01 pm

I would first like to echo Boaz, that this is a large team effort — many people are working to make this a success.

Second, having attended ICALP last year in Rome, I would say that I think ICALP is fantastic, and there should be plenty of ways for both to learn from each other and grow together.

Third, with regard to LICS, all I can say is that it wasn’t desirable, but scheduling conferences over the summer is a very complex problem.

5. April 24, 2017 2:03 am

I am not happy with the co-authorship auction. As someone with Erdos number n, I was once approached out of the blue by someone who was desperate to get Erdos number n+1, and begged me to put his name on my next paper, no matter what the subject.

I believe that any author should take responsibility for everything in the paper, so I have a counter-suggestion. Why not combine the co-authorship auction with the bug-a-thon? Anyone who can find and fix a bug in my paper is very welcome to be a co-author!

6. May 18, 2017 8:43 am