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 PDFPaper 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 PDFPaper 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 PDFKeywords: computational complexity, algorithms, learning theory, cryptography, data structures