All reports by Author Zhenjian Lu:

__
TR21-041
| 15th March 2021
__

Zhenjian Lu, Igor Carboni Oliveira#### An Efficient Coding Theorem via Probabilistic Representations and its Applications

__
TR21-040
| 15th March 2021
__

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira#### Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1

__
TR21-039
| 15th March 2021
__

Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam#### Pseudodeterministic Algorithms and the Structure of Probabilistic Time

__
TR20-018
| 18th February 2020
__

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira#### Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

__
TR19-022
| 23rd February 2019
__

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis#### Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

Revisions: 1

__
TR18-115
| 11th June 2018
__

Valentine Kabanets, Zhenjian Lu#### Satisfiability and Derandomization for Small Polynomial Threshold Circuits

__
TR18-012
| 20th January 2018
__

Valentine Kabanets, Zhenjian Lu#### Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates

__
TR17-026
| 17th February 2017
__

Valentine Kabanets, Daniel Kane, Zhenjian Lu#### A Polynomial Restriction Lemma with Applications

Zhenjian Lu, Igor Carboni Oliveira

A probabilistic representation of a string $x \in \{0,1\}^n$ is given by the code of a randomized algorithm that outputs $x$ with high probability [Oliveira, ICALP 2019]. We employ probabilistic representations to establish the first unconditional Coding Theorem in time-bounded Kolmogorov complexity. More precisely, we show that if a distribution ... more >>>

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

We develop a general framework that characterizes strong average-case lower bounds against circuit classes $\mathcal{C}$ contained in $\mathrm{NC}^1$, such as $\mathrm{AC}^0[\oplus]$ and $\mathrm{ACC}^0$. We apply this framework to show:

- Generic seed reduction: Pseudorandom generators (PRGs) against $\mathcal{C}$ of seed length $\leq n -1$ and error $\varepsilon(n) = n^{-\omega(1)}$ can ... more >>>

Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of $BPTIME$: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.

1. A new pseudorandom generator and its consequences: We build on techniques developed to ... more >>>

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira

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 ... more >>>

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $\theta$, for a given parameter $\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>>

Valentine Kabanets, Zhenjian Lu

A polynomial threshold function (PTF) is defined as the sign of a polynomial $p\colon\bool^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth.

Satisfiability (#SAT). We give the first zero-error randomized algorithm ... more >>>

Valentine Kabanets, Zhenjian Lu

We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree $d$ on $n$ inputs, our PRG for error $\epsilon$ has the seed ... more >>>

Valentine Kabanets, Daniel Kane, Zhenjian Lu

A polynomial threshold function (PTF) of degree $d$ is a boolean function of the form $f=\mathrm{sgn}(p)$, where $p$ is a degree-$d$ polynomial, and $\mathrm{sgn}$ is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is ... more >>>