A note about claw function with a small range

Andris Ambainis, Kaspars Balodis, Jānis Iraids

In the claw detection problem we are given two functions $f:D\to R$ and $g:D\to R$ ($|D|=n$, $|R|=k$), and we have to determine if there is exist $x,y\in D$ such th…