Zhenjian Lu

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Lower bounds on the overhead of indistinguishability obfuscation	2026-07-24	Paper
Optimal coding for randomized Kolmogorov complexity and its applications	2026-06-23	Paper
On the complexity of avoiding heavy elements	2026-06-23	Paper
Polynomial-time pseudodeterministic construction of primes Journal of the ACM	2026-06-03	Paper
Majority vs. approximate linear sum and average-case complexity below NC^1	2026-05-12	Paper
An efficient coding theorem via probabilistic representations and its applications	2026-05-12	Paper
Exact search-to-decision reductions for time-bounded Kolmogorov complexity	2026-01-28	Paper
Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity	2026-01-14	Paper
Polynomial-time pseudodeterministic construction of primes	2025-08-15	Paper
One-way functions and pKt complexity	2025-07-23	Paper
Bounded relativization	2024-11-19	Paper
Probabilistic Kolmogorov complexity with applications to average-case complexity	2024-07-05	Paper
Optimal coding theorems in time-bounded Kolmogorov complexity	2024-06-24	Paper
A duality between one-way functions and average-case symmetry of information	2024-05-08	Paper
scientific article; zbMATH DE number 7829266 (Why is no real title available?)	2024-04-09	Paper
Pseudodeterministic algorithms and the structure of probabilistic time Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing	2023-11-14	Paper
Pseudodeterministic algorithms and the structure of probabilistic time Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing	2023-11-14	Paper
Algorithms and lower bounds for comparator circuits from shrinkage Algorithmica	2023-06-28	Paper
scientific article; zbMATH DE number 7701424 (Why is no real title available?) (available as arXiv preprint)	2023-06-26	Paper
scientific article; zbMATH DE number 7701424 (Why is no real title available?)	2023-06-26	Paper
Circuit lower bounds for MCSP from local pseudorandom generators ACM Transactions on Computation Theory	2022-12-05	Paper
Circuit lower bounds for MCSP from local pseudorandom generators	2022-07-21	Paper
Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates	2022-07-21	Paper
Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates ACM Transactions on Computation Theory	2022-03-29	Paper
Satisfiability and derandomization for small polynomial threshold circuits	2021-08-04	Paper
A polynomial restriction lemma with applications Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing	2017-08-17	Paper

Research outcomes over time

This page was built for person: Zhenjian Lu