Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Zhenjian Lu:

TR23-076 | 24th May 2023
Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam

Polynomial-Time Pseudodeterministic Construction of Primes

A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.

... more >>>

TR23-070 | 9th May 2023
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Bounded Relativization

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called *bounded relativization*. For a complexity class $C$, we say that a statement is *$C$-relativizing* if the statement holds relative ... more >>>

TR23-035 | 22nd March 2023
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira

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

Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) ... more >>>

TR22-081 | 26th May 2022
Zhenjian Lu, Igor Oliveira

Theory and Applications of Probabilistic Kolmogorov Complexity

Diverse applications of Kolmogorov complexity to learning [CIKK16], circuit complexity [OPS19], cryptography [LP20], average-case complexity [Hir21], and proof search [Kra22] have been discovered in recent years. Since the running time of algorithms is a key resource in these fields, it is crucial in the corresponding arguments to consider time-bounded variants ... more >>>

TR22-072 | 15th May 2022
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

Understanding the relationship between the worst-case and average-case complexities of $\mathrm{NP}$ and of other subclasses of $\mathrm{PH}$ is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the ... more >>>

ISSN 1433-8092 | Imprint