ACM Transactions on Computation Theory (TOCT), Volume 1

Volume 1, Number 1, February 2009

• Lance Fortnow:
  Editor's Foreword.
  
• Scott Aaronson, Avi Wigderson:
  Algebrization: A New Barrier in Complexity Theory.
  
• Alexander A. Razborov:
  A Simple Proof of Bazzi's Theorem.
  
• Chris Bourke, Raghunath Tewari, N. V. Vinodchandran:
  Directed Planar Reachability Is in Unambiguous Log-Space.
  

Volume 1, Number 2, September 2009

• Matei David, Toniann Pitassi, Emanuele Viola:
  Improved Separations between Nondeterministic and Randomized Multiparty Communication.
  
• Venkatesan Guruswami, Prasad Raghavendra:
  Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.
  
• Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah:
  Sound 3-Query PCPPs Are Long.
  

Volume 1, Number 3, March 2010

• Jan Kyncl, Tomás Vyskocil:
  Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case.
  
• Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
  Formula Caching in DPLL.
  
• Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan:
  Planarity, Determinants, Permanents, and (Unique) Matchings.
  

Last update Wed Feb 15 05:46:03 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page