In a secure multi-party computation problem, players are required to compute a function of their private inputs without revealing any extra information about this input to other players.
Meta-complexity refers to the study of complexity of problems that are themselves about computational complexity. The canonical meta-complexity problem in the Boolean world is MCSP (Minimum Circuit Size Problem).
We consider two-player stochastic games on a graph. Two-player stochastic games are a generalization of two-player games and Markov decision processes. Each state in the graph is controlled by one of the two players P1 and P2.
The "nearest neighbor (NN) classifier" labels a new data instance by taking a majority vote over the k most similar instances seen in the past. With an appropriate setting of k, it is capable of modeling arbitrary decision rules.
Over the last three decades, the online bipartite matching (OBM) problem has emerged as a central problem in the area of Online Algorithms. Perhaps even more important is its role in the area of Matching-Based Market Design.