4 Search Results for "Touchette, Dave"

Document
DOI: 10.4230/LIPIcs.CCC.2021.30
On Query-To-Communication Lifting for Adversary Bounds

Authors: Anurag Anshu, Shalev Ben-David, and Srijita Kundu

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.
Cite as

Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On Query-To-Communication Lifting for Adversary Bounds. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 30:1-30:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{anshu_et_al:LIPIcs.CCC.2021.30,
  author =	{Anshu, Anurag and Ben-David, Shalev and Kundu, Srijita},
  title =	{{On Query-To-Communication Lifting for Adversary Bounds}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{30:1--30:39},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.30},
  URN =		{urn:nbn:de:0030-drops-143042},
  doi =		{10.4230/LIPIcs.CCC.2021.30},
  annote =	{Keywords: Quantum computing, query complexity, communication complexity, lifting theorems, adversary method}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.61
Communication Memento: Memoryless Communication Complexity

Authors: Srinivasan Arunachalam and Supartha Podder

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ 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 (in particular, her reply is independent of the information from the previous rounds); 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 some of these different variants of our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space-bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these space-bounded communication complexity models. We establish the following main results: (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 model of computation; (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 c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].
Cite as

Srinivasan Arunachalam and Supartha Podder. Communication Memento: Memoryless Communication Complexity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2021.61,
  author =	{Arunachalam, Srinivasan and Podder, Supartha},
  title =	{{Communication Memento: Memoryless Communication Complexity}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{61:1--61:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.61},
  URN =		{urn:nbn:de:0030-drops-136007},
  doi =		{10.4230/LIPIcs.ITCS.2021.61},
  annote =	{Keywords: Communication complexity, space complexity, branching programs, garden-hose model, quantum computing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.47
The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting

Authors: Mathieu Laurière and Dave Touchette

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
In two-party interactive quantum communication protocols, we study a recently defined notion of quantum information cost (QIC), which has most of the important properties of its classical analogue (IC). Notably, its link with amortized quantum communication complexity has been used to prove an (almost) tight lower bound on the bounded round quantum complexity of Disjointness. However, QIC was defined through a purification of the input state. This is valid for fully quantum inputs and tasks but difficult to interpret even for classical tasks. Also, its link with other notions of information cost that had appeared in the literature was not clear. We settle both these issues: for quantum communication with classical inputs, we characterize QIC in terms of information about the input registers, avoiding any reference to the notion of a purification of the classical input state. We provide an operational interpretation of this new characterization as the sum of the costs of revealing and of forgetting information about the inputs. To obtain this result, we prove a general Information Flow Lemma assessing the transfer of information in general interactive quantum processes. Specializing this lemma to interactive quantum protocols accomplishing classical tasks, we are able to demistify the link between QIC and other previous notions of information cost in quantum protocols. Furthermore, we clarify the link between QIC and IC by simulating quantumly classical protocols. Finally, we apply these concepts to argue that any quantum protocol that does not forget information solves Disjointness on n-bits in Omega(n) communication, completely losing the quadratic quantum speedup. Hence forgetting information is here a necessary feature in order to obtain any significant improvement over classical protocols. We also prove that QIC at 0-error is exactly n for Inner Product, and n (1 - o(1)) for a random Boolean function on n+n bits.
Cite as

Mathieu Laurière and Dave Touchette. The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, p. 47:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lauriere_et_al:LIPIcs.ITCS.2017.47,
  author =	{Lauri\`{e}re, Mathieu and Touchette, Dave},
  title =	{{The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{47:1--47:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.47},
  URN =		{urn:nbn:de:0030-drops-81898},
  doi =		{10.4230/LIPIcs.ITCS.2017.47},
  annote =	{Keywords: Communication Complexity, Information Complexity, Quantum Computation and Information}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.23
Augmented Index and Quantum Streaming Algorithms for DYCK(2)

Authors: Ashwin Nayak and Dave Touchette

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
We show how two recently developed quantum information theoretic tools can be applied to obtain lower bounds on quantum information complexity. We also develop new tools with potential for broader applicability, and use them to establish a lower bound on the quantum information complexity for the Augmented Index function on an easy distribution. This approach allows us to handle superpositions rather than distributions over inputs, the main technical challenge faced previously. By providing a quantum generalization of the argument of Jain and Nayak [IEEE TIT'14], we leverage this to obtain a lower bound on the space complexity of multi-pass, unidirectional quantum streaming algorithms for the DYCK(2) language.
Cite as

Ashwin Nayak and Dave Touchette. Augmented Index and Quantum Streaming Algorithms for DYCK(2). In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nayak_et_al:LIPIcs.CCC.2017.23,
  author =	{Nayak, Ashwin and Touchette, Dave},
  title =	{{Augmented Index and  Quantum Streaming Algorithms for DYCK(2)}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.23},
  URN =		{urn:nbn:de:0030-drops-75437},
  doi =		{10.4230/LIPIcs.CCC.2017.23},
  annote =	{Keywords: Quantum streaming algorithms, Space complexity, Quantum communication complexity, Quantum information cost, DYCK(2), Augmented Index}
}
  • Refine by Author
  • 2 Touchette, Dave
  • 1 Anshu, Anurag
  • 1 Arunachalam, Srinivasan
  • 1 Ben-David, Shalev
  • 1 Kundu, Srijita
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Communication complexity
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 Augmented Index
  • 1 Communication Complexity
  • 1 Communication complexity
  • 1 DYCK(2)
  • 1 Information Complexity
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2017
  • 2 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact