'; print ''; ?>

Sergey Nikolenko

Sergey Nikolenko

Main pageBooks'; print '
Research papers'; print '
Talks and posters'; print '
Students'; print '
Popular science'; print '
Other stuff'; print '

   Research'; print '
CS and crypto'; print '
Bioinformatics'; print '
Machine learning'; print '
Algebraic geometry'; print '
Algebra'; print '
Bayesian networks'; print '
Earth sciences'; print '

   Teaching'; print '
 2014'; print '
ML, KFU'; print '
Game Theory, HSE'; print '
Mech. Design, HSE'; print '
ML, CSClub Kazan'; print '
Game theory, HSE'; print '
Math. logic, AU'; print '
Machine learning, STC'; print '
Machine learning, AU'; print '
 2013'; print '
Discrete math, HSE'; print '
Machine learning, STC'; print '
Math. logic, AU'; print '
Cryptography, AU'; print '
 2012'; print '
Machine learning, STC'; print '
Math. logic, AU'; print '
Machine learning II, AU'; print '
Machine learning, AU'; print '
Machine learning, EMC'; print '
 2011'; print '
Cryptography, AU'; print '
Math. logic, AU'; print '
Machine learning, AU'; print '
 2010'; print '
Math. logic, AU'; print '
Machine learning, AU'; print '
Cryptography, AU'; print '
 2009'; print '
Crypto in CS Club'; print '
Statistics'; print '
Machine learning, AU'; print '
Cryptography'; print '
 2008'; print '
Speech recognition'; print '
MD for CS Club'; print '
ML for CS Club'; print '
Mechanism design'; print '
 2007'; print '
Machine Learning'; print '
Probabilistic learning'; print '

  External links'; print '
Google Scholar profile'; print '
DBLP profile'; print '
LiveJournal account
userinfonikolenko (in Russian)

Theoretical computer science

Bio excerpt

I began with SAT algorithms, their upper/lower bounds and stuff like that. It pleases me to believe that I (in co-authoring with Alexander Sirotkin) was the first to actually implement an automated system to prove upper bounds for DPLL-like algorithms (a work later perfected by Alexander Kulikov who made a generalized program that could work with many other combinatorial problems).

A long period of work devoted to proof systems followed. It mainly consisted of programming and dealt with two Intel-sponsored CRDF projects, one for a SAT solver, and another for a first-order theorem prover. Theoretically, my only result was a simulation of the Cutting Planes with restricted degree of falsity by Resolution (co-authored by Dr. E. A. Hirsch).

I have been working on cryptography-related problems, namely algebraic cryptography and complete crypto problems. Together with Dr. D. Yu. Grigoriev we made progress in invariant-based algebraic cryptosystems. Recently, together with Arist Kojevnikov, we developed new examples of combinatorial complete one-way functions.

Jointly with Dr. E. A. Hirsch, I devised a feebly secure trapdoor function, the only trapdoor function currently known to be provably (but, alas, very weakly) secure.

The results on theoretical cryptography formed the base of my Ph. D. thesis, defended on February 18, 2009 in Steklov Mathematical Institute, St. Petersburg. The results of my thesis have been prepared for publication in a book form and have appeared in 2011 under the name «Provably Secure Constructions in Cryptography» (LAP Lambert Academic Publishing, 2011); latest results have been also summarized in a chapter in «Cryptography and Security in Computing» (InTech, 2012).

My latest interests in computer science include bioinformatics.

