Title: Circuit Complexity: New Techniques and Their Limitations
Adviser: Yevgeniy Dodis; Oded Regev
Institution: New York University
Graduation Date: May 2017
I am a Rabin postdoc at Harvard University. Prior to this, I was a research scientist at Columbia University and Yahoo Research. In 2017 I received my PhD from NYU advised by Oded Regev and Yevgeniy Dodis.
I have taught Massive Open Online Courses (MOOC) through Coursera, several mini courses on Algorithms and Computational Complexity, graduate courses on Algorithms and Random Graphs, and several courses for high-school students. Also, I have given a number of guest lectures in courses on my areas of expertise: Computational Complexity and Discrete Math.
Static Data Structure Lower Bounds Imply Rigidity. Zeev Dvir, Alexander Golovnev, Omri Weinstein. STOC, 2019Link to PDF
A Better-than-3n Lower Bound for the Circuit Complexity of an Explicit Function. Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov. FOCS, 2016Link to PDF
Tight Lower Bounds on Graph Embedding Problems. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socała. J. ACM, 2017Link to PDF
Keywords: computational complexity, algorithms, learning theory, cryptography, data structures