检索结果-内蒙古大学图书馆

On the communication complexity of AND Functions

IEEE TRANSACTIONS ON INFORMATION THEORY 2021年第7期67卷 4929-4935页

作者： Wu, Hsin-Lung Natl Taipei Univ Dept Comp Sci & Informat Engn Taipei 237 Taiwan

Log-rank conjecture is one of challenging problems in communication complexity. It is known to hold for some special function classes such as XOR functions f(x circle plus y) when the outer function f is monotone, symmetric, AC(0), low F-2-degree, linear threshold or read-k. However, for AND functions f(x boolean AND y), Log-rank conjecture is only known to hold when the outer function is a monotone function or a function with small alternating numbers. In this paper, we show that Log-rank conjecture holds for AND functions whose outer functions are read-once F-2-degree polynomials, constant-F-2-degree polynomials, and symmetric functions. For read-once and symmetric AND functions, their proof are based on the elementary analysis of Mobius sparsity of the outer functions and designing efficient protocols for computing the corresponding AND functions in terms of the Mobius sparsity of their outer functions. For a constant-F-2-degree AND function f(x boolean AND y), we use the concept of the variable rank to design a decision tree for computing f where the tree depth is bounded above by a polynomial in the logarithm of the Mobius sparsity of f. The communication protocol can be obtained easily from the constructed decision tree. Our results deepen the understanding of the log-rank conjecture for AND functions.

关键词： communication complexity log-rank conjecture AND functions symmetric functions constant-degree polynomials read-once polynomials

来源：评论

学校读者我要写书评

暂无评论

On communication complexity of Fixed Point Computation

引用

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 2021年第4期9卷 1–27页

作者： Ganor, Anat Karthik, C. S. Palvolgyi, Domotor Hebrew Univ Jerusalem Sch Comp Sci & Engn Rothberg Bldg IL-9190401 Jerusalem Israel Weizmann Inst Sci 234 Herzl St IL-7610001 Rehovot Israel Eotvos Lorand Univ Inst Math Pazmany Peter Setimy 1-C H-1117 Budapest Hungary

Brouwer's fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOGS 2016) initiated the study of fixed point computation in the two-player communication model, where each player gets a function from [0, 1](n) to [0, 1](n), and their goal is to find an approximate fixed point of the composition of the two functions. They left it as an open question to show a lower bound of 2(Omega(n)) for the (randomized) communication complexity of this problem, in the range of parameters which make it a total search problem. We answer this question affirmatively. Additionally, we introduce two natural fixed point problems in the two-player communication model. Each player is given a function from [0, 1](n) to [0, 1](n/2) and their goal is to find an approximate fixed point of the concatenation of the functions. Each player is given a function from [0.1](n) to [0, 1](n), and their goal is to find an approximate fixed point of the mean of the functions. We show a randomized communication complexity lower bound of 2(Omega(n)) for these problems (for some constant approximation factor). Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner's lemma) in the two-player communication model: A triangulation T of the d-simplex is publicly known and one player is given a set S-A subset of T and a coloring function from S-A to {0, ..., d/2), and the other player is given a set S-B subset of T and a coloring function from S-B to {d/2 + 1, ..., d), such that S-A boolean OR S-B = T, and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of vertical bar T vertical bar(Omega(1)) for the aforementioned problem as well (when d is large). On the positive side, we show that if d <= 4 then there is a deterministic protocol for the Sperner problem with O((log vertical bar T vertical bar)(2)) b

关键词： Brouwer's fixed point theorem communication complexity Nash equilibrium Sperner's lemma

来源：评论

学校读者我要写书评

暂无评论

Refuting the Direct Sum Conjecture for Total Functions in Deterministic communication complexity 25

Refuting the Direct Sum Conjecture for Total Functions in De...

引用

Proceedings of the 57th Annual ACM Symposium on Theory of Computing

作者： Simon Mackenzie Abdallah Saffidine Unaffiliated Sydney Australia Potassco Solutions Potsdam Germany

ISBN: (纸本)9798400715105

In communication complexity the input of a function f:X×Y→Z is distributed between two players Alice and Bob. If Alice knows only x∈X and Bob only y∈Y, how much information must Alice and Bob share to be able to elicit the value of f(x,y)? Do we need ℓ more resources to solve ℓ instances of a problem? This question is the direct sum question and has been studied in many computational models. In this paper we focus on the case of 2-party deterministic communication complexity and give a counterexample to the direct sum conjecture in its strongest form. To do so we exhibit a family of functions for which the complexity of solving ℓ instances is less than (1−ϵ)ℓ times the complexity of solving one instance for some small enough ϵ>0. We use a customised method in the analysis of our family of total functions, showing that one can force the alternation of rounds between players. This idea allows us to exploit the integrality of the complexity measure to create an increasing gap between the complexity of solving the instances independently with that of solving them together.

关键词： communication complexity

来源：评论

学校读者我要写书评

暂无评论

Average-Case communication complexity of Statistical Problems 34

Average-Case Communication Complexity of Statistical Problem...

引用

Conference on Learning Theory (COLT)

