Skip to main content

Thesis Information
Title: Circuit Complexity: New Techniques and Their Limitations
Adviser: Yevgeniy Dodis; Oded Regev
Institution: New York University
Graduation Date: May 2017

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

Candidate Bio:

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.

Teaching Aims:

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.

Paper 1:

Static Data Structure Lower Bounds Imply Rigidity. Zeev Dvir, Alexander Golovnev, Omri Weinstein. STOC, 2019

Link to PDF

Paper 2:

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, 2016

Link to PDF

Paper 3:

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, 2017

Link to PDF

Keywords: computational complexity, algorithms, learning theory, cryptography, data structures

All Job Candidates