Sergey Nikolenko

Sergey Nikolenko

Main page

Books
Research papers
Talks and posters
Students
Popular science
Other stuff

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

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

  External links
Google Scholar profile
DBLP profile
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.