Partition arguments in multiparty communication complexity

Consider the “Number in Hand” multiparty communication complexity model, where k players holding inputs x₁,…,x_k∈{0,1}ⁿ communicate to compute the value f(x₁,…,x_k) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem.In this paper, we study the power of partition arguments. Our two main results are very different in nature:

(i)

For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Ω(n), while partition arguments can only yield an Ω(logn) lower bound. The same holds for nondeterministiccommunication complexity.

(ii)

For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the “log-rank conjecture” in communication complexity. We also observe that, in the case of computing relations (search problems), very large gaps do exist.

We conclude with two results on the multiparty “fooling set technique”, another method for obtaining communication complexity lower bounds.     

An information statistics approach to data stream and communication complexity

We present a new method for proving strong lower bounds in communication complexity. This method is based on the notion of the conditional information complexity of a function which is the minimum amount of information about the inputs that has to be revealed by a communication protocol for the function. While conditional information complexity is a lower bound on communication complexity, we show that it also admits a direct sum theorem. Direct sum decomposition reduces our task to that of proving conditional information complexity lower bounds for simple problems (such as the AND of two bits). For the latter, we develop novel techniques based on Hellinger distance and its generalizations.Our paradigm leads to two main results:(1) An improved lower bound for the multi-party set-disjointness problem in the general communication complexity model, and a nearly optimal lower bound in the one-way communication model. As a consequence, we show that for any real k>2, approximating the kth frequency moment in the data stream model requires essentially Ω(n1−2/k) space; this resolves a conjecture of Alon et al. (J. Comput. System Sci. 58(1) (1999) 137).(2) A lower bound for the L_p approximation problem in the general communication model; this solves an open problem of Saks and Sun (in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 360-369). As a consequence, we show that for p>2, approximating the L_p norm to within a factor of n^ε in the data stream model with constant number of passes requires Ω(n1−4ε−2/p) space.     

Hadamard tensors and lower bounds on multiparty communication complexity

We develop a new method for estimating the discrepancy of tensors associated with multiparty communication problems in the “Number on the Forehead” model of Chandra, Furst, and Lipton. We define an analog of the Hadamard property of matrices for tensors in multiple dimensions and show that any k-party communication problem represented by a Hadamard tensor must have Ω(n/2 ^k ) multiparty communication complexity. We also exhibit constructions of Hadamard tensors. This allows us to obtain Ω(n/2 ^k ) lower bounds on multiparty communication complexity for a new class of explicitly defined Boolean functions.     

Strong computational lower bounds via parameterized complexity

We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k)no(k) for any function f, even if we restrict the parameter values to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be of the order Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/?)no(1/?) for any function f unless an unlikely collapse occurs in parameterized complexity theory.     

Decision algorithms for multiplayer noncooperative games of incomplete information

Extending the complexity results of Reif [1,2] for two player games of incomplete information, this paper (see also [3]) presents algorithms for deciding the outcome for various classes of multiplayer games of incomplete information, i.e., deciding whether or not a team has a winning strategy for a particular game. Our companion paper, [4] shows that these algorithms are indeed asymptotically optimal by providing matching lower bounds. The classes of games to which our algorithms are applicable include games which were not previously known to be decidable. We apply our algorithms to provide alternative upper bounds, and new time-space trade-offs on the complexity of multiperson alternating Turing machines [3]. We analyze the algorithms to characterize the space complexity of multiplayer games in terms of the complexity of deterministic computation on Turing machines.In hierarchical multiplayer games, each additional clique (subset of players with the same information) increases the complexity of the outcome problem by a further exponential. We show that an S(n) space bounded k-player game of incomplete information has a deterministic time upper bound of k + 1 repeated exponentials of S(n). Furthermore, S(n) space bounded k-player blindfold games have a deterministic space upper bound of k repeated exponentials of S(n). This paper proves that this exponential blow-up can occur.We also show that time bounded games do not exhibit such hierarchy. A T(n) time bounded blindfold multiplayer game, as well as a T(n) time bounded multiplayer game of incomplete information, has a deterministic space bound of T(n).     

One-write algorithms for multivalued regular and atomic registers

