The ACM Transactions on Computation Theory has published its first issue with three exciting papers: - Algebrization: A New Barrier in Complexity Theory byMessage 1 of 1 , Apr 2, 2009View SourceThe ACM Transactions on Computation Theory has published its first issue with three exciting papers:
This is just the start of what is becoming a strong journal. Submit your papers and join the fun.
- Algebrization: A New Barrier in Complexity Theory by Aaronson and Wigderson.
- Scott and Avi's new take on relativization.
- A Simple Proof of Bazzi's Theorem by Razborov.
- A short proof that polylog independence fools DNFs. Precursor to Braverman's new result.
- Directed Planar Reachability Is in Unambiguous Log-Space by Bourke, Tewari and Vinodchandran.
- Roughly, given a map with one-way streets, you can nondeterministically find a unique route from point A to point B if one exists.
Posted By Lance to Computational Complexity at 4/02/2009 07:33:00 AM