FCRC Complexity

On Wednesday at FCRC, the Complexity, STOC and EC (Economics and Computation) conferences all have sessions, a smorgasbord of talks, but tough decisions on what session to attend. Here's one you might have misses, the EC paper Why Prices Need Algorithms by Roughgarden and Talgam-Cohen that has a nice application of complexity to the existence of equilibrium, not whether the equilibrium is hard to compute but whether it exists.

Roughly Roughgarden and Talgam-Cohen show if a certain kind of a pricing equilibrium holds then one can get an efficient algorithm for a certain kind of reduction. Under reasonable complexity assumptions (like P <> NP) such reductions can't exist and so neither can the equilibrium.

Late Wednesday came the Complexity business meeting, the first open business meeting of the now unaffiliated Computational Complexity Conference. There were 84 attendees, a little bit down from last FCRC but higher than last year. There were 30 papers accepted out of 110 submissions. The 2016 conference will be held in Tokyo May 29-June 1.

There was much discussion on where Complexity will be in 2017 and on which journal will get the special issue for the next three years. Watch my twitter to see when they get set.