Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Kuan Cheng:

TR24-048 | 4th March 2024
Kuan Cheng, Yichuan Wang

$BPL\subseteq L-AC^1$

Whether $BPL=L$ (which is conjectured to be equal), or even whether $BPL\subseteq NL$, is a big open problem in theoretical computer science. It is well known that $L-NC^1\subseteq L\subseteq NL\subseteq L-AC^1$. In this work we will show that $BPL\subseteq L-AC^1$, which was not known before. Our proof is based on ... more >>>

TR23-128 | 30th August 2023
Xue Chen, Kuan Cheng, Xin Li, Songtao Mao

Random Shortening of Linear Codes and Application

Random linear codes (RLCs) are well known to have nice combinatorial properties and near-optimal parameters in many different settings. However, getting explicit constructions matching the parameters of RLCs is challenging, and RLCs are hard to decode efficiently. This motivated several previous works to study the problem of partially derandomizing RLCs, ... more >>>

ISSN 1433-8092 | Imprint