We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.
The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.
The tester is ... more >>>

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, ... more >>>

We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings
$x$ and $y$ is equal, up to logarithmic precision, to the length of the longest shared secret key that
two parties, one having $x$ and the complexity profile of the pair and the ... more >>>