Thursday, February 19, 2015

And the Winners Are...

[Shortly after this post went up, STOC announced their accepted papers as well]

I always like that the announcement of accepted papers for the Computational Complexity Conference happens around the time of the Academy Awards. These acceptances are the Oscars for our community that shares its name with this conference and the blog.

The title that interests me is Identifying an honest EXP^NP oracle among many by Shuichi Hirahara since it seems closely related to some of my own research. Not only cannot I not find the paper online, I can't even find the author's email. Shuichi, if you reading this, please send me a copy of your paper.

Luckily not all papers are so elusive. Murray and Williams show that proving the NP-hardness of computing the circuit complexity would require proving real complexity class separation results. Oliveira and Santhanam give tight lower bounds on how much you can compress majority so that you can compute it with constant-depth circuits. A different Oliveira has two papers in the conference, a solely authored paper showing that polynomials of low individual degree with small low-depth arithmetic circuits have factors similarly computable, and a paper with Shpilka and Volk on hitting sets for bounded-depth multilinear formula. A hitting set is a small easily and deterministically computable set that contains, for every such arithmetic circuit, an input with a non-zero output.

Many more interesting papers and you can see them all at the conference in Portland, this year part of the Federated Computing Research Conference which includes STOC, SPAA and EC, which now stands for Economics and Computation. My tip: book your hotels now, they fill up fast.


  1. Shouldn't you say "...and the CCC presentation slots goes to..."

  2. Was there any noticeable change this year from previous years, after the separation from IEEE? It is probably unrelated to this separation, but I think that this year CCC had more submissions than usual.

  3. "Murray and Williams show shows that proving the NP-hardness..."
    No typo there?

    P = NP has been fascinating for me. It strucks me how difficult it is to even formally prove that there is no polynomial time algorithm (with 100% certainty) for a problem, apart from problems consiting in enumerating all cases of something e.g. all subsets of a n-element set.

  4. Accepted papers for STOC have also been announced: