Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Zeyong Li:

TR24-061 | 5th April 2024
Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi

Improved Lower Bounds for 3-Query Matching Vector Codes

A Matching Vector ($\mathbf{MV}$) family modulo a positive integer $m \ge 2$ is a pair of ordered lists $\mathcal{U} = (\mathbf{u}_1, \cdots, \mathbf{u}_K)$ and $\mathcal{V} = (\mathbf{v}_1, \cdots, \mathbf{v}_K)$ where $\mathbf{u}_i, \mathbf{v}_j \in \mathbb{Z}_m^n$ with the following property: for any $i \in [K]$, the inner product $\langle \mathbf{u}_i, \mathbf{v}_i \rangle ... more >>>

TR24-049 | 7th March 2024
Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

Oblivious Classes Revisited: Lower Bounds and Hierarchies

In this work we study oblivious complexity classes. Among our results:
1) For each $k \in \mathbb{N}$, we construct an explicit language $L_k \in O_2P$ that cannot be computed by circuits of size $n^k$.
2) We prove a hierarchy theorem for $O_2TIME$. In particular, for any function $t:\mathbb{N} \rightarrow \mathbb{N}$ ... more >>>

TR23-193 | 3rd December 2023
Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz

On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in ... more >>>

TR23-156 | 26th October 2023
Zeyong Li

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform

Revisions: 1

In a recent breakthrough, Chen, Hirahara and Ren prove that S$_2$E/$_1 \not\subset$ SIZE$[2^n/n]$ by giving a single-valued FS$_2$P algorithm for the Range Avoidance Problem (Avoid) that works for infinitely many input size $n$.

Building on their work, we present a simple single-valued FS$_2$P algorithm for Avoid that works for all ... more >>>

ISSN 1433-8092 | Imprint