Publications

  1. S.I. Nikolenko. Provably Secure Cryptographic Constructions. In J. Sen (ed.), Cryptography and Security in Computing, InTech, 2012, pp. 3–22. (electronic edition) (.pdf, 192kb)
  2. A.P. Davydow, S.I. Nikolenko. Circuit Complexity of Linear Functions: Gate Elimination and Feeble Security. Journal of Mathematical Sciences, vol. 188, no. 1, pp. 35–43, 2013 (springerlink). Zapiski nauchnyh seminarov POMI (Journal of Mathematical Sciences), vol. 399, 2012, pp. 65–87. (.pdf, 285kb, in Russian)
  3. E.A. Hirsch, O. Melanich, S.I. Nikolenko. Feebly Secure Cryptographic Primitives. Journal of Mathematical Sciences, vol. 188, no. 1, pp. 17–34, 2013 (springerlink). Zapiski nauchnyh seminarov POMI (Journal of Mathematical Sciences), vol. 399, 2012, pp. 32–64. (.pdf, 350kb)
  4. S.I. Nikolenko. Provably Secure Constructions in Cryptography. Lambert Academic Publishing, 2011 (morebooks.de).
  5. A. Davydow, S.I. Nikolenko. Gate Elimination for Linear Functions and New Feebly Secure Constructions. Proceedings of the 6th Computer Science Symposium in Russia (CSR 2011), LNCS vol. 6651, pp. 148-161. (.pdf, 294kb)
  6. S.I. Nikolenko, A.V. Sirotkin. Extensions of the TrueSkillTM rating system. Proceedings of the 9th International Conference on Applications of Fuzzy Systems and Soft Computing (ICAFS 2010), pp. 151–160. (.pdf, 1053kb)
  7. I. Gnilomedov, S.I. Nikolenko. Fuzzy computing via multiagent negotiations. Proceedings of the 9th International Conference on Applications of Fuzzy Systems and Soft Computing (ICAFS 2010), pp. 210–220.
  8. I. Gnilomedov, S.I. Nikolenko. Agent-Based Economic Modeling with Finite State Machines. Proceedings of the 36th Annual Convention of the Society for the Study of Artificial Intelligence and Simulation of Behaviour (AISB 2010). (.pdf, 130kb)
  9. E.A. Hirsch, S.I. Nikolenko. A feebly secure trapdoor function. Proceedings of the 4th Computer Science Symposium in Russia (CSR 2009), LNCS vol. 5675, 2009, pp. 129-142. (.pdf, 198kb)
  10. A. Kojevnikov, S.I. Nikolenko. On Complete One-Way Functions. Problems of Information Transmission, vol. 45, no. 2, 2009, pp. 101-118. (.pdf, 191kb)
  11. S.I. Nikolenko. New constructions of cryptographic primitives based on semigroups, groups, and linear algebra. Ph. D. thesis. Steklov Mathematical Institute, St-Petersburg, 2009. (.pdf, 607kb, in Russian)
  12. E.A. Hirsch, S.I. Nikolenko. A feebly secure trapdoor function. PDMI Preprints, 16/2008, 2008. (.pdf, 189kb), (.pdf, 320kb, in Russian)
  13. D.Yu. Grigoriev, A. Kojevnikov, S.I. Nikolenko. Algebraic Cryptography: New Constructions and Their Security against Provable Break. St. Petersburg Mathematical Journal, vol. 20, no. 6, 2008, pp. 119-147. (.pdf, 342kb) (.pdf, 385kb, in Russian)
  14. E.A. Hirsch, A. Kojevnikov, A.S. Kulikov, S.I. Nikolenko. Complexity of Semialgebraic Proofs with Restricted Degree of Falsity. Journal of Satisfiability, vol. 6, 2008, pp. 53-69. (.pdf, 255kb)
  15. A. Kojevnikov, S.I. Nikolenko. New Combinatorial Complete One-Way Functions. Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Bordeaux, France, 2008, pp. 457-466. (.pdf, 175kb)
  16. D. Grigoriev, A. Kojevnikov, S.I. Nikolenko. Invariant-Based Cryptosystems and Their Security Against Provable Worst-Case Break. Max-Planck-Institut fur Mathematik Preprint no. 158, 2007. (.pdf, 210kb)
  17. E.A. Hirsch, S.I. Nikolenko. Simulating Cutting Planes proofs with restricted degree of falsity by Resolution. Proceedings of SAT'05, Lecture Notes in Computer Science, vol. 3569, 2005, pp. 135-142. Available as ECCC TR05-006.
  18. S.S. Fedin, A. Kojevnikov, B. Konev, A.S. Kulikov, S.I. Nikolenko, V.P. Orevkov. First report on the semialgebraic prover. PDMI preprint 2004-09. ( ps.gz from ftp )
  19. S.I. Nikolenko, A.V. Sirotkin. Worst-case upper bounds for SAT: automated proof. Student Session Proceedings, 15th European Summer School in Logic, Language, and Information (ESSLLI 2003), pp. 225-232. Vienna, Austria, 2003. (.ps.gz, 74kb)
  20. S.I. Nikolenko. Hard satisfiable instances for DPLL-type algorithms. Journal of Mathematical Sciences, vol. 293, p. 139-149, 2003. (.pdf, 163kb)

Talks and posters

  1. S.I. Nikolenko. Continuous hard-to-invert functions based on tropical constructions. Symbolic Computations and Post-Quantum Cryptography Online Seminar, April 05, 2012, talk. (.pdf, 476kb)
  2. S.I. Nikolenko. A group-based combinatorial complete one-way function. First Russian-Finnish Symposium on Discrete Mathematics, September 22, 2011, talk.
  3. S.I. Nikolenko. Fuzzy cryptography. Workshop on Post-Quantum Cryptography, June 12, 2011, talk.
  4. S.I. Nikolenko. Feebly secure cryptographic primitives. Workshop on Complexity and Group-based Cryptography, September 2, 2010, talk.