Annual IEEE Conference on Computational Complexity : San Diego, CA - 2007

Papers from a June 2007 conference shed light on recent work in areas such as halfspace matrices, time-space tradeoffs for counting NP Solutions modulo integers, unbalanced expanders and randomness extractions from Parvesh-Vardy codes, and quantum versus classical proofs and advice. Other topics examined include approximate majority and probabilistic time, the complexity of polynomials and their coefficient functions, a linear round lower bound for Lovasz- Schrijver SDP relaxations of vertex cover, and directed planar reachability in unambiguous log-space. Heuristic time hierarchies, mathgate computations, a new interactive hashing theorem, and parity problems in planar graphs are some other subjects explored.Annual IEEE Conference on Computational Complexity : San Diego, CA - 2007, 22 was published 2007 under ISBN 9780769527802 and ISBN 0769527809.