Dmitry Itsykson

I am a non-faculty researcher at the Computer Science Department of the Ben-Gurion University of the Negev.

I am currently on leave from the Laboratory of Mathematical Logic of Steklov Institute of Mathematics at St.Petersburg, where I hold a leading researcher position.

Profile photo

Research interests

I am a theoretical computer scientist. My research mainly focuses on computational complexity theory, including propositional proof complexity, lower bounds for algorithms for Boolean satisfiability, and average-case complexity.

Computational Complexity Proof Complexity Average-case Complexity SAT Algorithms

Education and degrees

In 2006 I graduated from St. Petersburg State University.

In 2009, I completed a PhD (Russian degree candidate of science) at Steklov Institute of Mathematics at St. Petersburg, thesis "Average-case complexity of randomized computations with bounded error" (supervisor Edward A. Hirsch).

In 2022, I defended a habilitation thesis (for a Russian degree doctor of science), "Lower bounds and optimality for proof systems".

Research positions

Since 2009, I have been working at the Laboratory of Mathematical Logic of Steklov Institute of Mathematics at St.Petersburg.

Since 2022, I have been working at the Computer Science Department of the Ben-Gurion University of the Negev, at Klim Efremenko's invitation.

Teaching

From 2004 to 2011, I taught at the Center of Mathematical Education at Lyceum 239 (additional mathematical education for high school students).

From 2008 to 2019, I was a part-time associate professor at the Department of Mathematics and Information Technology of St. Petersburg Academic University.

From 2018 to 2022, I was a part-time associate professor at the Department of Mathematics and Computer Science of St. Petersburg State University.