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.
Raghavendra's famous result from 2008 fully characterizes the inapproximability of every maximum constraint satisfaction problem (Max-CSP). However, the result inherently loses perfect completeness.
