6 papers
Pseudodeterministic Communication Complexity
Mika Göös, Nathaniel Harms, Artur Riazanov +3
We exhibit an -bit partial function with randomized communication complexity but such that any completion of this function into a total one requires randomized commu…
No Constant-Cost Protocol for Point--Line Incidence
Mika Göös, Nathaniel Harms, Florian K. Richter +1
Alice and Bob are given -bit integer pairs and , respectively, and they must decide if . We prove that the randomised communication complexity of this Poi…
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…
Equality is Far Weaker than Constant-Cost Communication
Mika Göös, Nathaniel Harms, Artur Riazanov
We exhibit an -bit communication problem with a constant-cost randomized protocol but which requires deterministic (or even non-deterministic) queries to an Equality…
Constant-Cost Communication is not Reducible to k-Hamming Distance
Yuting Fang, Mika Göös, Nathaniel Harms +1
Every known communication problem whose randomized communication cost is constant (independent of the input size) can be reduced to -Hamming Distance, that is, solved with a con…
Better Boosting of Communication Oracles, or Not
Nathaniel Harms, Artur Riazanov
Suppose we have a two-party communication protocol for which allows the parties to make queries to an oracle computing ; for example, they may query an Equality oracle. To t…