This paper presents an algorithm for implementing a k-valued regular register (the logical register) using binary regular registers (the physical registers) that requires only one physical write per logical write. The same algorithm using binary atomic registers implements a k-valued atomic register. The algorithm is simple to describe and depends on properties of paths in a related graph. Two lower bounds are given on the number of registers required by one-write implementations in the regular case. The first lower bound, , holds for a fairly general class of algorithms. The second lower bound holds for a restricted class of implementations and implies that our algorithm is optimal for this class. Both lower bounds improve on the best previously known lower bound, which was k. The two lower bounds also hold for the atomic case under further restrictions. Received: 9 June 2000     

A strong direct product theorem for quantum query complexity

We show that quantum query complexity satisfies a strong direct product theorem. This means that computing k copies of a function with fewer than k times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in k. For a boolean function f, we also show an XOR lemma—computing the parity of k copies of f with fewer than k times the queries needed for one copy implies that the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, characterizes bounded-error quantum query complexity. In particular, we show that the multiplicative adversary bound is always at least as large as the additive adversary bound, which is known to characterize bounded-error quantum query complexity.     

Graph Complexity and Slice Functions

Abstract. A graph-theoretic approach to study the complexity of Boolean functions was initiated by Pudlák, Rödl, and Savický [PRS] by defining models of computation on graphs. These models generalize well-known models of Boolean complexity such as circuits, branching programs, and two-party communication complexity. A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of {2-slice functions} would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. We prove, for instance, that a lower bound of n ^1+Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2 ^Ω(?) lower bound on the formula size over a complete basis of another explicit function g on l variables, where l=Θ( log n) . We also consider lower bound questions for depth-3 bipartite graph complexity. We prove a weak lower bound on this measure using algebraic methods. For instance, our result gives a lower bound of Ω(( log n) ³ / ( log log n) ⁵ ) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. Lower bounds for depth-3 bipartite graph complexity are motivated by two significant applications: (i) a lower bound of n ^Ω(1) on the depth-3 complexity of an explicit n -vertex bipartite graph would yield superlinear size lower bounds on log-depth Boolean circuits for an explicit function, and (ii) a lower bound of $\exp((\log \log n)^{\omega(1)})$ would give an explicit language outside the class Σ ₂ ^cc of the two-party communication complexity as defined by Babai, Frankl, and Simon [BFS]. Our lower bound proof is based on sign-representing polynomials for DNFs and lower bounds on ranks of ±1 matrices even after being subjected to sign-preserving changes to their entries. For the former, we use a result of Nisan and Szegedy [NS] and an idea from a recent result of Klivans and Servedio [KS]. For the latter, we use a recent remarkable lower bound due to Forster [F1].     

Information Lower Bounds via Self-Reducibility

We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD is linear even under the uniform distribution, which strengthens the Ω(n) bound recently shown by Kerenidis et al. (2012), and answers an open problem from Chakrabarti et al. (2012). In our second result we prove that the information cost of IP_n is arbitrarily close to the trivial upper bound n as the permitted error tends to zero, again strengthening the Ω(n) lower bound recently proved by Braverman and Weinstein (Electronic Colloquium on Computational Complexity (ECCC) 18, 164 2011). Our proofs demonstrate that self-reducibility makes the connection between information complexity and communication complexity lower bounds a two-way connection. Whereas numerous results in the past (Chakrabarti et al. 2001; Bar-Yossef et al. J. Comput. Syst. Sci. 68(4), 702–732 2004; Barak et al. 2010) used information complexity techniques to derive new communication complexity lower bounds, we explore a generic way in which communication complexity lower bounds imply information complexity lower bounds in a black-box manner.     

The BNS-Chung criterion for multi-party communication complexity

The "Number on the Forehead" model of multi-party communication complexity was first suggested by Chandra, Furst and Lipton. The best known lower bound, for an explicit function (in this model), is a lower bound of , where n is the size of the input of each player, and k is the number of players (first proved by Babai, Nisan and Szegedy). This lower bound has many applications in complexity theory. Proving a better lower bound, for an explicit function, is a major open problem. Based on the result of BNS, Chung gave a sufficient criterion for a function to have large multi-party communication complexity (up to ). In this paper, we use some of the ideas of BNS and Chung, together with some new ideas, resulting in a new (easier and more modular) proof for the results of BNS and Chung. This gives a simpler way to prove lower bounds for the multi-party communication complexity of a function. Received: December 12, 1997.     

