Zhenjian Lu

According to our database, Zhenjian Lu authored at least 25 papers between 2017 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2026

Lower Bounds on the Overhead of Indistinguishability Obfuscation.

Zhenjian Lu, Noam Mazor, Igor C. Oliveira, Rafael Pass

Proceedings of the Advances in Cryptology - EUROCRYPT 2026, 2026

2025

Equivalence Between Coding and Complexity Lower Bounds.

Jinqiao Hu, Zhenjian Lu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2025

Hardness of Computing Nondeterministic Kolmogorov Complexity.

Jinqiao Hu, Zhenjian Lu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2025

Synergies Between Complexity Theory and Nondeterministic Kolmogorov Complexity.

Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2025

2024

One-Way Functions and pKt Complexity.

Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira

Proceedings of the Theory of Cryptography - 22nd International Conference, 2024

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

Zhenjian Lu, Rahul Santhanam

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

On the Complexity of Avoiding Heavy Elements.

Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications.

Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity.

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira

Proceedings of the 39th Computational Complexity Conference, 2024

2023

A Duality between One-Way Functions and Average-Case Symmetry of Information.

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Polynomial-Time Pseudodeterministic Construction of Primes.

Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Bounded Relativization.

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Theory and Applications of Probabilistic Kolmogorov Complexity.

Zhenjian Lu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2022

Algorithms and Lower Bounds for Comparator Circuits from Shrinkage.

Bruno Pasqualotto Cavalar, Zhenjian Lu

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.

Zhenjian Lu, Igor C. Oliveira, Marius Zimand

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira

Proceedings of the 37th Computational Complexity Conference, 2022

2021

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

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2021

Pseudodeterministic algorithms and the structure of probabilistic time.

Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

An Efficient Coding Theorem via Probabilistic Representations and Its Applications.

Zhenjian Lu, Igor C. Oliveira

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹.

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor C. Oliveira

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

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

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates.

Valentine Kabanets, Zhenjian Lu

Electron. Colloquium Comput. Complex., 2018

Satisfiability and Derandomization for Small Polynomial Threshold Circuits.

Valentine Kabanets, Zhenjian Lu

Proceedings of the Approximation, 2018

2017

A polynomial restriction lemma with applications.

Valentine Kabanets, Daniel M. Kane, Zhenjian Lu

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017