"Zapiski Nauchnyh Seminarov POMI"
VOL. 316
This issue is entitled "Computational complexity theory. Part IX"
editor E.A.Hirsch
Contents
- Ayad A. Complexity bound of absolute factoring of
parametric polynomials
.......5
(.ps.gz)
- Bargachev V.
On some properties of min-wise independent
families and groups of permutations
.......30
(.ps.gz)
- Basu S., Pollack R., Roy M.-F. Computing the dimension
of a semi-algebraic set
.......42
(.ps.gz)
- Evdokimov S. A., Ponomarenko I. N.
On the vertex connectivity of a relation in association scheme
.......55
(.ps.gz)
- Kreinovich V., Finkelstein A. M. Towards applying computational complexity to
foundations of physics
.......63
(.ps.gz)
- Kulikov A. S., Fedin S. S.
Automated proofs of upper bounds on the running time of splitting algorithms
.......111
(.ps.gz)
- Mints G., Kojevnikov A. Intuitionistic Frege systems are
polynomially equivalent
.......129
(.ps.gz)
- Orevkov V. P.
A new decidable Horn fragment of the predicate calculus
.......147
(.ps.gz)
- Pan V. Y. On theoretical and practical acceleration of
randomized computation of the determinant of an integer matrix
.......163
(.ps.gz)
- Paturi R., Pudl\'ak P. Circuit lower bounds and linear codes
.......188
(.ps.gz)
- Finkel O., Ressayre J.-P., Simonnet P. On infinite real trace rational languages
of maximum topological complexity
.......205
(.ps.gz)
- Reviews .......224
(.ps.gz)
Paging: 229 pp.
-
Language: Russian
Back to the Petersburg Department of
Steklov Institute of Mathematics