A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical protocols on _total_ Boolean functions in the two-party interactive model. The answer appears to be ``No. In 2002,
Razborov proved this conjecture for so far the most general class of functions F(x, y) = f(x_1 * y_1, x_2 * y_2, ..., x_n * y_n), where f is a_symmetric_ Boolean function on n Boolean inputs, and x_i, y_i are the ith bit of x and y, respectively. His elegant proof critically depends on the symmetry of f. We develop a lower-bound method that does not require symmetry and prove the conjecture for a broader class of functions. Each of those functions F(x, y) is obtained by what we call the ``block-composition of a ``building block g : {0, 1}^k by {0, 1}^k --> {0, 1}, with an f : {0, 1}^n -->{0, 1}, such that F(x, y) = f(g(x_1, y_1), g(x_2, y_2), ..., g(x_n, y_n)), where x_i and y_i are the ith k-bit block of x and y, respectively. We show that as long as g itself is ``hard enough, its block-composition with an_arbitrary_ f has polynomially related quantum and classical communication complexities. Our approach gives an alternative proof for Razborovs result (albeit with a slightly weaker parameter), and establishes new quantum lower bounds. For example, when g is the Inner Product function for k=Omega(log n), the_deterministic_ communication complexity of its block-composition with_any_ f is asymptotically at most the quantum complexity to the power of 7.
Many hard algorithmic problems dealing with graphs, circuits, formulas and constraints admit polynomial-time upper bounds if the underlying graph has small treewidth. The same problems often encourage reducing the maximal degree of vertices to simpli
fy theoretical arguments or address practical concerns. Such degree reduction can be performed through a sequence of splittings of vertices, resulting in an _expansion_ of the original graph. We observe that the treewidth of a graph may increase dramatically if the splittings are not performed carefully. In this context we address the following natural question: is it possible to reduce the maximum degree to a constant without substantially increasing the treewidth? Our work answers the above question affirmatively. We prove that any simple undirected graph G=(V, E) admits an expansion G=(V, E) with the maximum degree <= 3 and treewidth(G) <= treewidth(G)+1. Furthermore, such an expansion will have no more than 2|E|+|V| vertices and 3|E| edges; it can be computed efficiently from a tree-decomposition of G. We also construct a family of examples for which the increase by 1 in treewidth cannot be avoided.
