Quantum Distributed Complexity of Set Disjointness on a Line

• URL: http://arxiv.org/abs/2002.11795v5
• Date: Tue, 8 Mar 2022 22:07:19 GMT
• Title: Quantum Distributed Complexity of Set Disjointness on a Line
• Authors: Frederic Magniez and Ashwin Nayak
• Abstract summary: Set Disjointness on a Line is a variant of the Set Disjointness problem in a distributed computing scenario. We prove an unconditional lower bound of $widetildeOmegabig(sqrt[3]n d2+sqrtn, big)$ rounds for Set Disjointness on a Line with $d + 1$ processors.
• Score: 3.2590610391507444
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Set Disjointness on a Line is a variant of the Set Disjointness problem in a distributed computing scenario with $d+1$ processors arranged on a path of length $d$. It was introduced by Le Gall and Magniez (PODC 2018) for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path consists of O$( \log n)$ qubits for $n$-bit inputs. We prove an unconditional lower bound of $\widetilde{\Omega}\big(\sqrt[3]{n d^2}+\sqrt{n} \, \big)$ rounds for Set Disjointness on a Line with $d + 1$ processors. The result gives us a new lower bound of $\widetilde{\Omega} \big( \sqrt[3]{n\delta^2}+\sqrt{n} \, \big)$ on the number of rounds required for computing the diameter $\delta$ of any $n$-node network with quantum messages of size O$(\log n)$ in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. The information-theoretic technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to the number of rounds in this query model. We provide an algorithm for Set Disjointness in this query model with round complexity that matches the round lower bound stated above, up to a polylogarithmic factor. This presents a barrier for obtaining a better round lower bound for Set Disjointness on the Line. At the same time, it hints at the possibility of better communication protocols for the problem.

Related papers

• Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
  We propose variance- optimistic sliding (SVOGS) method, which takes the advantage of the finite-sum structure in the objective. We prove $mathcal O(delta D2/varepsilon)$, communication complexity of $mathcal O(n+sqrtndelta D2/varepsilon)$, and local calls of $tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$.
  arXiv  Detail & Related papers  (2024-05-25T08:34:49Z)
• Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
  We study the problem of reaching agreement in a synchronous distributed system by $n$ autonomous parties, when the communication links from/to faulty parties can omit messages. We design a randomized algorithm that works in $O(sqrtnlog2 n)$ rounds and sends $O(n2log3 n)$ communication bits. We prove that no MC algorithm can work in less than $Omega(fracn2maxR,nlog n)$ rounds if it uses less than $O(R)$ calls to
  arXiv  Detail & Related papers  (2024-05-08T02:17:10Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• A Framework for Distributed Quantum Queries in the CONGEST Model [0.0]
  We give a general framework for implementing quantum query algorithms in Quantum CONGEST. We generalize the protocol for the distributed Deutsch-Jozsa problem. We also give quantum speedups for the problems of cycle detection and computation.
  arXiv  Detail & Related papers  (2022-02-22T15:18:39Z)
• Cut query algorithms with star contraction [4.570617424761779]
  We study the complexity of determining the edge connectivity of a simple graph with cut queries. We show that there is a bounded-error randomized algorithm that computes edge connectivity with $O(n)$ cut queries. We also show that there is a bounded-error quantum algorithm that computes edge connectivity with $O(sqrtn)$ cut queries.
  arXiv  Detail & Related papers  (2022-01-14T21:13:49Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  We show that a given suboptimality $epsilon0$ is achieved master/workers networks in $Omegabig. We then propose algorithms matching the lower bounds either types of networks (up to log-overs) We assess effectiveness of the proposed algorithms on a robust logistic regression problem.
  arXiv  Detail & Related papers  (2021-07-22T14:25:16Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks [0.0]
  The computation of the diameter is one of the most central problems in distributed computation. We show a $tilde O(sqrtnD)$-round quantum distributed algorithm for exact diameter computation, where $D$ denotes the diameter. This shows a separation between the computational power of quantum and classical algorithms in the CONGEST model.
  arXiv  Detail & Related papers  (2018-04-09T11:24:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.