Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn The Communication Complexity of High-Dimensional Permutations
290
0
0.0
(
0
)
Added by
Adi Shraibman
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the multiparty communication complexity of high dimensional permutations, in the Number On the Forehead (NOF) model. This model is due to Chandra, Furst and Lipton (CFL) who also gave a nontrivial protocol for the Exactly-n problem where three players receive integer inputs and need to decide if their inputs sum to a given integer $n$. There is a considerable body of literature dealing with the same problem, where $(mathbb{N},+)$ is replaced by some other abelian group. Our work can be viewed as a far-reaching extension of this line of work. We show that the known lower bounds for that group-theoretic problem apply to all high dimensional permutations. We introduce new proof techniques that appeal to recent advances in Additive Combinatorics and Ramsey theory. We reveal new and unexpected connections between the NOF communication complexity of high dimensional permutations and a variety of well known and thoroughly studied problems in combinatorics. Previous protocols for Exactly-n all rely on the construction of large sets of integers without a 3-term arithmetic progression. No direct algorithmic protocol was previously known for the problem, and we provide the first such algorithm. This suggests new ways to significantly improve the CFL protocol. Many new open questions are presented throughout.
rate research
Read More
For integers $n$ and $k$, the density Hales-Jewett number $c_{n,k}$ is defined as the maximal size of a subset of $[k]^n$ that contains no combinatorial line. We show that for $k ge 3$ the density Hales-Jewett number $c_{n,k}$ is equal to the maximal size of a cylinder intersection in the problem $Part_{n,k}$ of testing whether $k$ subsets of $[n]$ form a partition. It follows that the communication complexity, in the Number On the Forehead (NOF) model, of $Part_{n,k}$, is equal to the minimal size of a partition of $[k]^n$ into subsets that do not contain a combinatorial line. Thus, the bound in cite{chattopadhyay2007languages} on $Part_{n,k}$ using the Hales-Jewett theorem is in fact tight, and the density Hales-Jewett number can be thought of as a quantity in communication complexity. This gives a new angle to this well studied quantity. As a simple application we prove a lower bound on $c_{n,k}$, similar to the lower bound in cite{polymath2010moser} which is roughly $c_{n,k}/k^n ge exp(-O(log n)^{1/lceil log_2 krceil})$. This lower bound follows from a protocol for $Part_{n,k}$. It is interesting to better understand the communication complexity of $Part_{n,k}$ as this will also lead to the better understanding of the Hales-Jewett number. The main purpose of this note is to motivate this study.
We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high dimensional expansion, which coincides with the earlier definition in terms of two-sided link expanders. Using this definition, we describe an analogue of the Fourier expansion and the Fourier levels of the Boolean hypercube for simplicial complexes. Our analogue is a decomposition into approximate eigenspaces of random walks associated with the simplicial complexes. We then use this decomposition to extend the Friedgut-Kalai-Naor theorem to high-dimensional expanders. Our results demonstrate that a high-dimensional expander can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing only $|X(k-1)|=O(n)$ points in contrast to $binom{n}{k}$ points in the $(k)$-slice (which consists of all $n$-bit strings with exactly $k$ ones). Our random-walk definition and the decomposition has the additional advantage that they extend to the more general setting of posets, which include both high-dimensional expanders and the Grassmann poset, which appears in recent works on the unique games conjecture.
This paper is aimed to investigate some computational aspects of different isoperimetric problems on weighted trees. In this regard, we consider different connectivity parameters called {it minimum normalized cuts}/{it isoperimteric numbers} defined through taking minimum of the maximum or the mean of the normalized outgoing flows from a set of subdomains of vertices, where these subdomains constitute a {it partition}/{it subpartition}. Following the main result of [A. Daneshgar, {it et. al.}, {it On the isoperimetric spectrum of graphs and its approximations}, JCTB, (2010)], it is known that the isoperimetric number and the minimum normalized cut both can be described as ${0,1}$-optimization programs, where the latter one does {it not} admit a relaxation to the reals. We show that the decision problem for the case of taking $k$-partitions and the maximum (called the max normalized cut problem {rm NCP}$^M$) as well as the other two decision problems for the mean version (referred to as {rm IPP}$^m$ and {rm NCP}$^m$) are $NP$-complete problems. On the other hand, we show that the decision problem for the case of taking $k$-subpartitions and the maximum (called the max isoperimetric problem {rm IPP}$^M$) can be solved in {it linear time} for any weighted tree and any $k geq 2$. Based on this fact, we provide polynomial time $O(k)$-approximation algorithms for all differe
We study the communication complexity of computing functions $F:{0,1}^ntimes {0,1}^n rightarrow {0,1}$ in the memoryless communication model. Here, Alice is given $xin {0,1}^n$, Bob is given $yin {0,1}^n$ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x; the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS13), space bounded communication complexity by Brody et al. (ITCS13) and the overlay communication complexity by Papakonstantinou et al. (CCC14). Thus the memoryless communication complexity model provides a unified framework to study space-bounded communication models. We establish the following: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose complexity; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c>1 for which the memoryless communication complexity is at least $c log n$? Note that $cgeq 2+varepsilon$ would imply a $Omega(n^{2+varepsilon})$ lower bound for general formula size, improving upon the best lower bound by Nev{c}iporuk in 1966.
Information-theoretic methods have proven to be a very powerful tool in communication complexity, in particular giving an elegant proof of the linear lower bound for the two-party disjointness function, and tight lower bounds on disjointness in the multi-party number-in-the-hand (NIH) model. In this paper, we study the applicability of information theoretic methods to the multi-party number-on-the-forehead model (NOF), where determining the complexity of disjointness remains an important open problem. There are two basic parts to the NIH disjointness lower bound: a direct sum theorem and a lower bound on the one-bit AND function using a beautiful connection between Hellinger distance and protocols revealed by Bar-Yossef, Jayram, Kumar and Sivakumar [BYJKS04]. Inspired by this connection, we introduce the notion of Hellinger volume. We show that it lower bounds the information cost of multi-party NOF protocols and provide a small toolbox that allows one to manipulate several Hellinger volume terms and lower bound a Hellinger volume when the distributions involved satisfy certain conditions. In doing so, we prove a new upper bound on the difference between the arithmetic mean and the geometric mean in terms of relative entropy. We then apply these new tools to obtain a lower bound on the informational complexity of the AND_k function in the NOF setting. Finally, we discuss the difficulties of proving a direct sum theorem for information cost in the NOF model.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
