Zhenjian Lu

According to our database, Zhenjian Lu authored at least 16 papers between 2017 and 2023.

Collaborative distances:

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

2023

Algorithms and Lower Bounds for Comparator Circuits from Shrinkage.

Bruno Pasqualotto Cavalar, Zhenjian Lu

Algorithmica, July, 2023

Bounded Relativization.

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Electron. Colloquium Comput. Complex., 2023

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

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2023

Polynomial-Time Pseudodeterministic Construction of Primes.

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2023

2022

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.

Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand

Electron. Colloquium Comput. Complex., 2022

Theory and Applications of Probabilistic Kolmogorov Complexity.

Zhenjian Lu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2022

Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.

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

Electron. Colloquium Comput. Complex., 2022

2021

Pseudodeterministic Algorithms and the Structure of Probabilistic Time.

Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2021

An Efficient Coding Theorem via Probabilistic Representations and its Applications.

Zhenjian Lu, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 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

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

Electron. Colloquium Comput. Complex., 2020

2019

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

Electron. Colloquium Comput. Complex., 2019

2018

Satisfiability and Derandomization for Small Polynomial Threshold Circuits.

Valentine Kabanets, Zhenjian Lu

Electron. Colloquium Comput. Complex., 2018

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

Valentine Kabanets, Zhenjian Lu

Electron. Colloquium Comput. Complex., 2018

2017

A Polynomial Restriction Lemma with Applications.

Valentine Kabanets, Daniel M. Kane, Zhenjian Lu

Electron. Colloquium Comput. Complex., 2017