\( \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:


August 18, 2014