Skip to main content

Thesis Information
Title: Complexity of Heuristic Computations and Interactive Protocols
Adviser: Edward A. Hirsch
Institution: Steklov Institute
Graduation Date: March 2017

Contact Information
Email Candidate
Candidate Website
SIGACT Membership No.: 1223933

Candidate Bio:

"I have a master degree in mathematics from St Petersburg State University with a specialty in algebra in 2013. Afterward, I have studied at Steklov Institute at St Petersburg as a Ph. D. student in mathematical logic under the supervision of Edward A. Hirsch. Last three years, I am an SEW Assistant Professor at the University of California, San Diego.

During my Ph. D. studies, in addition to the research, I taught algebra, algorithms, discrete mathematics, and complexity theory at Academic University at St Petersburg and in the centers of extracurricular education."

Research Summary:

"I am interested in theoretical computer science; however, lately, the main interest is proof complexity and its relations with communication and circuit complexity.

During my undergraduate and Ph. D. studies, I studied average-case complexity. I proved fixed-polynomial circuit lower bounds on the complexity of functions from the average-case version of the MA class. In a joint project with Dmitry Itsykson and Dmitry Sokolov, we gave a simplified proof for time hierarchies of average-case versions of semantic classes (such as BPP and AM).

In the last year at Steklov Institute, I, together with Dmitry Itsykson, Dmitry Sokolov, Andrey Romaschenko, and Sam Buss, started the study of OBDD bases proof systems. We give a complete picture of relations between these systems and resolution.

During my stay at UCSD, Sam Buss and I studied stable merge sort algorithms; and together with Eddie Amari, I study computational complexity of statistical problems in geometry."

Teaching Aims:

"Nowadays, resources are abundant in every possible topic. So in my classes, I am trying to show to my students that questioning is the only possible way not to be lost in this ``ocean''.

So I encourage them to ask me all the questions they have. It is not a secret that asking questions in the big audiences (for example, a typical UCSD classroom consists of 200 students) is difficult for students. It is especially true for members of underrepresented groups.
To mitigate this problem, I am using modern technology and teaching techniques.

Besides, I am showing to my students that even in fields like mathematics and theoretical computer science, there are several different points of view. Therefore it is a good idea to read about the same topic in various sources. To help them find such sources, I provide my lecture notes and videos recorded for my classes. "

Paper 1:

"Reordering Rule Makes OBDD Proof Systems Stronger, Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov, CCC, 2018"

Link to PDF

Paper 2:

Strategies for Stable Merge Sorting, Sam Buss, Alexander Knop, SODA, 2019

Link to PDF

Paper 3:

"On the Limits of Gate Elimination, Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov, MFCS, 2016"

Link to PDF

Keywords: computational complexity, algorithms, computational applications of logic

All Job Candidates