Theoretical Computer Science, Volume 157

Volume 157, Number 1, 9 April 1996

• Manuel Bronstein, Marko Petkovsek:
  An Introduction to Pseudo-Linear Algebra. 3-33
  
• Olivier Devillers:
  An Introduction to Randomization in Computational Geometry. 35-52
  
• Yoram Elichai, Yosi Yomdin:
  Flexible High-Order Discretization of Geometric Data for Global Motion Planning. 53-77
  
• Dima Grigoriev:
  NC Solving of a System of Linear Ordinary Differential Equations in Several Unknowns. 79-90
  
• Dima Grigoriev, Marek Karpinski:
  Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. 91-99
  
• Jean-Paul Laumond, Jean-Jacques Risler:
  Nonholonomic Systems: Controllability and Complexity. 101-114
  
• Jean Moulin Ollagnier:
  Algorithms and Methods in Differential Algebra. 115-127
  
• Jean-Jacques Risler:
  A Bound for the Degree of Nonholonomy in the Plane. 129-136
  

Volume 157, Number 2, 5 May 1996

• Farid M. Ablayev:
  Lower Bounds for One-Way Probabilistic Communication Complexity and Their Application to Space Complexity. 139-159
  
• Dima Burago, Michel de Rougemont, Anatol Slissenko:
  On the Complexity of Partially Observed Markov Decision Processes. 161-183
  
• Dima Grigoriev, Nicolai Vorobjov:
  Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates. 185-214
  
• Alexander V. Karzanov:
  How to Tidy up a General Set-System by Use of Uncrossing Operations. 215-225
  
• Andrei A. Muchnik, Nikolai K. Vereshchagin:
  A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes. 227-258
  
• Marek Karpinski, Igor Shparlinski:
  On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields. 259-266
  
• Leonid A. Levin:
  Computational Complexity of Functions. 267-271
  
• Igor Shparlinski:
  On Finding Primitive Roots in Finite Fields. 273-275
  
• Oleg Verbitsky:
  Towards the Parallel Repetition Conjecture. 277-282