videos

Derandomization: Hardness vs Randomness

These are three expository presentations to hardness vs randomness that I gave at the DIMACS event "Frontiers in Complexity Theory: A Graduate Workshop"; the slides appear on the left, the videos are below. The presentations start from classical textbook results, and quickly reach results from 2023-2024. The target audience is grad students working in complexity theory, so the presentations assume familiarity with common techniques in complexity (and some comfort with them).

Errata: I incorrectly claimed that the CLORS23 algorithm is pseudodeterministic on all input lengths. However, the argument I presented only establishes that on almost all input lengths, whp the algorithm outputs a value in { ⟂, p_n }, where p_n is a canonical prime (it might output each wp 1/2).

Also, be warned: My presentation of Nisan-Wigderson was very bad, since I misjudged the audience's background and didn't prepare correctly (I thought that most attendants knew it already).

Depth-d threshold circuits vs. depth-(d+1) AND-OR trees

Presenting this paper virtually at STOC 2023. The paper is very technical, and the video is short (~30min). So you can expect to get context and light background, statements of the main result and of corollaries, and mostly teasers about the techniques. There's a cool high-level point that I didn't emphasize clearly enough in the video: Many classical circuit lower bounds have been strengthened in the last ~15 years such that the hard function is in AC0, rather than parity/majority/Andreev.

Unstructured hardness to average-case randomness [Feb 2023, Simons]

Presenting this paper as part of the great Lower Bounds, Learning, and Average-Case Complexity workshop in the Simons Meta-Complexity program. Fair warning: The talk was intended for experts in a workshop, so I was quite fast and informal in some technical parts.

Superfast derandomization of interactive proof systems [Oct 2022, IAS]

Presenting this paper. The first half of the talk was unfortunately truncated, and what remains is the second half, which presents the proof of (the most interesting case of) the main theorem.

New Directions in Derandomization: Non-Black-Box Techniques, Superfast Algorithms [Oct 2022, Princeton]

In the first half of the talk I presented new directions that have been studied in derandomization in the last couple of years, very briefly and at a high level. In the second half I presented a main result from this paper. 

Randomness in Algorithms: Understanding It, Eliminating It  [Oct 2022, IAS]

A 15-minute overview of my research area and main directions of interest at the time, intended for a broad math audience. I found the great illustrative example about sautéing onions in David Zuckerman's survey from 2010.

Hardness vs Randomness, revised: Uniform, non-black-box, instance-wise [Mar 2022, TCS+]

Presenting this paper. The YouTube video has one comment, saying " ??????? ?", so maybe I should've presented it in a clearer way.

Fooling Constant-Depth Threshold Circuits [Feb 2022, FOCS]

Presenting this paper. William Hoza gave a great and more detailed presentation of this paper at TCS+ (maybe from slightly different angles), it's available on his webpage.

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise [Feb 2022, FOCS]

Presenting this paper. The TCS+ talk above (from March 2022) presents the paper in a more elaborate way.

Simple and Fast Derandomization from Very Hard Functions: Eliminating Randomness at Almost No Cost [Jun 2021, STOC]

Presenting this paper in a virtual STOC session. The extension of the average-case derandomization to one that holds over all polytime-samplable distributions (mentioned in the end) appears here.

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds [Oct 2020, FOCS]

Presenting this paper. The first main theorem in this paper was superseded later by this paper (I'll share a link for a recorded presentation of it from FOCS22 as soon as it becomes available). But the underlying technical construction and other results can still hopefully be interesting.

On Hitting-Set Generators for Polynomials that Vanish Rarely  [Aug 2020, RANDOM]

Presenting this paper in the virtual "polynomials session" at RANDOM. 

An Overview of Quantified Derandomization [Sep 2018, Simons]

A survey talk about quantified derandomization in the Boolean Devices workshop. The talk is a bit outdated, but only in the sense that it doesn't include newer results (see my 2022 survey for a more current overview, here or here).

Quantified Derandomization of Linear Threshold Circuits [June 2018, STOC]

Presenting this paper in STOC 2018. The second main result has been quantitatively improved since, using the same high-level idea but a better construction (in this paper; also see this very relevant paper). We also now have a PRG for this class (see this paper), rather than only a quantified derandomization algorithm.