For any desired rate $R \in (0,1)$, and gap to list-decoding capacity $\varepsilon > 0$, we give an explicit $n^{O_{\varepsilon}(1)}$ time construction of Reed-Solomon codes over extension fields of size polynomial in the block length $n$ that can be list-decoded from a fraction $1-R-\varepsilon$ of errors with the optimal list-size ... more >>>

We give a short-description decomposition of bounded-width CNFs. For every fixed $\varepsilon>0$, every width-$b$ CNF on $m$ variables is an exact disjoint union of at most $2^{\varepsilon m}$ width-$b$ CNFs, each determined by $2^{O_\varepsilon(b)}\log(m+1)$ satisfying assignments.

For every fixed $d\ge3$, we prove a worst-case size lower bound of $2^{\Omega_d((n\log n)^{1/(d-1)})}$ ... more >>>

We give a $3.5n-o(n)$ lower bound on the size of Boolean circuits over the $B_2$ basis computing an explicit Boolean function F in P. This improves the best previous lower bound of $3.1n-o(n)$ [Li-Yang22].

The proof of the lower bound uses the gate elimination technique, and builds heavily on ideas ... more >>>