An approximation algorithm for approximation rank (2008)
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a...
A direct product theorem for discrepancy (2008)
Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in the distributional, randomized, quantum, and even unbounded error models of communication. We...
Approximation norms and duality for communication complexity lower bounds (2008)
Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound...
Disjointness is hard in the multi-party number on the forehead model (2007)
We show that disjointness requires randomized communication Omega(frac{n^{1/2k}}{(k-1)2^{k-1}2^{2^{k-1}}}) in the general k-party number-on-the-forehead model of complexity. The previous best lower...
Lower bounds in communication complexity based on factorization norms (2007)
We introduce a new method to derive lower bounds on randomized and quantum communication complexity. Our method is based on factorization norms, a notion from Banach Space theory. As we show, our...
Lower bounds in communication complexity based on factorization norms (2007)
We introduce a new method to derive lower bounds on randomized and quantum communication complexity. Our method is based on factorization norms, a notion from Banach Space theory. This approach gives...
Learning complexity vs. communication complexity (2006)
This paper has two main focal points. We first consider an important class of machine learning algorithms- large margin classifiers (Support Vector Machines belong to this class). The notion of...
Rank, trace-norm and max-norm (2005)
Abstract. We study the rank, trace-norm and max-norm as complexity measures of matrices, focusing on the problem of fitting a matrix with matrices having low complexity. We present generalization...