In the last few days, a Denial of Service attack was launched on universities in Israel, leading the administrators of the Israel Academic network to block access to it from the global internet. Consequently, websites such as ECCC have been accessible only from within the Israeli and European academic networks.
It seems that this blocking was just removed, and we hope it will not be put back in the future.
Needless to say, deciding on such blocking is not in our control, but we do apologize for this disruption of service.
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 >>>