作者： Rashtchian, Cyrus Woodruff, David P. Ye, Peng Zhu, Hanlin Univ Calif San Diego La Jolla CA 92093 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA Tsinghua Univ Beijing Peoples R China

We study statistical problems, such as planted clique, its variants, and sparse principal component analysis in the context of average-case communication complexity. Our motivation is to understand the statistical-computational trade-offs in streaming, sketching, and query-based models. communication complexity is the main tool for proving lower bounds in these models, yet many prior results do not hold in an average-case setting. We provide a general reduction method that preserves the input distribution for problems involving a random graph or matrix with planted structure. Then, we derive two-party and multi-party communication lower bounds for detecting or finding planted cliques, bipartite cliques, and related problems. As a consequence, we obtain new bounds on the query complexity in the edge-probe, vector-matrix-vector, matrix-vector, linear sketching, and F-2-sketching models. Many of these results are nearly tight, and we use our techniques to provide simple proofs of some known lower bounds for the edge-probe model.

关键词： Planted clique sketching query complexity communication complexity

来源：评论

学校读者我要写书评

暂无评论

The communication complexity of Payment Computation 2021

The Communication Complexity of Payment Computation

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Dobzinski, Shahar Ron, Shiri Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9781450380539

Let (f, P) be an incentive compatible mechanism where f is the social choice function and P is the payment function. In many important settings, f uniquely determines P (up to a constant) and therefore a common approach is to focus on the design of f and neglect the role of the payment function. Fadel and Segal [JET, 2009] question this approach by taking the lenses of communication complexity: can it be that the communication complexity of an incentive compatible mechanism that implements f (that is, computes both the output and the payments) is much larger than the communication complexity of computing the output? I.e., can it be that cc(IC) (f) >> cc(f)? Fadel and Segal show that for every f, cc(IC) (f) <= exp(cc(f)). They also show that fully computing the incentive compatible mechanism is strictly harder than computing only the output: there exists a social choice function f such that cc(IC) (f) = cc(f ) + 1. In a followup work, Babaioff, Blumrosen, Naor, and Schapira [EC'08] provide a social choice function f such that cc(IC) (f) = circle minus(n . cc(f)), where n is the number of players. The question of whether the exponential upper bound of Fadel and Segal is tight remained wide open. In this paper we solve this question by explicitly providing a function f such that cc(IC) (f) = exp(cc(f)). In fact, we establish this via two very different proofs. In contrast, we show that if the players are risk-neutral and we can compromise on a randomized truthful-in-expectation implementation (and not on deterministic ex-post implementation) gives that cc(TIE) (f ) = poly(n, cc(f)) for every function f, as long as the domain of f is single parameter or a convex multi-parameter domain. We also provide efficient algorithms for deterministic computation of payments in several important domains.

关键词： communication complexity Payment Computation Mechanism Design

来源：评论

学校读者我要写书评

暂无评论

The Randomized communication complexity of Randomized Auctions 2021

The Randomized Communication Complexity of Randomized Auctio...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Rubinstein, Aviad Zhao, Junyao Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9781450380539

We study the communication complexity of incentive compatible auction-protocols between a monopolist seller and a single buyer with a combinatorial valuation function over n items. Motivated by the fact that revenue-optimal auctions are randomized (as well as by an open problem of Babaioff, Gonczarowski, and Nisan), we focus on the randomized communication complexity of this problem (in contrast to most prior work on deterministic communication). We design simple, incentive compatible, and revenue-optimal auction-protocols whose expected communication complexity is much (in fact infinitely) more efficient than their deterministic counterparts. We also give nearly matching lower bounds on the expected communication complexity of approximately-revenue-optimal auctions. These results follow from a simple characterization of incentive compatible auction-protocols that allows us to prove lower bounds against randomized auction-protocols. In particular, our lower bounds give the first approximation-resistant, exponential separation between communication complexity of incentivizing vs implementing a Bayesian incentive compatible social choice rule, settling an open question of Fadel and Segal.

关键词： Algorithmic game theory communication complexity

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for Monotone Arithmetic Circuits via communication complexity 2021

Lower Bounds for Monotone Arithmetic Circuits via Communicat...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Chattopadhyay, Arkadev Datta, Rajit Mukhopadhyay, Partha TIFR Mumbai Maharashtra India CMI Chennai Tamil Nadu India

ISBN: (纸本)9781450380539

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first improvement to this classical result: we construct a family of polynomials P-n in n variables, each of its monomials has nonnegative coefficient, such that P-n can be computed by a polynomial-size depth-three formula but every monotone circuit computing it has size 2(Omega(n1/4/log(n))). The polynomial P-n embeds the SINK o XOR function devised recently by Chattopadhyay, Mande and Sherif (2020) to refute the Log-Approximate-Rank Conjecture in communication complexity. To prove our lower bound for P-n, we develop a general connection between corruption of combinatorial rectangles by any function f circle XOR and corruption of product polynomials by a certain polynomial P-f that is an arithmetic embedding of f. This connection should be of independent interest. Using further ideas from communication complexity, we construct another family of set-multilinear polynomials f(n,m )such that both F-n,F-m - epsilon . f(n,m) and F-n,F-m + epsilon.f(n,m) have monotone circuit complexity 2(Omega(n/log(n))) if epsilon >= 2(-Omega(m)) and F-n,F-m := Pi(n)(i=1) (x(i,1 )+ ... + x(i,m)), with m = O(n/log n). The polynomials f(n,m) have 0/1 coefficients and are in VNP. Proving such lower bounds for monotone circuits has been advocated recently by Hrubeg (2020) as a first step towards proving lower bounds against general circuits via his new approach.

关键词： Monotone Arithmetic Circuits communication complexity Lower Bounds

来源：评论

学校读者我要写书评

暂无评论

New Bounds on the Half-Duplex communication complexity 47th

New Bounds on the Half-Duplex Communication Complexity

引用

47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Dementiev, Yuriy Ignatiev, Artur Sidelnik, Vyacheslav Smal, Alexander Ushakov, Mikhail St Petersburg State Univ St Petersburg Russia Russian Acad Sci Steklov Math Inst St Petersburg Dept St Petersburg Russia

ISBN: (纸本)9783030677305;9783030677312

In this work, we continue the research started in [6], where the authors suggested to study the half-duplex communication complexity. Unlike the classical model of communication complexity introduced by Yao, in the half-duplex model, Alice and Bob can speak or listen simultaneously, as if they were talking using a walkie-talki.e. The motivation for such a communication model comes from the study of the KRW conjecture. Following the open questions formulated in [6], we prove lower bounds for the disjointness function in all variants of half-duplex models and an upper bound in the half-duplex model with zero, that separates disjointness from the inner product function in this setting. Next, we prove lower and upper bounds on the half-duplex complexity of the Karchmer-Wigderson games for the counting functions and for the recursive majority function, adapting the ideas used in the classical communication complexity. Finally, we define the non-deterministic half-duplex complexity and establish bounds connecting it with non-deterministic complexity in the classical model.

关键词： communication complexity Half-duplex communication Karchmer-wigderson games

来源：评论

学校读者我要写书评

暂无评论

The communication complexity of Multiparty Set Disjointness under Product Distributions 2021

The Communication Complexity of Multiparty Set Disjointness ...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Dershowitz, Nachum Oshman, Rotem Roth, Tal Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9781450380539

In the multiparty number-in-hand set disjointness problem, we have k players, with private inputs X-1, ..., X-k subset of [n]. The players' goal is to check whether boolean AND(k)(l=1) X-l = empty set. It is known that in the shared blackboard model of communication, set disjointness requires Omega(n log k + k) bits of communication, and in the coordinator model, it requires Omega(kn) bits. However, these two lower bounds require that the players' inputs can be highly correlated. We study the communication complexity of multiparty set disjointness under product distributions, and ask whether the problem becomes significantly easier, as it is known to become in the two-party case. Our main result is a nearly-tight bound of (Theta) over tilde (n(1-1/k) + k) for both the shared blackboard model and the coordinator model. This shows that in the shared blackboard model, as the number of players grows, having independent inputs helps less and less;but in the coordinator model, when k is very large, having independent inputs makes the problem much easier. Both our upper and our lower bounds use new ideas, as the original techniques developed for the two-party case do not scale to more than two players.

关键词： communication complexity set disjointness product distributions

来源：评论

学校读者我要写书评

暂无评论

Public vs. private randomness in simultaneous multi-party communication complexity

引用

THEORETICAL COMPUTER SCIENCE 2020年 810卷 72-81页

作者： Fischer, Orr Oshman, Rotem Zwick, Uri Tel Aviv Univ Comp Sci Dept Tel Aviv Israel

In simultaneous number-in-hand multi-party communication protocols, we have k players, who each receive a private input, and wish to compute a joint function of their inputs. The players simultaneously each send a single message to a referee, who then outputs the value of the function. The cost of the protocol is the total number of bits sent to the referee. For two players, it is known that giving the players a public (shared) random string is much more useful than private randomness: public-coin protocols can be unboundedly better than deterministic protocols, while private-coin protocols can only give a quadratic improvement on deterministic protocols. We extend the two-player gap to multiple players, and show that the private-coin communication complexity of a k-player function f is at least Omega(root D(f)) for any k >= 2. Perhaps surprisingly, this bound is tight: although one might expect the gap between private-coin and deterministic protocols to grow with the number of players, we show that the All-Equality function, where each player receives n bits of input and the players must determine if their inputs are all the same, can be solved by a private-coin protocol with (O) over tilde(root nk + k) bits. Since All-Equality has deterministic complexity Theta(nk), this shows that sometimes the gap scales only as the square root of the number of players, and consequently the number of bits each player needs to send actually decreases as the number of players increases. We also consider the Exists-Equality function, where we ask whether there is a pair of players that received the same input, and prove a nearly-tight bound of (Theta) over tilde (k root n) for it. (C) 2018 Elsevier B.V. All rights reserved.

关键词： communication complexity Simultaneous communication complexity Multi-party communication complexity Number in hand

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：