Demo Section: Dynamic Block

We propose an extension of Yao's standard two-party communication model, where Alice and Bob respectively hold probability distributions p and q over inputs to a function f, rather than singleton inputs. Their goal is to estimate E[f(x,y)] to within additive error eps where x is drawn from p and y is drawn (independently) from q. We refer to this as the distributed estimation problem for f. We motivate this problem by showing that communication problems that have been studied in sketching, databases and learning are instantiations of distributed estimation for various functions f. Our goal is to understand how the required communication scales with the communication complexity of f and the error parameter eps. 

The naive sampling protocol achieves communication that scales as O(1/eps^2). We design a new debiasing protocol for arbitrary bounded functions that requires communication only linear in 1/\eps, and gives better variance reduction than random sampling. We develop a novel spectral technique to show lower bounds for distributed estimation, and use it to show that the Equality function is the easiest full rank Boolean function for distributed estimation. This technique yields tight lower bounds for most functions, with set-disjointness being the notable exception. 

Based on joint work with Raghu Meka (UCLA), Prasad Raghavendra (UC Berkeley), Mihir Singhal (UC Berkeley) and Avi Wigderson (IAS).  

Two vector spaces of the same finite dimension are related by a linear isomorphism; that’s how the dimension is defined. Similarly, two simple subalgebras over complex numbers that are closed under conjugate transpose are related by a unitary conjugation whenever their dimensions are the same. On a many-qubit system, the unitary isomorphism can be written as a unitary quantum circuit, of which we ask about the complexity. For example, a simple lightcone argument proves that the algebra of all logical operators of any nontrivial quantum error correcting code is isomorphic to that of unencoded qubits by a deep unitary circuit. Essentially, this has been the only explicit (rather than random) example pair of isomorphic simple subalgebras where the isomorphism complexity lower bound is proved. Here, we report another kind of an explicit simple subalgebra on a two-dimensional grid of 2n qubits, isomorphic to the algebra of all operators on n qubits, where any geometrically local unitary circuit realizing any such isomorphism must have depth linear in the grid’s diameter.