A fundamental question in computer science is: Is it harder to solve $n$ instances independently than to solve them simultaneously? This question, known as the direct sum question or direct sum theorem, has been paid much attention in several research fields. Despite its importance, however, little has been discovered in many other research fields. In this paper, we introduce a novel framework that extends to classical/quantum query complexity, PAC-learning for machine learning, statistical estimation theory, and more. Within this framework, we establish several fundamental direct sum theorems. The main contributions of this paper include: (i) establishing a complete characterization of the amortized query/oracle complexities, and (ii) proving tight direct sum theorems when the error is small. Note that in our framework, every oracle access needs to be performed \emph{classically} even in the quantum setting. This can be thought of one limitation of this work. As a direct consequence of our results, we obtain the following: (A) The first known asymptotic separation of the randomized query complexity. Specifically, we show that there is a function $f: \{0, 1\}^k \to \{0, 1\}$ and small error $\varepsilon > 0$ such that solving $n$ instances simultaneously requires the query complexity $\tilde{O}(n\sqrt{k})$ but solving one instance with the same error has the complexity $\tildeΩ(k)$. In communication complexity this type of separation was previously given in~Feder, Kushilevitz, Naor and Nisan (1995). (B) The query complexity counterpart of the ``information = amortized communication" relation, one of the most influential results in communication complexity shown by Braverman and Rao (2011) and further investigated by Braverman (2015). We hope that our results will provide further interesting applications in the future.
A fundamental question in computer science is: Is it harder to solve n instances independently than to solve them simultaneously? This question, known as the direct sum question or direct sum theorem, has been paid much attention in several research fields. Despite its importance, however, little has been discovered in many other research fields. In this paper, we introduce a novel framework that extends to classical/quantum query complexity, PAC-learning for machine learning, statistical estimation theory, and more. Within this framework, we establish several fundamental direct sum theorems. The main contributions of this paper include: (i) establishing a complete characterization of the amortized query/oracle complexities, and (ii) proving tight direct sum theorems when the error is small. Note that in our framework, every oracle access needs to be performed \emph{classically} even in the quantum setting. This can be thought of one limitation of this work. As a direct consequence of our results, we obtain the following: (A) The first known asymptotic separation of the randomized query complexity. Specifically, we show that there is a function f:{0,1}k→{0,1} and small error ε>0 such that solving n instances simultaneously requires the query complexity O~(nk) but solving one instance with the same error has the complexity Ω~(k). In communication complexity this type of separation was previously given in~Feder, Kushilevitz, Naor and Nisan (1995). (B) The query complexity counterpart of the ``information = amortized communication" relation, one of the most influential results in communication complexity shown by Braverman and Rao (2011) and further investigated by Braverman (2015). We hope that our results will provide further interesting applications in the future.
We establish two results regarding the query complexity of bounded-error randomized algorithms. Bounded-error separation theorem. There exists a total function f : {0,1}^n -> {0,1} whose epsilon-error randomized query complexity satisfies overline{R}_epsilon(f) = Omega(R(f) * log 1/epsilon). Strong direct sum theorem. For every function f and every k >= 2, the randomized query complexity of computing k instances of f simultaneously satisfies overline{R}_epsilon(f^k) = Theta(k * overline{R}_{epsilon/k}(f)). As a consequence of our two main results, we obtain an optimal superlinear direct-sum-type theorem for randomized query complexity: there exists a function f for which R(f^k) = Theta(k log k * R(f)). This answers an open question of Drucker (2012). Combining this result with the query-to-communication complexity lifting theorem of Göös, Pitassi, and Watson (2017), this also shows that there is a total function whose public-coin randomized communication complexity satisfies R^{cc}(f^k) = Theta(k log k * R^{cc}(f)), answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).
This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation f and any error tolerance ε∈[0,1], we prove limn→∞nRε(fn)=(1−ε)R0(f). Thus the amortization converts bounded-error into zero error with the exact multiplicative factor 1−ε. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function ORn∘f, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.
Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting Q(f∘g)=Θ(Q(f)Q(g)) for all Boolean functions f and g; a direct sum theorem asserting that computing k copies of a function (or search problem) costs Ω(k) times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires Ω(k) times the cost of computing one copy to bounded error.
However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution μ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing k copies of f when the input comes from the product distribution μk instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions.
In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the γ2 norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.
Consider the expected query complexity of computing the k-fold direct product f⊗k of a function f to error ε with respect to a distribution μk . One strategy is to sequentially compute each of the k copies to error ε/k with respect to μ and apply the union bound. We prove a strong direct sum theorem showing that this naive strategy is essentially optimal. In particular, computing a direct product necessitates a blowup in both query complexity and error. Strong direct sum theorems contrast with results that only show a blowup in query complexity or error but not both. There has been a long line of such results for distributional query complexity, dating back to (Impagliazzo, Raz, Wigderson 1994) and (Nisan, Rudich, Saks 1994), but a strong direct sum theorem had been elusive. A key idea in our work is the first use of the Hardcore Theorem (Impagliazzo 1995) in the context of query complexity. We prove a new “resilience lemma" that accompanies it, showing that the hardcore of f⊗k is likely to remain dense under arbitrary partitions of the input space.
The "direct product problem" is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k. We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1 - ε in computing the Boolean function f on input distribution μ, then for α ≤ 1, every αεTk-query algorithm has success probability at most (2αε(1 - ε))kin computing the fc-fold direct product f⊗kcorrectly on k independent inputs from μ. In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability. Using this DPT, we show that for an absolute constant α >; 0, the worst-case success probability of any αR2(f)k-query randomized algorithm for f⊗kfalls exponentially with k. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k). Our proof technique involves defining and analyzing a collec tion of martingales associated with an algorithm attempting to solve f⊗k. Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.
Direct-sum questions in (two-party) communication complexity ask whether two parties, Alice and Bob, can compute the value of a function f on l inputs (x_1,y_1),...,(x_l,y_l) more efficiently than by applying the best protocol for f, independently on each input (x_i,y_i). In spite of significant efforts to understand these questions (under various communication-complexity measures), the general question is still far from being well understood. In this paper, we offer a multiparty view of these questions: The direct-sum setting is just a two-player system with Alice having inputs x_1,...,x_l, Bob having inputs y_1,...,y_l and the desired output is f(x_1,y_1),...,f(x_l,y_l). The naive solution of solving the l problems independently, is modeled by a network with l (disconnected) pairs of players Alice i and Bob i, with inputs x_i,y_i respectively, and communication only within each pair. Then, we consider an intermediate ("star") model, where there is one Alice having l inputs x_1,...,x_l and l players Bob_1,...,Bob_l holding y_1,...,y_l, respectively (in fact, we consider few variants of this intermediate model, depending on whether communication between each Bob i and Alice is point-to-point or whether we allow broadcast). Our goal is to get a better understanding of the relation between the two extreme models (i.e., of the two-party direct-sum question). If, for instance, Alice and Bob can do better (for some complexity measure) than solving the l problems independently, we wish to understand what intermediate model already allows to do so (hereby understanding the "source" of such savings). If, on the other hand, we wish to prove that there is no better solution than solving the l problems independently, then our approach gives a way of breaking the task of proving such a statement into few (hopefully, easier) steps. We present several results of both types. Namely, for certain complexity measures, communication problems f and certain pairs of models, we can show gaps between the complexity of solving f on l instances in the two models in question; while, for certain other complexity measures and pairs of models, we can show that such gaps do not exist (for any communication problem f). For example, we prove that if only point-to-point communication is allowed in the intermediate "star" model, then significant savings are impossible in the public-coin randomized setting. On the other hand, in the private-coin randomized setting, if Alice is allowed to broadcast messages to all Bobs in the "star" network, then some savings are possible. While this approach does not lead yet to new results on the original two-party direct-sum question, we believe that our work gives new insights on the already-known direct-sum results, and may potentially lead to more such results in the future.