^{0}circuit C that maps the number i to the ith clause. NC

^{0}means every output bit depends on only a constant number of input bits. The proof uses old-fashioned parallel routing.

Should have some interesting applications. It does save a step in Williams' proof that ACC

^{0}≠ NEXP but the combined proofs are longer.

In other news, I've been getting several email from other CS chairs looking for students to hire as faculty in their departments. The latest CRA News is 59 pages, 50 of them are faculty job ads. It's a good year to be on the job market.

The combined proofs are not longer. You do not need the full constant-locality result to simplify the proof of the ACC^0 lower bound. Also, locality considerations aside, the reduction presented in the paper is arguably simpler than the one used as a black-box in the ACC^0 lower bound. This is discussed in the paper.

ReplyDeleteIn terms of simplifying William's proof, Igor Oliveira's survey (ECCC TR13-177 http://eccc.hpi-web.de/report/2013/117/) contains a fairly simple and clean (and as far as I can tell, new) proof of the SAT-algorithms vs lbs connection, that in particular scales well with circuit depth as the Jahanjou-Miles-Viola result does.

ReplyDeleteFYI: http://eccc.hpi-web.de/report/2013/099/

ReplyDelete