Local Reductions

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.