Zhenjian Lu

56 papers A* 11A 5Journal 38Unranked 2
YearRankTypeTitle / Venue / Authors
2025 J jnl
Equivalence Between Coding and Complexity Lower Bounds.
Electron. Colloquium Comput. Complex.
Jinqiao Hu, Zhenjian Lu, Igor C. Oliveira
2025 J jnl
Hardness of Computing Nondeterministic Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Jinqiao Hu, Zhenjian Lu, Igor C. Oliveira
2025 J jnl
Synergies Between Complexity Theory and Nondeterministic Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
2024 A conf
Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity.
CCC
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2024 A* conf
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity.
ICALP
Zhenjian Lu, Rahul Santhanam
2024 J jnl
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Rahul Santhanam
2024 J jnl
Lower Bounds on the Overhead of Indistinguishability Obfuscation.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Noam Mazor, Igor C. Oliveira, Rafael Pass
2024 J jnl
Lower Bounds on the Overhead of Indistinguishability Obfuscation.
IACR Cryptol. ePrint Arch.
Zhenjian Lu, Noam Mazor, Igor C. Oliveira, Rafael Pass
2024 A* conf
On the Complexity of Avoiding Heavy Elements.
FOCS
Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2024 J jnl
On the Complexity of Avoiding Heavy Elements.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2024 — conf
One-Way Functions and pKt Complexity.
TCC (1)
Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
One-Way Functions and pKt Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
One-Way Functions and pKt Complexity.
IACR Cryptol. ePrint Arch.
Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
2024 A* conf
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications.
FOCS
Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima
2024 J jnl
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications.
CoRR
Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima
2024 J jnl
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima
2023 J jnl
A Duality Between One-Way Functions and Average-Case Symmetry of Information.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
2023 J jnl
A Duality Between One-Way Functions and Average-Case Symmetry of Information.
IACR Cryptol. ePrint Arch.
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira
2023 A* conf
A Duality between One-Way Functions and Average-Case Symmetry of Information.
STOC
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira
2023 J jnl
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage.
Algorithmica
Bruno Pasqualotto Cavalar, Zhenjian Lu
2023 A conf
Bounded Relativization.
CCC
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren
2023 J jnl
Bounded Relativization.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren
2023 A* conf
Polynomial-Time Pseudodeterministic Construction of Primes.
FOCS
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2023 J jnl
Polynomial-Time Pseudodeterministic Construction of Primes.
CoRR
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2023 J jnl
Polynomial-Time Pseudodeterministic Construction of Primes.
Electron. Colloquium Comput. Complex.
Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam
2022 A conf
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage.
ITCS
Bruno Pasqualotto Cavalar, Zhenjian Lu
2022 A* conf
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.
ICALP
Zhenjian Lu, Igor C. Oliveira, Marius Zimand
2022 J jnl
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.
CoRR
Zhenjian Lu, Igor C. Oliveira, Marius Zimand
2022 J jnl
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
2022 A conf
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.
CCC
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2022 J jnl
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.
Electron. Colloquium Comput. Complex.
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2022 J jnl
Theory and Applications of Probabilistic Kolmogorov Complexity.
CoRR
Zhenjian Lu, Igor C. Oliveira
2022 J jnl
Theory and Applications of Probabilistic Kolmogorov Complexity.
Bull. EATCS
Zhenjian Lu, Igor C. Oliveira
2022 J jnl
Theory and Applications of Probabilistic Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor C. Oliveira
2021 J jnl
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage.
CoRR
Bruno Pasqualotto Cavalar, Zhenjian Lu
2021 J jnl
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage.
Electron. Colloquium Comput. Complex.
Bruno Pasqualotto Cavalar, Zhenjian Lu
2021 J jnl
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates.
ACM Trans. Comput. Theory
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2021 A* conf
An Efficient Coding Theorem via Probabilistic Representations and Its Applications.
ICALP
Zhenjian Lu, Igor C. Oliveira
2021 J jnl
An Efficient Coding Theorem via Probabilistic Representations and its Applications.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor Carboni Oliveira
2021 J jnl
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1.
Electron. Colloquium Comput. Complex.
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira
2021 A* conf
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹.
ICALP
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor C. Oliveira
2021 J jnl
Pseudodeterministic Algorithms and the Structure of Probabilistic Time.
CoRR
Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam
2021 J jnl
Pseudodeterministic Algorithms and the Structure of Probabilistic Time.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
2021 A* conf
Pseudodeterministic algorithms and the structure of probabilistic time.
STOC
Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam
2020 A conf
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates.
CCC
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2020 J jnl
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates.
CoRR
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2020 J jnl
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates.
Electron. Colloquium Comput. Complex.
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2020 J jnl
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.
ACM Trans. Comput. Theory
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
2019 A* conf
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.
ICALP
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
2019 J jnl
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis
2018 J jnl
Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates.
Electron. Colloquium Comput. Complex.
Valentine Kabanets, Zhenjian Lu
2018 — conf
Satisfiability and Derandomization for Small Polynomial Threshold Circuits.
APPROX-RANDOM
Valentine Kabanets, Zhenjian Lu
2018 J jnl
Satisfiability and Derandomization for Small Polynomial Threshold Circuits.
Electron. Colloquium Comput. Complex.
Valentine Kabanets, Zhenjian Lu
2017 J jnl
A Polynomial Restriction Lemma with Applications.
Electron. Colloquium Comput. Complex.
Valentine Kabanets, Daniel M. Kane, Zhenjian Lu
2017 A* conf
A polynomial restriction lemma with applications.
STOC
Valentine Kabanets, Daniel M. Kane, Zhenjian Lu