We consider algorithms with access to an unknown matrix M ε F n×d via matrixvector products , namely, the algorithm chooses vectors v 1 , ⃛ , v q , and observes Mv 1 , ⃛ , Mv q . Here the v i can be randomized as well as chosen adaptively as a function of Mv 1 , ⃛ , Mv i1 . Motivated by applications of sketching in distributed computation, linear algebra, and streaming models, as well as connections to areas such as communication complexity and property testing, we initiate the study of the number q of queries needed to solve various fundamental problems. We study problems in three broad categories, including linear algebra, statistics problems, and graph problems. For example, we consider the number of queries required to approximate the rank, trace, maximum eigenvalue, and norms of a matrix M; to compute the AND/OR/Parity of each column or row of M, to decide whether there are identical columns or rows in M or whether M is symmetric, diagonal, or unitary; or to compute whether a graph defined by M is connected or trianglefree. We also show separations for algorithms that are allowed to obtain matrixvector products only by querying vectors on the right, versus algorithms that can query vectors on both the left and the right. We also show separations depending on the underlying field the matrixvector product occurs in. For graph problems, we show separations depending on the form of the matrix (bipartite adjacency versus signed edgevertex incidence matrix) to represent the graph. Surprisingly, very few works discuss this fundamental model, and we believe a thorough investigation of problems in this model would be beneficial to a number of different application areas.
more »
« less
Dimensionfree bounds and structural results in communication complexity
The purpose of this article is to initiate a systematic study of dimensionfree relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to perhaps the more common framework in communication complexity where polylogarithmic dependencies on the number of input bits are tolerated.
Dimensionfree bounds are also closely related to structural results, where one seeks to describe the structure of Boolean matrices and functions that have low complexity. We prove such theorems for several communication and query complexity measures as well as various matrix and operator norms. In several other cases we show that such bounds do not exist.
We propose several conjectures, and establish that, in addition to applications in complexity theory, these problems are central to characterization of the idempotents of the algebra of Schur multipliers, and could lead to new extensions of Cohen’s celebrated idempotent theorem regarding the Fourier algebra.
more »
« less
 Award ID(s):
 1947546
 NSFPAR ID:
 10488558
 Publisher / Repository:
 Springer
 Date Published:
 Journal Name:
 Israel Journal of Mathematics
 Volume:
 253
 Issue:
 2
 ISSN:
 00212172
 Page Range / eLocation ID:
 555 to 616
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


The noise sensitivity of a Boolean function f:{0,1}n→{0,1} is one of its fundamental properties. A function of a positive noise parameter δ, it is denoted as NSδ[f]. Here we study the algorithmic problem of approximating it for monotone f, such that NSδ[f]≥1/nC for constant C, and where δ satisfies 1/n≤δ≤1/2. For such f and δ, we give a randomized algorithm performing O(min(1,n√δlog1.5n)NSδ[f]poly(1ϵ)) queries and approximating NSδ[f] to within a multiplicative factor of (1±ϵ). Given the same constraints on f and δ, we also prove a lower bound of Ω(min(1,n√δ)NSδ[f]⋅nξ) on the query complexity of any algorithm that approximates NSδ[f] to within any constant factor, where ξ can be any positive constant. Thus, our algorithm's query complexity is close to optimal in terms of its dependence on n. We introduce a novel descendingascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield previously unknown lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.more » « less

Testing membership in lattices is of practical relevance, with applications to integer programming, error detection in latticebased communication and cryptography. In this work, we initiate a systematic study of {\em local testing} for membership in lattices, complementing and building upon the extensive body of work on locally testable codes. In particular, we formally define the notion of local tests for lattices and present the following: \begin{enumerate} \item We show that in order to achieve low query complexity, it is sufficient to design onesided nonadaptive {\em canonical} tests. This result is akin to, and based on an analogous result for errorcorrecting codes due to BenSasson \etal\ (SIAM J. Computing 35(1) pp121). \item We demonstrate upper and lower bounds on the query complexity of local testing for membership in {\em code formula} lattices. We instantiate our results for code formula lattices constructed from ReedMuller codes to obtain nearlymatching upper and lower bounds on the query complexity of testing such lattices. \item We contrast lattice testing from code testing by showing lower bounds on the query complexity of testing lowdimensional lattices. This illustrates large lower bounds on the query complexity of testing membership in {\em knapsack lattices}. On the other hand, we show that knapsack lattices with bounded coefficients have lowquery testers if the inputs are promised to lie in the span of the lattice. \end{enumerate}more » « less

Tauman Kalai, Yael (Ed.)We study unitary property testing, where a quantum algorithm is given query access to a blackbox unitary and has to decide whether it satisfies some property. In addition to containing the standard quantum query complexity model (where the unitary encodes a binary string) as a special case, this model contains "inherently quantum"; problems that have no classical analogue. Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods. Our main contribution is a generalized polynomial method for unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a marked subspace, and approximating the entanglement entropy of a marked state. We also present a unitary property testingbased approach towards an oracle separation between QMA and QMA(2), a long standing question in quantum complexity theory.more » « less

We introduce several new blackbox reductions that significantly improve the design of adaptive and parameterfree online learning algorithms by simplifying analysis, improving regret guarantees, and sometimes even improving runtime. We reduce parameterfree online learning to online expconcave optimization, we reduce optimization in a Banach space to onedimensional optimization, and we reduce optimization over a constrained domain to unconstrained optimization. All of our reductions run as fast as online gradient descent. We use our new techniques to improve upon the previously best regret bounds for parameterfree learning, and do so for arbitrary norms.more » « less