Skip to content

Theory Fest—Should You Go?

April 20, 2017

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.

Turing Award 2016

April 7, 2017

It takes a …

Sir Tim Berners-Lee is the latest winner of the ACM Turing Award. He was cited for “inventing the World Wide Web (WWW), the first web browser, and the fundamental protocols and algorithms allowing the web to scale.”

Today we congratulate Sir Tim on his award and review the work by which the Web flew out and floated wide.
Read more…

The End Of Human Science?

April 1, 2017

Could we go the way of telegraph operators?

Pixabay source

Lofa Polir has sent us some new information that will have widespread ramifications for math and theory and science in general.

Today Ken and I wish to comment on this information.

Polir is sure that this information is correct. If he is correct the consequences for all will be immense.

Read more…

Gender Bias: It Is Worse Than You Think

March 28, 2017

Science meets bias and diversity

Deborah Belle is a psychology professor at Boston University (BU) who is interested in gender differences in social behavior. She has reported a shocking result about bias.

Today I thought I would discuss the issue of gender bias and also the related issue of the advantages of diversity.
Read more…

Leprechauns are Multiplying

March 17, 2017

Littlewood’s Law and Big Data

“Leprechaun-proofing” data source

Neil L. is a leprechaun. He has visited Dick on St. Patrick’s Day or the evening before many times. Up until this night I had never seen him.

Today, Neil’s message is more important than ever.
Read more…

Is Computer Security Possible?

March 8, 2017

The breaks keep on coming…

Holly Dragoo, Yacin Nadji, Joel Odom, Chris Roberts, and Stone Tillotson are experts in computer security. They recently were featured in the GIT newsletter Cybersecurity Commentary.

Today, Ken and I consider how their comments raise a basic issue about cybersecurity. Simply put:

Is it possible?

Read more…

Working Backward

February 27, 2017

With a little more from Smullyan

YouTube source

Maurice Ashley is an American chess grandmaster. He played for the US Championship in 2003. He coached two youth teams from Harlem to national championships and played himself in one scene of the movie Brooklyn Castle. He created a TEDYouth video titled, “Working Backward to Solve Problems.”

Today we discuss retrograde analysis in chess and other problems, including one of my own.
Read more…