Computer Science/Discrete Mathematics

A d-dimensional framework is a pair $(G, \vec{p})$ consisting of a finite simple graph $G$ and an embedding $\vec{p}$ of its vertices in $\mathbb{R}^d$. A framework is called rigid if every continuous motion of the vertices in ${\mathbb R}^d$ that...

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send the k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication? This is the...