Theoretical Computer Science, Volume 157

Volume 157, Number 1, 9 April 1996

Algorithmic Complexity of Algebraic and Geometric Models

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

Complexity Theory and the Theory of Algorithms as developed in the CIS

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