Collision problems are important problems in complexity theory and cryptography with diverse applications. Previous fruitful works have mainly focused on query models. Driven by various applications, several works by Bauer, Farshim and Mazaheri (CRYPTO 2018), Itsykson and Riazanov (CCC 2021), Göös and Jain (RANDOM 2022) independently proposed the communication version ... more >>>

For any fixed $t$, we present two fine-grained reductions of the problem of approximately counting the number of $t$-cliques in a graph to the problem of detecting a $t$-clique in a graph.
One of our reductions is slightly better than the prior reduction of Dell, Lapinskas, and Meeks (SODA20) and ... more >>>

Boolean function $F(x,y)$ for $x,y \in \{0,1\}^n$ is an XOR function if $F(x,y) = f(x\oplus y)$ for some function $f$ on $n$ input bits, where $\oplus$ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing Fourier analytic technique. For total XOR functions it is known ... more >>>