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
  

Last update Mon May 20 16:33:41 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page