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
• György Turán: On the Complexity of Planar Boolean Circuits. 24-42
• Benny Chor, Netta Shani: The Privacy of Dense Symmetric Functions. 43-59
• Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman: Derandomized Graph Products. 60-75
• Keju Ma, Joachim von zur Gathen: The Computational Complexity of Recognizing Permutation Functions. 76-97

Volume 5, Number 2, 1995

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

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
• Ran Raz: Fourier Analysis for Probabilistic Communication Complexity. 205-221
• Thomas Lickteig, Kai Werther: How can a Complex Square Root be Computed in an Optimal Way. 222-236 , Correction: Computational Complexity 6(1): 100 (1996/1997)
• Ueli M. Maurer: On the Oracle Complexity of Factoring Integers. 237-247
• Meera Sitharam: Pseudorandom Generators and Learning Algorithms for AC^0. 248-266
• David W. Juedes: Weakly Complete Problems are not Rare. 267-283