2 papers
cs.CC2025
Sign-Rank of -Hamming Distance is Constant
Mika Göös, Nathaniel Harms, Valentin Imbach +1
We prove that the sign-rank of the -Hamming Distance matrix on bits is , independent of the number of bits . This strongly refutes the conjecture of Hatami, Hat…
cs.CC2024
Supercritical Tradeoffs for Monotone Circuits
Mika Göös, Gilbert Maystre, Kilian Risse +1
We exhibit a monotone function computable by a monotone circuit of quasipolynomial size such that any monotone circuit of polynomial depth requires exponential size. This is the fi…