Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR25-060 | 6th May 2025
Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov

Sign-Rank of $k$-Hamming Distance is Constant

We prove that the sign-rank of the $k$-Hamming Distance matrix on $n$ bits is $2^{O(k)}$, independent of the number of bits $n$. This strongly refutes the conjecture of Hatami, Hatami, Pires, Tao, and Zhao (RANDOM 2022), and Hatami, Hosseini, and Meng (STOC 2023), repeated in several other papers, that the ... more >>>


TR25-059 | 6th May 2025
Emanuele Viola

Communication complexity of pointer chasing via the fixed-set lemma

Revisions: 1

I give a very simple, apparently new proof of a tight communication lower bound for pointer chasing.

more >>>

TR25-058 | 5th May 2025
Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan

Generalised Linial-Nisan Conjecture is False for DNFs

Comments: 1

Aaronson (STOC 2010) conjectured that almost $k$-wise independence fools constant-depth circuits; he called this the generalised Linial-Nisan conjecture. Aaronson himself later found a counterexample for depth-3 circuits. We give here an improved counterexample for depth-2 circuits (DNFs). This shows, for instance, that Bazzi's celebrated result ($k$-wise independence fools DNFs) cannot ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint