31 citations · 71 across the 12 of their papers we have counts for
14 papers
More about Exact Slow -Nim
Nikolay Chikin, Vladimir Gurvich, Konstantin Knop +2
Given piles of tokens and a positive integer , the game Nim of exact slow -Nim is played as follows. Two players move alternately. In each move, a play…
Haystack Hunting Hints and Locker Room Communication
Artur Czumaj, George Kontogeorgiou, Mike Paterson
We want to efficiently find a specific object in a large unstructured set, which we model by a random -permutation, and we have to do it by revealing just a single element. Clea…
Globe-hopping
Dmitry Chistikov, Olga Goulko, Adrian Kent +1
We consider versions of the grasshopper problem (Goulko and Kent, 2017) on the circle and the sphere, which are relevant to Bell inequalities. For a circle of circumference , w…
Convergence of Opinion Diffusion is PSPACE-complete
Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson +1
We analyse opinion diffusion in social networks, where a finite set of individuals is connected in a directed graph and each simultaneously changes their opinion to that of the maj…
Lower bound for monotone Boolean convolution
Mike S. Paterson
Any monotone Boolean circuit computing the -dimensional Boolean convolution requires at least and-gates. This precisely matches the obvious upper bound.
Maximizing the area of intersection of rectangles
David B. A. Epstein, Mike Paterson
This paper attacks the following problem. We are given a large number of rectangles in the plane, each with horizontal and vertical sides, and also a number . The given li…