Tradeoff lower lounds for stack machines

A space-bounded Stack Machine is a regular Turing Machine with a read-only input tape, several space-bounded read-write work tapes, and an unbounded stack. Stack Machines with a logarithmic space bound have been connected to other classical models of computation, such as polynomial-time Turing Machines (P) (Cook in J Assoc Comput Mach 18:4–18, 1971) and polynomial size, polylogarithmic depth, bounded fan-in circuits (NC) e.g., Borodin et al. (SIAM J Comput 18, 1989). In this paper, we present significant new lower bounds and techniques for Stack Machines. This comes in the form of a trade-off lower bound between space and number of passes over the input tape. Specifically, we give an explicit permuted inner product function such that any Stack Machine computing this function requires either ${\Omega (N^{1/4 - \epsilon})}$ space or ${\Omega (N^{1/4 - \epsilon})}$ number of passes for every constant ${\epsilon > 0}$ , where N is the input size. In the case of logarithmic space Stack Machines, this yields an unconditional ${\Omega (N^{1/4 - \epsilon})}$ lower bound for the number of passes. To put this result in perspective, we note that Stack Machines with logarithmic space and a single pass over the input can compute Parity, Majority, as well as certain languages outside NC. The latter follows from Allender (J Assoc Comput Mach 36:912–928, 1989), conditional on the widely believed complexity assumption that PSPACE ${\subsetneq}$ EXP. Our technique is a novel communication complexity reduction, thereby extending the already wide range of models of computation for which communication complexity can be used to obtain lower bounds. Informally, we show that a k-player number-in-hand (NIH) communication protocol for a base function f can efficiently simulate a space- and pass-bounded Stack Machine for a related function F, which consists of several “permuted” instances of f, bundled together by a combining function h. Trade-off lower bounds for Stack Machines then follow from known communication complexity lower bounds. The framework for this reduction was given by Beame & Huynh-Ngoc (2008), who used it to obtain similar trade-off lower bounds for Turing Machines with a constant number of pass-bounded external tapes. We also prove that the latter cannot efficiently simulate Stack Machines, conditional on the complexity assumption that E ${\not \subset}$ PSPACE. It is the treatment of an unbounded stack which constitutes the main technical novelty in our communication complexity reduction.     

On the Number of Edges of a Uniform Hypergraph with a Range of Allowed Intersections

We study the quantity p(n, k, t₁, t₂) equal to the maximum number of edges in a k-uniform hypergraph having the property that all cardinalities of pairwise intersections of edges lie in the interval [t₁, t₂]. We present previously known upper and lower bounds on this quantity and analyze their interrelations. We obtain new bounds on p(n, k, t₁, t₂) and consider their possible applications in combinatorial geometry problems. For some values of the parameters we explicitly evaluate the quantity in question. We also give a new bound on the size of a constant-weight error-correcting code.     

Lower bounds in spectral tests for vectors of nonsuccessive values produced by multiple recursive generator with some zero multipliers

L'Ecuyer develops lower bounds for the maximum distance of the parallel hyperplanes generated by the vectors of nonsuccessive random numbers (RNs) obtained from multiple recursive generators (MRGs). In this paper, a stronger bound, twice that obtained by L'Ecuyer, is derived. For k^th-order MRGs with fewer than k terms in the recursive relationship, much stronger bounds are found. Large distance implies bad lattice structure. In designing RN generators, this factor should be taken into consideration.     

A characterization of average case communication complexity

It is well known that the average case deterministic communication complexity is bounded below by an entropic quantity, which one would now call deterministic information complexity. In this paper we show a corresponding upper bound. We also improve known lower bounds for the public coin Las Vegas communication complexity by a constant factor.     

Kolmogorov complexity and combinatorial methods in communication complexity

We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods.We use Kolmogorov complexity for three different things: first, to give a general lower bound in terms of Kolmogorov mutual information; second, to prove an alternative to Yao’s minmax principle based on Kolmogorov complexity; and finally, to identify hard inputs.We show that our method implies the rectangle and corruption bounds, known to be closely related to the subdistribution bound. We apply our method to the hidden matching problem, a relation introduced to prove an exponential gap between quantum and classical communication. We then show that our method generalizes the VC dimension and shatter coefficient lower bounds. Finally, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result.     

Lower Bounds for k-DNF Resolution on Random 3-CNFs

We prove exponential lower bounds on refutations of a random 3-CNF with linear number of clauses by k-DNF Resolution for ${k\leq \sqrt{\log n/\log\log n}}$ . For this we design a specially tailored random restrictions that preserve the structure of the input random 3-CNF while mapping every k-DNF with large covering number to one with high probability. Next we make use of the switching lemma for small restrictions by Segerlind, Buss and Impagliazzo to prove the lower bound. This work improves the previously known lower bound for Res(2) system on random 3-CNFs by Atserias, Bonet and Esteban and the result of Segerlind, Buss, Impagliazzo stating that random O(k ²)-CNF do not possess short Res(k) refutations.     

Relations between diagonalization,proof systems,and complexity gaps

In this paper we study diagonal processes over time bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. This replaces the traditional “clock” in resource bounded diagonalization by formal proofs about running times and establishes close relations between properties of proof systems and existence of sharp time bounds for one-tape Turing machine complexity classes. These diagonalization methods also show that the Gap Theorem for resource bounded computations can hold only for those complexity classes which differ from the corresponding provable complexity classes. Furthermore, we show that there exist recursive time bounds T(n) such that the class of languages for which we can formally prove the existence of Turing machines which accept them in time T(n) differs from the class of languages accepted by Turing machines for which we can prove formally that they run in time T(n). We also investigate the corresponding problems for tape bound computations and discuss the difference time and tapebounded computations.     

Polynomial certificates for propositional classes

This paper studies the complexity of learning classes of expressions in propositional logic from equivalence queries and membership queries. In particular, we focus on bounding the number of queries that are required to learn the class ignoring computational complexity. This quantity is known to be captured by a combinatorial measure of concept classes known as the certificate complexity. The paper gives new constructions of polynomial size certificates for monotone expressions in conjunctive normal form (CNF), for unate CNF functions where each variable affects the function either positively or negatively but not both ways, and for Horn CNF functions. Lower bounds on certificate size for these classes are derived showing that for some parameter settings the new certificate constructions are optimal. Finally, the paper gives an exponential lower bound on the certificate size for a natural generalization of these classes known as renamable Horn CNF functions, thus implying that the class is not learnable from a polynomial number of queries.     

Comparing the strength of query types in property testing: The case of k-colorability

We study the power of four query models in the context of property testing in general graphs, where our main case study is the problem of testing k-colorability. Two query types, which have been studied extensively in the past, are pair queries and neighbor queries. The former corresponds to asking whether there is an edge between any particular pair of vertices, and the latter to asking for the i ^th neighbor of a particular vertex. We show that while for pair queries testing k-colorability requires a number of queries that is a monotone decreasing function in the average degree d, the query complexity in the case of neighbor queries remains roughly the same for every density and for large values of k. We also consider a combined model that allows both types of queries, and we propose a new, stronger, query model, related to the field of Group Testing. We give upper and lower bounds on the query complexity for one-sided error in all the models, where the bounds are nearly tight for three of the models. In some of the cases, our lower bounds extend to two-sided error algorithms. The problem of testing k-colorability was previously studied in the contexts of dense graphs and of sparse graphs, and in our proofs we unify approaches from those cases, and also provide some new tools and techniques that may be of independent interest.     

On Spectral Bounds for the k-Partitioning of Graphs

When executing processes on parallel computer systems a major bottle-neck is interprocessor communication. One way to address this problem is to minimize the communication between processes that are mapped to different processors. This translates to the k-partitioning problem of the corresponding process graph, where k is the number of processors. The classical spectral lower bound of (|V|/2k)\sum ^k _i=1λ _i for the k-section width of a graph is well known. We show new relations between the structure and the eigenvalues of a graph and present a new method to get tighter lower bounds on the k-section width. This method makes use of the level structure defined by the k-section. We define a global expansion property and prove that for graphs with the same k-section width the spectral lower bound increases with this global expansion. We also present examples of graphs for which our new bounds are tight up to a constant factor.