ACM DL

Computation Theory (TOCT)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computation Theory (TOCT), Volume 1 Issue 1, February 2009

Editor’s Foreword
Lance Fortnow
Article No.: 1
DOI: 10.1145/1490270.1490271

Algebrization: A New Barrier in Complexity Theory
Scott Aaronson, Avi Wigderson
Article No.: 2
DOI: 10.1145/1490270.1490272

Any proof of P ≠ NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (e.g., that PP does not have linear-size circuits) that overcome...

A Simple Proof of Bazzi’s Theorem
Alexander Razborov
Article No.: 3
DOI: 10.1145/1490270.1490273

Linial and Nisan [1990] asked if any polylog-wise independent distribution fools any function in AC0. In a recent remarkable development, Bazzi solved this problem for the case of DNF formulas. The aim of this note is to present a...

Directed Planar Reachability Is in Unambiguous Log-Space
Chris Bourke, Raghunath Tewari, N. V. Vinodchandran
Article No.: 4
DOI: 10.1145/1490270.1490274

We make progress in understanding the complexity of the graph reachability problem in the context of unambiguous logarithmic space computation; a restricted form of nondeterminism. As our main result, we show a new upper bound on the directed...