Nathaniel Harms

activity

20242026

collaborators

Showing 2025Show all

3 papers · 1 filter

cs.CC2025

Pseudodeterministic Communication Complexity

Mika Göös, Nathaniel Harms, Artur Riazanov +3

We exhibit an $n$ -bit partial function with randomized communication complexity $O (lo g n)$ but such that any completion of this function into a total one requires randomized commu…

cs.CC2025

Equality is Far Weaker than Constant-Cost Communication

Mika Göös, Nathaniel Harms, Artur Riazanov

We exhibit an $n$ -bit communication problem with a constant-cost randomized protocol but which requires $n^{Ω (1)}$ deterministic (or even non-deterministic) queries to an Equality…

cs.CC2025

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

Mika Göös, Nathaniel Harms, Valentin Imbach +1

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, Hat…

Pseudodeterministic Communication Complexity

Equality is Far Weaker than Constant-Cost Communication

Sign-Rank of k-Hamming Distance is Constant

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