Zhenjian Lu

Postdoctoral Researcher
Department of Computer Science
University of Warwick, UK

[FirstName].[LastName]@warwick.ac.uk

Hello!

I am a postdoctoral researcher at the University of Warwick, hosted by Igor Carboni Oliveira.

Previously, I held positions as a postdoctoral researcher at the University of Oxford, hosted by Rahul Santhanam, and as a Research Fellow for the Meta-Complexity program at the Simons Institute for the Theory of Computing. I obtained my Ph.D. from Simon Fraser University, where I was advised by Valentine Kabanets and Andrei Bulatov. I did my Bachelor's in Computer Science at the University of British Columbia.

Research Interests

  • Computational Complexity

  • Circuit Complexity

  • Randomness in Computation

  • Meta-Complexity

  • Connections between Lower Bounds and Algorithms

Papers


  • One-Way Functions and pKt Complexity

    • [ECCC]

    with Shuichi Hirahara and Igor C. Oliveira

    TCC 2024


  • Optimal Coding for Randomized Kolmogorov Complexity and Its Applications

    • [ECCC]

    with Shuichi Hirahara and Mikito Nanashima

    FOCS 2024


  • On the Complexity of Avoiding Heavy Elements

    • [ECCC]

    with Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam

    FOCS 2024


  • Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity

    • [ECCC]

    with Shuichi Hirahara, Valentine Kabanets, and Igor C. Oliveira

    CCC 2024


  • Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity

    • [ECCC]

    with Rahul Santhanam

    ICALP 2024


  • Polynomial-Time Pseudodeterministic Construction of Primes

    • [ECCC] [Quanta] [Computational Complexity Blog] [Oded's Choices]

    with Lijie Chen, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam

    FOCS 2023


  • Bounded Relativization

    • [ECCC]

    with Shuichi Hirahara and Hanlin Ren

    CCC 2023


  • A Duality Between One-Way Functions and Average-Case Symmetry of Information

    • [ECCC]

    with Shuichi Hirahara, Rahul Ilango, Mikito Nanashima, and Igor C. Oliveira

    STOC 2023


  • Theory and Applications of Probabilistic Kolmogorov Complexity

    • [ECCC]

    with Igor C. Oliveira

    The Computational Complexity Column - Bulletin of EATCS No 137, 2022


  • Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

    • [ECCC]

    with Halley Goldberg, Valentine Kabanets, and Igor C. Oliveira

    CCC 2022


  • Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

    • [arXiv]

    with Igor C. Oliveira and Marius Zimand

    ICALP 2022


  • Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

    • [ECCC]

    with Bruno P. Cavalar

    ITCS 2022


  • Majority vs. Approximate Linear Sum and Average-Case Complexity below NC1

    • [ECCC]

    with Lijie Chen, Xin Lyu, and Igor C. Oliveira

    ICALP 2021


  • An Efficient Coding Theorem via Probabilistic Representations and its Applications

    • [ECCC]

    with Igor C. Oliveira

    ICALP 2021


  • Pseudodeterministic Algorithms and the Structure of Probabilistic Time

    • [ECCC]

    with Igor C. Oliveira and Rahul Santhanam

    STOC 2021


  • Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates

    • [ECCC]

    with Valentine Kabanets, Sajin Koroth, Dimitrios Myrisiotis, and Igor C. Oliveira

    CCC 2020


  • Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

    • [ECCC]

    with Mahdi Cheraghchi, Valentine Kabanets, and Dimitrios Myrisiotis

    ICALP 2019


  • Satisfiability and Derandomization for Small Polynomial Threshold Circuits

    • [ECCC]

    with Valentine Kabanets

    RANDOM 2018


  • A Polynomial Restriction Lemma with Applications

    • [ECCC]

    with Valentine Kabanets and Daniel Kane

    STOC 2017