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.

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

All Job Candidates

Candidate Bio:

I am an NSF postdoctoral fellow at Harvard University with joint appointments in the School of Engineering and Applied Sciences and the Center for Mathematical Sciences and Applications. I graduated from Yale University in 2017 under the supervision of Van Vu. Before that, I received my undergraduate degree from Harvey Mudd College.

Teaching Aims:

I have seven years of teaching experience and have won two competitive teaching awards. I recently designed and taught a graduate course on high-dimensional probability at Harvard. In the classroom, I try to achieve a balance between intuition and rigor. I am also committed to promoting participation in mathematics and computer science from traditionally underrepresented groups.

Keywords: Random matrices, high-dimensional algorithms, machine learning, compressed sensing

All Job Candidates

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. “

Keywords: computational complexity, algorithms, computational applications of logic

All Job Candidates

Candidate Bio:

I completed my PhD in the area of Proof Complexity under supervision of Jan Krajíček. Afterwards, I held a postdoctoral position at the University of Toronto hosted by Stephen Cook, Toniann Pitassi and Alasdair Urquhart, a postdoctoral position at the University of Leeds hosted by Olaf Beyersdorff, and then relocated to the University of Vienna where I worked with Moritz Muller on an FWF project “Complexity Theory in Feasible Mathematics”. Later I continued my research at the University of Oxford hosted by Rahul Santhanam. Since September 2019 I am back in Prague at the Czech Academy of Sciences.

Research Summary:

I am interested in Mathematical Logic and Complexity Theory. In particular, in my research I focus on proof complexity of circuit lower bounds, a research direction initiated by Razborov with a proof-theoretic formulation of the natural proofs barrier. I proved, for example, that first-order theories strictly below Cook’s theory PV, which formalizes polynomial-time reasoning, cannot separate P and NP unless standard hardness assumptions break. Complementing this lower bound I showed that PV is strong enough to prove the PCP theorem. More recently, these investigations led me to a co-development of a theory of hardness magnification, an approach to strong complexity lower bounds avoiding some of the earlier formal barriers in Complexity Theory. In particular, hardness magnification establishes that a slight improvement over many known circuit lower bounds for natural problems would imply breakthrough separations such as P\ne NP or the non-existence of efficient learning algorithms.

Teaching Aims:

“I have a broad background in Mathematics and Theoretical Computer Science and I would be happy to teach standard courses in these subjects, e.g. Calculus, Algebra, Logic, Algorithms. Regarding more advanced courses, I would enjoy teaching various topics in Complexity Theory and Mathematical Logic, e.g. Cryptography, Learning Theory, Circuit Complexity, Model Theory. I would be also happy to organize seminars focusing on the latest advances on the most fundamental open problems in these areas.
My general teaching philosophy is to attract students to think about important problems by making advanced and emerging research areas accessible, in particular, by a proper motivation of abstract concepts and by highlighting key ideas. I want to keep lectures well-organized, with clear goals and rigorous proofs but also believe that students should feel comfortable to ask questions and discuss their ideas.”

Keywords: proof complexity, circuit complexity, hardness magnification, bounded arithmetic

All Job Candidates

Candidate Bio:

I have held postdoctoral positions in University of Vienna and Max Planck Institute (MPI) for Informatics, and currently in Singapore University of Technology and Design. Trained as a Theoretical Computer Science (TCS) researcher and having knowledge of Dynamical Systems (DS), I enjoy the interdisciplinary research at the intersection of Computer Science and Economics, where I have applied concepts and techniques in TCS and DS to analyze (in)stability of machine learning algorithm, asynchronous optimization and market dynamics. I also like thinking about problems in Combinatorics, particularly those arising from Graph Sparsification and Partitioning.

Research Summary:

“My research focuses on Computational Economics and Algorithmic Game Theory. Economies (e.g., games, markets, auctions) have agents making decisions (i.e., computing or learning) and interacting rapidly, with minimal centralized coordination. My long term goal is to develop a thorough understanding of complex economies from a modern computer-science perspective.

My interdisciplinary research in Computer Science and Economics has proved that the two subjects can gain insight from each other. Here are some highlights:

a) we use a volume expansion argument to show that Multiplicative Weights Update (MWU) and Follow-the-Regularized-Leader (FTRL) algorithms in zero-sum games are Lyapunov chaotic in a payoff space;

b) using duality and transformations of convex programs, we drew direct connections between market dynamics and gradient/mirror descent;

c) using amortized analysis and adversary construction, we derived tight bounds on permissible parallelism of Stochastic Asynchronous Coordinate Descent; we also showed a market dynamic is robust against asynchrony.”

Teaching Aims:

“I enjoy teaching and mentoring students. It is always fulfilling to see students progress in my classes. Also, teaching improves myself; I view teaching as an indispensable process of developing myself into a better researcher and scholar.

My first teaching experience dates back to at least 17 years ago. In 2017, I was the lecturer in Max Planck Institute of a graduate level Algorithmic Game Theory course. I have developed my teaching philosophy with five principles:

a) emphasis of meaning and understanding;
b) try the very best to give motivation on the topic to be taught;
c) encourage critical thinking;
d) elicit potential of advanced students;
e) teaching and research are mutually beneficial to each other.”

Keywords: Computational Economics, Algorithmic Game Theory, Learning in Games, Asynchronous Optimization, Dynamical Systems

All Job Candidates

Candidate Bio:

I did my B.Sc. in CS at Comenius University, Bratislava, Slovakia, graduating in 2005; M.Sc. in CS at Simon Fraser University, Burnaby, BC, Canada, with Gábor Tardos, graduating in 2008; and PhD in Mathematics with János Pach at EPFL, Lausanne, Switzerland, graduating in 2012. I held postdoctoral research positions at EPFL (2012-13), Charles University, Prague, Czechia (2013), Columbia University, NYC (2013-2015), and IST Austria, Klosterneuburg, Austria (2015-2019). I joined University of Arizona as a postdoctoral research associate in September 2019.

Research Summary:

“The general area of my research is studying combinatorial properties of arrangements of basic geometric objects such as points, lines, polygons, polyhedra, discs, convex sets, etc., motivated mainly by computational problems. Closely related to this, I am interested in topological graph theory, which can be regarded as the study of arrangements of curves on a fixed set of endpoints.
I have worked on a variety of problems in combinatorial geometry and the theory of topological graphs.
My scientific achievements include the first algorithm with a polynomial running time for clustered planarity, and the confirmation of a conjecture of M. Skopenkov from 2003 and its weaker variant by A. Skopenkov and Repovs from 1998 extending the classical Hanani-Tutte theorem to the setting of approximating maps of graphs.”

Teaching Aims:

Teaching and mentoring is one of the most important aspects of academic life and often one of the most rewarding ones. In my past teaching experience, I really enjoyed giving classes related to my research interests and lecturing about material that I wanted to better understand myself.

Keywords: computational geometry, combinatorics, algorithms, algorithmic graph theory, optimization

All Job Candidates