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.
You have n candidates to fill up n vacant positions in an office. The question is which candidate gets which position? To decide this, you ask non-candidates to vote. There are n!
A Simple Stochastic Game is a game with a reachability objective played by two players on a directed graph. Each vertex of the graph is either controlled by one of the players or is a probabilistic vertex.
The Minimum Circuit Size problem is a fundamental problem in theoretical computer science, connecting cryptography, learning theory, structural complexity, etc., One of the longstanding open problems is whether determining the size of a smallest c
Can a sender encode a pair of messages (m0, m1) jointly, and send their encoding over (say) a binary erasure channel, so that the receiver can decode exactly one of the two messages and the sender does not know which one?
How does one store a graph in the database? Typically the vertices are labelled by a set {1, 2, ..., n}. The edges can be denoted in many different ways: adjacency matrix, incidence matrix, adjacency list, to name a few.
Optimal resource allocation in networks gives rise to some of the most fundamental problems at the intersection of algorithms, stochastic processes, and learning.
We know that for matrices A and B, AB is not the same as BA in general. But suppose B is a polynomial in A, like B = A^2 - 3A + I (note I = A^0). Then AB is indeed the same as BA.
Tiling of a surface is acted upon by its automorphism group. The tilings with single vertex orbit, the transitive tilings, are well studied since antiquity.
