Zap. Nauchn. Sem. POMI, 2012, Volume 399

Zapiski Nauchnykh Seminarov POMI

RUS ENG

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

2012, Volume 399

Contents

Computational complexity theory. Part X

	A new upper bound for $(n,3)$-MAX-SAT I. A. Bliznets		5–14
	Optimal heuristic algorithms for the image of an injective function E. A. Hirsch, D. M. Itsykson, V. O. Nikolaenko, A. V. Smal		15–31
	Feebly secure cryptographic primitives E. A. Hirsch, O. Melanich, S. I. Nikolenko		32–64
	Circuit complexity of linear functions: gate elimination and feeble security A. P. Davydow, S. I. Nikolenko		65–87
	The complexity of inversion of explicit Goldreich's function by DPLL algorithms D. M. Itsykson, D. O. Sokolov		88–108
	Diophantine hierarchy A. A. Knop		109–127