We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for ``easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an $n$-variate Boolean function $f$ computable by some unknown small circuit ... more >>>

We provide a new framework for establishing strong lower bounds on the nonnega- tive rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance ... more >>>

Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research ... more >>>