## Computational Complexity: Proceedings : Fourteenth Annual IEEE Conference on Computational Complexity : May 4-6, 1999, Atlanta, Georgia, USASix of the 28 papers chosen for presentation and publication were also chosen for the joint STOC/Complexity session, and so are presented in full in that proceedings and only by abstracts here. Only abstracts and references are provided for the two invited talks as well. Among the topics of the full papers are a lower bound for primality, computing from partial solutions, the complexity of solving equations over finite groups, the expected size of Heilbronn's triangles, quantum branded query complexity, deterministic amplification of space-bounded probabilistic undirected graph connectivity, the shortest lattice vector problem, and complicated complementations. No subject index. Annotation copyrighted by Book News, Inc., Portland, OR |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Pseudorandom Generators without the XOR Lemma | 4 |

A Lower Bound for Primality | 10 |

On Monotone Planar Circuits | 24 |

Copyright | |

18 other sections not shown

### Other editions - View all

### Common terms and phrases

ACM Symposium afﬁne Ajtai algorithm ampliﬁcation assume basis Boolean function complexity classes Computational Complexity Computer Science conﬁguration constant construction Corollary deﬁne Deﬁnition denote dimension distribution efﬁcient encoding equations erasure code exists exponential extractors factor fan-in ﬁeld ﬁnd ﬁnite ﬁrst ﬁxed fonnula formula Fortnow gates given Goldreich graph hierarchy inﬁnite input integer interactive proof systems Kolmogorov complexity lattice point least Lemma linear linear span logspace lower bound matrix nodes NP-complete NP-hard O(log obtain oracle orthogonal pebbles polynomial polynomial hierarchy polynomial-time predicate probabilistic probability Proc promise problem proof of Theorem proof system protocol prove PSPACE public-coin quantum computation queries random bits reduction result Sample satisﬁes satisfying assignment Section sequence shortest vector simulator solution space space-bounded Speciﬁcally stratiﬁed subset subset sum problem subspace sufﬁciently Theory of Computing tion Turing machine upper bound variables veriﬁer zero-knowledge