\(
\def\<#1>{\left<#1\right>}
\newcommand{\OR}{\mathrm{OR}}
\newcommand{\XOR}{\mathrm{XOR}}
\newcommand{\SUM}{\mathrm{SUM}}
\newcommand{\GEN}{\mathrm{GEN}}
\newcommand{\Cov}{c}
\newcommand{\Dec}{d}
\newcommand{\tr}{\mathrm{tr}}
\newcommand{\pr}{\mathrm{rk}_+}
\newcommand{\br}{\mathrm{rk}_{\lor}}
\newcommand{\Geq}{\succcurlyeq}
\newcommand{\Leq}{\preccurlyeq}
\)
On XOR complexity of circulant matrices
Due to a very recent result [1], the bound in Theorem 5.9 can
be slightly improved:
Theorem ([1]): There is a constant $c>1$ such that, for any circulant $n\times n$ matrix $A$,
\[
\XOR(A) \Leq n\ln n \cdot c^{\ln^* n}.
\]
Here $\ln^* n$ is the iterated logarithm whose value is the smallest natural number $k$
such that the $k$-fold logarithm $\ln \cdots \ln n \leq 1$:
\[
\lfloor \underbrace{\ln \ldots \ln}_{\ln^*n}\ n \rfloor = 1.
\]
That is, the factor $\ln\ln n$ in
Thm. 5.9 can be replaced by $c^{\ln^* n}$.
This leads to a minor improvement of some gaps mentioned in Section 5.4, including the
gap (5.3).
References:
- [1] D. Harvey, J. van der Hoeven, G. Lecerf: Faster polynomial multiplication over finite fields, http://arxiv.org/abs/1407.3361 (submitted on 12 Jul 2014)
August 18, 2014