Source author record

Zhenjian Lu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Information Theory math.IT

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

The classical coding theorem in Kolmogorov complexity states that if an $n$ -bit string $x$ is sampled with probability $δ$ by an algorithm with prefix-free domain then K $(x) \leq \log(1/δ) + O(1)$ . In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that if $x$ can be efficiently sampled with probability $δ$ then rKt $(x) = O(\log(1/δ)) + O(\log n)$ , where rKt denotes the randomized analogue of Levin's Kt complexity. Unfortunately, this result is often insufficient when transferring applications of the classical coding theorem to the time-bounded setting, as it achieves a $O(\log(1/δ))$ bound instead of the information-theoretic optimal $\log(1/δ)$ . We show a coding theorem for rKt with a factor of $2$ . As in previous work, our coding theorem is efficient in the sense that it provides a polynomial-time probabilistic algorithm that, when given $x$ , the code of the sampler, and $δ$ , it outputs, with probability $\ge 0.99$ , a probabilistic representation of $x$ that certifies this rKt complexity bound. Assuming the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt $(x) \leq (2 - o(1)) \cdot \log(1/δ) +$ poly $(\log n)$ . Under a weaker assumption, we exhibit a gap between efficient coding theorems and existential coding theorems with near-optimal parameters. We consider pK $^t$ complexity [GKLO22], a variant of rKt where the randomness is public and the time bound is fixed. We observe the existence of an optimal coding theorem for pK $^t$ , and employ this result to establish an unconditional version of a theorem of Antunes and Fortnow [AF09] which characterizes the worst-case running times of languages that are in average polynomial-time over all P-samplable distributions.

preprint2022arXiv

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 of Kolmogorov complexity. While fruitful interactions between time-bounded Kolmogorov complexity and different areas of theoretical computer science have been known for quite a while (e.g., [Sip83, Ko91, ABK+06, AF09], to name a few), the aforementioned results have led to a renewed interest in this topic. The theory of Kolmogorov complexity is well understood, but many useful results and properties of Kolmogorov complexity are not known to hold in time-bounded settings. This creates technical difficulties or leads to conditional results when applying methods from time-bounded Kolmogorov complexity to algorithms and complexity theory. Perhaps even more importantly, in many cases it is necessary to consider randomised algorithms. Since random strings have high complexity, the classical theory of time-bounded Kolmogorov complexity might be inappropriate in such contexts. To mitigate these issues and develop a theory of time-bounded Kolmogorov complexity that survives in the setting of randomised computations, some recent papers [Oli19, LO21, LOS21, GKLO22, LOZ22] have explored probabilistic notions of time-bounded Kolmogorov complexity, such as $\mathsf{rKt}$ complexity [Oli19], $\mathsf{rK}^t$ complexity [LOS21], and $\mathsf{pK}^t$ complexity [GKLO22]. These measures consider different ways of encoding an object via a probabilistic representation. In this survey, we provide an introduction to probabilistic time-bounded Kolmogorov complexity and its applications, highlighting many open problems and research directions.

preprint2020arXiv

Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size- $s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$ . We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$ , for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be the maximum $k$ -party NOF randomized communication complexity of $\mathcal{G}$ . We show: (1) The Generalized Inner Product function $GIP^k_n$ cannot be computed in $FORMULA[s]\circ \mathcal{G}$ on more than $1/2+\varepsilon$ fraction of inputs for $s = o \! \left ( \frac{n^2}{ \left(k \cdot 4^k \cdot {R}^{(k)}(\mathcal{G}) \cdot \log (n/\varepsilon) \cdot \log(1/\varepsilon) \right)^{2}} \right).$ As a corollary, we get an average-case lower bound for $GIP^k_n$ against $FORMULA[n^{1.99}]\circ PTF^{k-1}$ . (2) There is a PRG of seed length $n/2 + O\left(\sqrt{s} \cdot R^{(2)}(\mathcal{G}) \cdot\log(s/\varepsilon) \cdot \log (1/\varepsilon) \right)$ that $\varepsilon$ -fools $FORMULA[s] \circ \mathcal{G}$ . For $FORMULA[s] \circ LTF$ , we get the better seed length $O\left(n^{1/2}\cdot s^{1/4}\cdot \log(n)\cdot \log(n/\varepsilon)\right)$ . This gives the first non-trivial PRG (with seed length $o(n)$ ) for intersections of $n$ half-spaces in the regime where $\varepsilon \leq 1/n$ . (3) There is a randomized $2^{n-t}$ -time $\#$ SAT algorithm for $FORMULA[s] \circ \mathcal{G}$ , where $t=Ω\left(\frac{n}{\sqrt{s}\cdot\log^2(s)\cdot R^{(2)}(\mathcal{G})}\right)^{1/2}.$ In particular, this implies a nontrivial #SAT algorithm for $FORMULA[n^{1.99}]\circ LTF$ . (4) The Minimum Circuit Size Problem is not in $FORMULA[n^{1.99}]\circ XOR$ . On the algorithmic side, we show that $FORMULA[n^{1.99}] \circ XOR$ can be PAC-learned in time $2^{O(n/\log n)}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.