We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\bigl(\frac{\log n}{\log\log n}\bigr)^{1/k}$ in (Lin, 2019) and $(\log n)^{1/\text{poly}(k)}$ in (Karthik, Laekhanukit, and Manurangsi, 2019). Here $k$ is the yes-case guarantee and $n$ is the ... more >>>

Given any fixed constant $0<\varepsilon<1$ and a matrix space
$\mathcal{B}=\langle B_1,\ldots,B_m\rangle\le\mathbb{Q}^{n\times n}$,
we give a deterministic $NC^3$ algorithm that outputs a matrix \(A\in\mathcal{B}\) such that $rank(A)\geq (1-\varepsilon) crk(\mathcal{B})$,
where $crk(\mathcal{B})$ denotes the maximum rank of a matrix in $\mathcal{B}$. This complements the recent breakthrough of Chatterjee, Ghosh, Gurjar, Raj, and ... more >>>

Braverman, Rao, Raz, and Yehudayoff (SICOMP 2014) showed that there is an explicit pseudorandom generator (PRG) that fools standard-order regular read-once branching programs (ROBPs) with seed length
$$
O(\log n \cdot \log \log n + \log n \cdot \log(wd/\epsilon)),
$$
where $w$ is the width of ... more >>>