Zap. Nauchn. Sem. POMI, 2004, Volume 316

RUS ENG

JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

2004, Volume 316

|

General information

|

Contents

|

Computational complexity theory. Part IX

	Complexity bound of absolute factoring of parametric polynomials A. Ayad		5
	On some properties of min-wise independent families and groups of permutations V. Bargachev		30
	Computing the dimension of a semi-algebraic set S. Basu, R. Pollack, M.-F. Roy		42
	On the vertex connectivity of a relation in association scheme S. A. Evdokimov, I. N. Ponomarenko		55
	Towards Applying Computational Complexity to Foundations of Physics V. Kreinovich, A. M. Finkelstein		63
	Automated proofs of upper bounds on the running time of splitting algorithms A. S. Kulikov, S. S. Fedin		111
	Intuitionistic frege systems are polynomially equivalent G. Mints, A. A. Kojevnikov		129
	A new decidable Horn fragment of the predicate calculus V. P. Orevkov		147
	On theoretical and practical acceleration of randomized computation of the determinant of an integer matrix V. Ya. Pan		163
	Circuit lower bounds and linear codes R. Paturi, P. Pudlák		188
	On infinite real trace rational languages of maximum topological complexity O. Finkel, J.-P. Ressayre, P. Simonnet		205

© Steklov Math. Inst. of RAS, 2025