Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Xin Lyu:

TR23-114 | 8th August 2023
Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs ... more >>>

TR22-102 | 15th July 2022
Venkatesan Guruswami, Xin Lyu, Xiuhan Wang

Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness

In the range avoidance problem, the input is a multi-output Boolean circuit with more outputs than inputs, and the goal is to find a string outside its range (which is guaranteed to exist). We show that well-known explicit construction questions such as finding binary linear codes achieving the Gilbert-Varshamov bound ... more >>>

TR22-021 | 19th February 2022
Xin Lyu

Improved Pseudorandom Generators for $\mathrm{AC}^0$ Circuits

We give PRG for depth-$d$, size-$m$ $\mathrm{AC}^0$ circuits with seed length $O(\log^{d-1}(m)\log(m/\varepsilon)\log\log(m))$. Our PRG improves on previous work [TX13, ST19, Kel21] from various aspects. It has optimal dependence on $\frac{1}{\varepsilon}$ and is only one “$\log\log(m)$” away from the lower bound barrier. For the case of $d=2$, the seed length tightly ... more >>>

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

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

TR21-003 | 6th January 2021
Lijie Chen, Xin Lyu

Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma

In this work we prove that there is a function $f \in \textrm{E}^\textrm{NP}$ such that, for every sufficiently large $n$ and $d = \sqrt{n}/\log n$, $f_n$ ($f$ restricted to $n$-bit inputs) cannot be $(1/2 + 2^{-d})$-approximated by $\textrm{F}_2$-polynomials of degree $d$. We also observe that a minor improvement ... more >>>

TR20-150 | 7th October 2020
Lijie Chen, Xin Lyu, Ryan Williams

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether $\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely ... more >>>

ISSN 1433-8092 | Imprint