Homepage of Alexey Chernov


I am a postdoctoral researcher at IDSIA since November 2003, in Jürgen Schmidhuber's lab.

In 1995-2003 I was a student and then a PhD student at Moscow State University
(Faculty of Mechanics and Mathematics, Department of Mathematical Logic and Theory of Algorithms,
supervisor prof. Vereshchagin).

Research interests: Kolmogorov complexity, realizability, computational complexity.

Contact:

Alexey Chernov
IDSIA, Galleria 2,
CH-6928 Manno,
Switzerland
E-mail: alexeyidsiach


Publications:

  1. Alexey Chernov, Juergen Schmidhuber. Prefix-like Complexities and Computability in the Limit. Proc. of Second Conference on Computability in Europe, CiE 2006, LNCS 3988, pp. 85-93.
    Alexey Chernov, Juergen Schmidhuber. Prefix-like Complexities of Finite and Infinite Sequences on Generalized Turing Machines. Tech Report IDSIA-11-05, IDSIA, Manno(Lugano), Switzerland, 2005. pdf

  2. Alexey Chernov, Marcus Hutter, Juergen Schmidhuber. Complexity Monotone in Conditions and Future Prediction Errors. Dagstuhl Seminar Proceedings 06051, 2006. pdf
    Alexey Chernov, Marcus Hutter. Monotone Conditional Complexity Bounds on Future Prediction Errors. Proc. of 16th International Conf. on Algorithmic Learning Theory (ALT-2005), LNCS 3734, pp. 414-428. Springer link Tech Report: IDSIA-16-05 pdf, arXiv.
    Alexey Chernov, Juergen Schmidhuber. On decrease of a priori randomness deficiency. Tech Report IDSIA-12-05, IDSIA, Manno(Lugano), Switzerland, 2005. pdf

  3. A.Chernov. Finite Problems and the Logic of the Weak Law of Excluded Middle. Matematicheskie Zametki, 2005, vol. 77, no. 2, pp. 291-302, in Russian (ps.gz). English translation: Mathematical Notes, 2005, vol. 77, no. 1, pp. 263-272. Springer link
    Preliminary version: Dep. in VINITI 3.07.2003 No.1263-B2003, in Russian (ps.gz).

  4. A.Chernov. Complexity of Sets Obtained as Values of Propositional Formulas. Matematicheskie Zametki, 2004, vol. 75, no. 1, pp. 142-150, in Russian (ps.gz). English translation: Mathematical Notes, 2004, vol. 75, no. 1, pp. 131-139. Springer link

  5. A.Chernov, D.Skvortsov, E.Skvortsova, N.Vereshchagin. Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle. In: Mathematical Logic and Algebra. Proceedings of Steklov Mathematical Insitute, 2003, vol. 242, pp. 77-97.
    Conference version in Computer Science Logic: 16th International Workshop, CSL 2002, LNCS 2471, pp. 74-88. Springer link

  6. A.Chernov, An.Muchnik, A.Romashchenko, A.Shen, N.Vereshchagin. Upper semi-lattice of binary strings with the relation 'x is simple conditional to y'. Theoretical Computer Science, 2002, v.271, pp. 69-95.

Conference talks:

  1. Effective Operations on Sets and Kolmogorov Complexity. Centennial Seminar on Kolmogorov Complexity and Applications, Dagstuhl, Germany, April 27 - May 2, 2003.
  2. Kolmogorov Complexity, Kleene Realizability and the Weak Law of Excluded Middle. Workshop on Computability and Randomness, Heidelberg, Germany, April 25-26, 2003.
  3. Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle (joint with D.Skvortsov, E.Skvortsova, N.Vereshchagin). Computer Science Logic'02, Edinburgh, Scotland, September 22-25, 2002.
  4. Variants of Realizability for Propositional Formulas Leading to the Logic of the Weak Law of Excluded Middle (joint with D.Skvortsov, E.Skvortsova, N.Vereshchagin). 2nd Moscow - Vienna Workshop on Logic and Computation, Moscow, Russia, April 26-27, 2002.
  5. The Set of Quasy-independent Random Variables is 3-dimensional. XXI Conference of Young Scientists, Moscow, Russia, May 11-14, 1999.

Candidate  dissertation  (PhD thesis),  in Russian:

On Some Variants of the Notion of Realizability. Moscow State University, 2003.