Computational Complexity, Volume 5

Volume 5, Number 1, 1995

• Nick Littlestone, Philip M. Long, Manfred K. Warmuth: On-line Learning of Linear Functions. 1-23 BibTeX
• György Turán: On the Complexity of Planar Boolean Circuits. 24-42 BibTeX
• Benny Chor, Netta Shani: The Privacy of Dense Symmetric Functions. 43-59 BibTeX
• Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman: Derandomized Graph Products. 60-75 BibTeX
• Keju Ma, Joachim von zur Gathen: The Computational Complexity of Recognizing Permutation Functions. 76-97 BibTeX

Volume 5, Number 2, 1995

• Johan Håstad, Stasys Jukna, Pavel Pudlák: Top-Down Lower Bounds for Depth-Three Circuits. 99-112 BibTeX
• Faith E. Fich, Miroslaw Kowaluk, Miroslaw Kutylowski, Krzysztof Lorys, Prabhakar Ragde: Retrieval of Scattered Information by EREW, CREW, and CRCW PRAMs. 113-131 BibTeX
• Alain P. Hiltgen, Mike Paterson: PI_k Mass Production and an Optimal Circuit for the Neciporuk Slice. 132-154 BibTeX
• Carme Àlvarez, Birgit Jenner: A Note on Logspace Optimization. 155-166 BibTeX
• Meera Sitharam: Evaluating Spectral Norms for Constant Depth Circuits with Symmetric Gates. 167-189 BibTeX

Volume 5, Number 3/4, 1995

• Mauricio Karchmer, Ran Raz, Avi Wigderson: Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. 191-204 BibTeX
• Ran Raz: Fourier Analysis for Probabilistic Communication Complexity. 205-221 BibTeX
• Thomas Lickteig, Kai Werther: How can a Complex Square Root be Computed in an Optimal Way. 222-236 BibTeX , Correction: Computational Complexity 6(1): 100 (1996/1997)
• Ueli M. Maurer: On the Oracle Complexity of Factoring Integers. 237-247 BibTeX
• Meera Sitharam: Pseudorandom Generators and Learning Algorithms for AC^0. 248-266 BibTeX
• David W. Juedes: Weakly Complete Problems are not Rare. 267-283 BibTeX