XOR Functions and Beyond in the Random Query ModelResearch Paper
In the random query model an algorithm cannot choose which input bit to read. At each of time steps it receives a pair with drawn uniformly at random, and between steps it keeps only bits of memory. The model, introduced by Raz and Zhan (ITCS 2020), describes streaming access to unordered data and learning from random examples, and it asks a…