With the STOC deadline passing on Monday, now is a good time to look at the arXiv to see what has been posted since then. Hamid Jahanjou, Eric Miles and Emanuele Viola have a new paper, Local Reductions, that gives a new reduction from NTIME(t) to 3-SAT formulas of size t polylog(t). The twist to their new reduction: there is an NC0 circuit C that maps the number i to the ith clause. NC0 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 ACC0 ≠ 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