[Colloquium] Zelin Lv Candidacy Exam/Dec 18, 2025

[via Colloquium]

This is an announcement of Zelin Lv's Candidacy Exam.
===============================================
Candidate: Zelin Lv

Date: Thursday, December 18, 2025

Time:  9 am CST

Remote Location: https://uchicago.zoom.us/j/98103678898?pwd=OjaP5H9PsaMHpZb5MCaEw9Qi3iDYKr.1 Meeting ID: 981 0367 8898 Passcode: 170509

Location: JCL 298

Title: Random Determinants and Pseudorandomness in Computational Complexity

Abstract: In this talk, I will present my research on randomness and derandomization, spanning both random matrix theory and pseudorandomness for computational models.

On the random matrix side, I will first discuss my work on moments of determinants of random matrices. Using tools from analytic combinatorics, I analyzed the second moment of the determinant for random symmetric, Wigner, and Hermitian matrices, obtaining a unified framework that covers all three ensembles under mild independence assumptions on the entries. I will then describe results on the sixth moment of the determinant for asymmetric n×n random matrices with i.i.d. entries drawn from an arbitrary mean-zero distribution Ω, including precise asymptotics as n→∞. Finally, I will outline an ongoing project that extends the sixth-moment analysis to much more general entry distributions. In this work, we develop new methods that reduce the problem to finitely many combinatorial types and then systematically enumerate and evaluate these cases via a large-scale computer program, highlighting the interaction between combinatorial structure and symbolic/numeric computation.

On the pseudorandomness side, I will focus on explicit constructions for derandomizing natural computational models. First, I will present a pseudorandom generator for decision trees whose seed length is essentially optimal in the size parameter. The key technical ingredient is a new variant of almost k-wise independence, which we call k-wise “probably uniform” distributions; I will show how to construct such distributions efficiently. Then I will show how to construct new hitting sets for systems of linear equations, leading to nontrivial PRGs and hitting sets for certain linear-size circuit classes. Next, I will describe a line of work that studies the bitwise XOR of multiple copies of the INW PRG for constant-width read-once branching programs (ROBPs), including both a positive error bound and a matching lower bound showing intrinsic limitations of this “XOR of INW’’ approach when one only uses spectral expansion of the underlying expanders. I will conclude by discussing ongoing work on deterministic samplers, a derandomizing object that sits strictly between weighted PRGs and hitting set generators. In particular, I will explain how to convert hitting set generators for ROBPs into deterministic samplers [result by Edward Pyne, Ran Raz, Wei Zhan], and I will outline some potential research directions along with deterministic samplers.

Advisors: Aaron Potechin and William Hoza

Committee Members: Aaron Potechin, William Hoza, Janos Simon