Nikolai N. Kuzjurin

ADDRESS

Institute for System Programming,
Russian Academy of Sciences (RAS)
B. Communisticheskaja, 25, Moscow, 109004, Russia
Ph. (007)(095)912-56-59
FAX (007)(095)912-15-24
E-mail: nnkuz@ispras.ru

Current position:

Head of the Department of Mathematical Metods and Algorithms

PERSONAL

Date of birth: July 7, 1952
Place of birth: Moscow, USSR
Nationality: Russian

EDUCATION

1969 - 1974 Moscow State University, Department of Computational
Mathematics and Cybernetics, MS in Mathematics, 1974.
1974 - 1977 Postgraduate, Moscow State University, Department of
Computational Mathematics and Cybernetics.

Degrees

1980, Ph.D. in Math., Computer Center of Academy of Sciences of the USSR
1997, Doctor of Sciences in Math., Computer Center of Russian Academy of Sciences

EMPLOYMENT

1999 -- present
Professor, Department of Mathematics, High School of Economics (HSE State University)
1996 -- present
Head of the Department of Mathematical Metods and Algorithms
Institute for System Programming RAS
1993 - 1996
Leading Researcher, Institute for System Programming RAS
1984 - 1993
Senior Researcher, Institute for Cybernetics Problems RAS
1982 - 1984
Researcher, Institute for Cybernetics Problems, USSR Academy of Sciences
1978 - 1982
Researcher, Scientific Council on Cybernetics, USSR Academy of Sciences

AREAS OF INTEREST

Discrete Mathematics and Theoretical Computer Science:
combinatorics, hypergraphs, packing and covering problems, partially ordered sets, probabilistic methods, randomized and approximation algorithms, derandomization technique, complexity of algorithms, communication complexity, integer and linear programming.

RESEARCH ACTIVITIES

Packing and covering problems
My results include finding a sharp threshold on k for which asymptotically good packings and coverings of l-subsets by k-subsets of an n-set exist.
Explicit constructions
My recent results include explicit constructions of asymptotically good packings and coverings.
Hypergraphs
My recent results include exact bounds of the number of nearly perfect matchings in almost regular hypergraphs satisfying the conditions of Pippenger-Spencer theorem (joint work with Armen Asratian).
Partially ordered sets
An asymptotics of the width of the Cartesian product of partially ordered sets was obtained (joint work with Konrad Engel).
(0,1)-matrices
I found an asymptotics of the maximum $\alpha$-height of (0,1)-matrices from Ryser's classes.
Derandomization technique
I developed a general method showing how to obtain deterministic approximation algorithms using derandomization in integer programming and proposed a variant of the method of conditional probabilities which doesn't use Raghavan's pessimistic estimators.
Approximations in integer linear programming
I developed a polynomial deterministic algorithm which is based on derandomization technique and provides finding near optimal solutions to covering integer linear programs. I obtained general bounds of the ratio of optima of integer linear programs and their linear relaxations.

PUBLICATIONS:

More than 50 papers and preprints.

List of Publications

VISITS

• Lulea University, Sweden (03-04/2001, 03-06/1999, 08-09/1998)
• Nortel Networks, Ottawa, Canada (10/2000)
• Cloakware Corporation, Ottawa, Canada (02/2000, 08/2000)
• Bielefeld University, Germany (10-11/1997)
• Banach Center of Mathematics, Warsaw, Poland (08/1996, 09/1987, 02/1985)
• Institute of Mathematics, Buadapest (12/1994)
• Institute of Technical Cybernetics, Bratislava (05-06/1990)
• University of Rostock, Germany (05-06/1982)