Zhenjian Lu

Publication Activity (10 Years)

Years Active: 2017-2024
Publications (10 Years): 44

Top Topics

Kolmogorov Complexity

Decreasing Function

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
On the Complexity of Avoiding Heavy Elements. Electron. Colloquium Comput. Complex. (2024)
Zhenjian Lu, Rahul Santhanam
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity. ICALP (2024)
Zhenjian Lu, Rahul Santhanam
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2024)
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2024)
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity. CCC (2024)
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
A Duality between One-Way Functions and Average-Case Symmetry of Information. STOC (2023)
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. FOCS (2023)
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. CoRR (2023)
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
A Duality Between One-Way Functions and Average-Case Symmetry of Information. IACR Cryptol. ePrint Arch. 2023 (2023)
Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. Electron. Colloquium Comput. Complex. (2023)
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren
Bounded Relativization. Electron. Colloquium Comput. Complex. (2023)
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren
Bounded Relativization. CCC (2023)
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
A Duality Between One-Way Functions and Average-Case Symmetry of Information. Electron. Colloquium Comput. Complex. (2023)
Bruno Pasqualotto Cavalar, Zhenjian Lu
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage. Algorithmica 85 (7) (2023)
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Carboni Oliveira
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. Electron. Colloquium Comput. Complex. (2022)
Zhenjian Lu, Igor Carboni Oliveira
Theory and Applications of Probabilistic Kolmogorov Complexity. Bull. EATCS 137 (2022)
Zhenjian Lu, Igor Carboni Oliveira
Theory and Applications of Probabilistic Kolmogorov Complexity. CoRR (2022)
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2022)
Bruno Pasqualotto Cavalar, Zhenjian Lu
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage. ITCS (2022)
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. CoRR (2022)
Zhenjian Lu, Igor Carboni Oliveira
Theory and Applications of Probabilistic Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2022)
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Carboni Oliveira
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. CCC (2022)
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. ICALP (2022)
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic algorithms and the structure of probabilistic time. STOC (2021)
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹. ICALP (2021)
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1. Electron. Colloquium Comput. Complex. 28 (2021)
Bruno Pasqualotto Cavalar, Zhenjian Lu
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage. Electron. Colloquium Comput. Complex. 28 (2021)
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic Algorithms and the Structure of Probabilistic Time. CoRR (2021)
Zhenjian Lu, Igor Carboni Oliveira
An Efficient Coding Theorem via Probabilistic Representations and Its Applications. ICALP (2021)
Zhenjian Lu, Igor Carboni Oliveira
An Efficient Coding Theorem via Probabilistic Representations and its Applications. Electron. Colloquium Comput. Complex. 28 (2021)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. ACM Trans. Comput. Theory 13 (4) (2021)
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic Algorithms and the Structure of Probabilistic Time. Electron. Colloquium Comput. Complex. 28 (2021)
Bruno Pasqualotto Cavalar, Zhenjian Lu
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage. CoRR (2021)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. CoRR (2020)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. Computational Complexity Conference (2020)
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. ACM Trans. Comput. Theory 12 (3) (2020)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. Electron. Colloquium Comput. Complex. 27 (2020)
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. Electron. Colloquium Comput. Complex. 26 (2019)
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. ICALP (2019)
Valentine Kabanets, Zhenjian Lu
Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates. Electron. Colloquium Comput. Complex. 25 (2018)
Valentine Kabanets, Zhenjian Lu
Satisfiability and Derandomization for Small Polynomial Threshold Circuits. APPROX-RANDOM (2018)
Valentine Kabanets, Zhenjian Lu
Satisfiability and Derandomization for Small Polynomial Threshold Circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Valentine Kabanets, Daniel M. Kane, Zhenjian Lu
A polynomial restriction lemma with applications. STOC (2017)
Valentine Kabanets, Daniel M. Kane, Zhenjian Lu
A Polynomial Restriction Lemma with Applications. Electron. Colloquium Comput. Complex. 24 (2017)