videos
This page contains a collection of potentially helpful videos that I have not watched because my voice sounds weird. :-)
I very much hope that the habit of recording seminar and conference talks, which we all had to develop during 2020-2022, will remain with us for the long run. In case you spot a silly thing that I've said, I'll be grateful if you ping me to let me know (I'll simply add a correction next to the video).
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.
New Directions in Derandomization [Oct 2022, FOCS]
These videos are from a workshop that was part of FOCS 2022 and that I co-organized with Lijie Chen. The workshop focused on developments in derandomization in the preceding ~3 years, and included presentations by the wonderful Dean Doron, Oliver Korten, Yanyi Liu, Hanlin Ren, and Nicollas Sdroievski, as well as by Lijie and myself. There was also an open problems session in the end.
The four videos linked below correspond to the four live sessions in which the workshop was held. A schedule and abstracts for the talks are available at the workshop's webpage.
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.
Recent Developments in Derandomization [May 2022, DIMACS]
A joint two-talk series with Lijie Chen at the wonderful DIMACS workshop, surveying the developments around derandomization in the recent three years (including more results than the IAS series in Feb). The first talk is Lijie presenting results in high-level, the second talk is me giving some technical details.
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.
Derandomization and its connections throughout complexity theory [Feb 2022, IAS]
This is a three-part series, joint with Lijie Chen, in which we survey the developments around derandomization in the recent three years. The first talk presents the background and main questions; the second talk (by Lijie) describes new unconditional lower bounds for Merlin-Arthur protocols with an ACC0 verifier; and the third talk focuses on the new approach of non-black-box derandomization.
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).
STOC 2018.mp4Source: STOC 2018 online proceedings by ACM.
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.