7 Search Results for "Kundu, Srijita"

Document
DOI: 10.4230/LIPIcs.STACS.2022.49
One-Way Communication Complexity and Non-Adaptive Decision Trees

Authors: Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. More generally, we show the following when the gadget is Inner Product on 2b input bits for all b ≥ 2, denoted IP. - If f is a total Boolean function that depends on all of its n input bits, then the bounded-error one-way quantum communication complexity of f∘IP equals Ω(n(b-1)). - If f is a partial Boolean function, then the deterministic one-way communication complexity of f∘IP is at least Ω(b ⋅ 𝖣_{dt}^ → (f)), where 𝖣_{dt}^ → (f) denotes non-adaptive decision tree complexity of f. To prove our quantum lower bound, we first show a lower bound on the VC-dimension of f∘IP. We then appeal to a result of Klauck [STOC'00], which immediately yields our quantum lower bound. Our deterministic lower bound relies on a combinatorial result independently proven by Ahlswede and Khachatrian [Adv. Appl. Math.'98], and Frankl and Tokushige [Comb.'99]. It is known due to a result of Montanaro and Osborne [arXiv'09] that the deterministic one-way communication complexity of f∘XOR equals the non-adaptive parity decision tree complexity of f. In contrast, we show the following when the inner gadget is the AND function on 2 input bits. - There exists a function for which even the quantum non-adaptive AND decision tree complexity of f is exponentially large in the deterministic one-way communication complexity of f∘AND. - However, for symmetric functions f, the non-adaptive AND decision tree complexity of f is at most quadratic in the (even two-way) communication complexity of f∘AND. In view of the first bullet, a lower bound on non-adaptive AND decision tree complexity of f does not lift to a lower bound on one-way communication complexity of f∘AND. The proof of the first bullet above uses the well-studied Odd-Max-Bit function. For the second bullet, we first observe a connection between the one-way communication complexity of f and the Möbius sparsity of f, and then give a lower bound on the Möbius sparsity of symmetric functions. An upper bound on the non-adaptive AND decision tree complexity of symmetric functions follows implicitly from prior work on combinatorial group testing; for the sake of completeness, we include a proof of this result. It is well known that the rank of the communication matrix of a function F is an upper bound on its deterministic one-way communication complexity. This bound is known to be tight for some F. However, in our final result we show that this is not the case when F = f∘AND. More precisely we show that for all f, the deterministic one-way communication complexity of F = f∘AND is at most (rank(M_{F}))(1 - Ω(1)), where M_{F} denotes the communication matrix of F.
Cite as

Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif. One-Way Communication Complexity and Non-Adaptive Decision Trees. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.STACS.2022.49,
  author =	{Mande, Nikhil S. and Sanyal, Swagato and Sherif, Suhail},
  title =	{{One-Way Communication Complexity and Non-Adaptive Decision Trees}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{49:1--49:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.49},
  URN =		{urn:nbn:de:0030-drops-158598},
  doi =		{10.4230/LIPIcs.STACS.2022.49},
  annote =	{Keywords: Decision trees, communication complexity, composed Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.27
A Direct Product Theorem for One-Way Quantum Communication

Authors: Rahul Jain and Srijita Kundu

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

Abstract
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation f ⊆ 𝒳×𝒴×𝒵. For any 0 < ε < δ < 1/2 and any k≥1, we show that Q¹_{1-(1-ε)^{Ω(k/log|𝒵|)}}(f^k) = Ω(k⋅Q¹_{δ}(f)), where Q¹_{ε}(f) represents the one-way entanglement-assisted quantum communication complexity of f with worst-case error ε and f^k denotes k parallel instances of f. As far as we are aware, this is the first direct product theorem for the quantum communication complexity of a general relation - direct sum theorems were previously known for one-way quantum protocols for general relations, while direct product theorems were only known for special cases. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlényi and Yao [Rahul Jain et al., 2014], and under anchored distributions due to Bavarian, Vidick and Yuen [Bavarian et al., 2017], as well as message compression for quantum protocols due to Jain, Radhakrishnan and Sen [Rahul Jain et al., 2005]. In particular, we show that a direct product theorem holds for the distributional one-way quantum communication complexity of f under any distribution q on 𝒳×𝒴 that is anchored on one side, i.e., there exists a y^* such that q(y^*) is constant and q(x|y^*) = q(x) for all x. This allows us to show a direct product theorem for general distributions, since for any relation f and any distribution p on its inputs, we can define a modified relation f̃ which has an anchored distribution q close to p, such that a protocol that fails with probability at most ε for f̃ under q can be used to give a protocol that fails with probability at most ε + ζ for f under p. Our techniques also work for entangled non-local games which have input distributions anchored on any one side, i.e., either there exists a y^* as previously specified, or there exists an x^* such that q(x^*) is constant and q(y|x^*) = q(y) for all y. In particular, we show that for any game G = (q, 𝒳×𝒴, 𝒜×ℬ, 𝖵) where q is a distribution on 𝒳×𝒴 anchored on any one side with constant anchoring probability, then ω^*(G^k) = (1 - (1-ω^*(G))⁵) ^{Ω(k/(log(|𝒜|⋅|ℬ|)))} where ω^*(G) represents the entangled value of the game G. This is a generalization of the result of [Bavarian et al., 2017], who proved a parallel repetition theorem for games anchored on both sides, i.e., where both a special x^* and a special y^* exist, and potentially a simplification of their proof.
Cite as

Rahul Jain and Srijita Kundu. A Direct Product Theorem for One-Way Quantum Communication. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 27:1-27:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.CCC.2021.27,
  author =	{Jain, Rahul and Kundu, Srijita},
  title =	{{A Direct Product Theorem for One-Way Quantum Communication}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{27:1--27:28},
  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.27},
  URN =		{urn:nbn:de:0030-drops-143017},
  doi =		{10.4230/LIPIcs.CCC.2021.27},
  annote =	{Keywords: Direct product theorem, parallel repetition theorem, quantum communication, one-way protocols, communication complexity}
}
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.TQC.2020.12
A Device-Independent Protocol for XOR Oblivious Transfer

Authors: Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract
Oblivious transfer is a cryptographic primitive where Alice has two bits and Bob wishes to learn some function of them. Ideally, Alice should not learn Bob’s desired function choice and Bob should not learn any more than logically implied by the function value. While decent quantum protocols for this task are known, many quickly become insecure if an adversary were to control the quantum devices used in the implementation of the protocol. Here we present how some existing protocols fail in this device-independent framework, and give a fully-device independent quantum protocol for XOR oblivious transfer which is provably more secure than any classical protocol.
Cite as

Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan. A Device-Independent Protocol for XOR Oblivious Transfer. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kundu_et_al:LIPIcs.TQC.2020.12,
  author =	{Kundu, Srijita and Sikora, Jamie and Tan, Ernest Y.-Z.},
  title =	{{A Device-Independent Protocol for XOR Oblivious Transfer}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.12},
  URN =		{urn:nbn:de:0030-drops-127579},
  doi =		{10.4230/LIPIcs.TQC.2020.12},
  annote =	{Keywords: Quantum cryptography, device independence, oblivious transfer, semidefinite programming, security analysis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.64
A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Authors: Dmitry Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.
Cite as

Dmitry Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal. A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 64:1-64:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gavinsky_et_al:LIPIcs.ICALP.2019.64,
  author =	{Gavinsky, Dmitry and Lee, Troy and Santha, Miklos and Sanyal, Swagato},
  title =	{{A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{64:1--64:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.64},
  URN =		{urn:nbn:de:0030-drops-106407},
  doi =		{10.4230/LIPIcs.ICALP.2019.64},
  annote =	{Keywords: query complexity, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.10
A Composition Theorem for Randomized Query Complexity

Authors: Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.
Cite as

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal. A Composition Theorem for Randomized Query Complexity. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{anshu_et_al:LIPIcs.FSTTCS.2017.10,
  author =	{Anshu, Anurag and Gavinsky, Dmitry and Jain, Rahul and Kundu, Srijita and Lee, Troy and Mukhopadhyay, Priyanka and Santha, Miklos and Sanyal, Swagato},
  title =	{{A Composition Theorem for Randomized Query Complexity}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.10},
  URN =		{urn:nbn:de:0030-drops-83967},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.10},
  annote =	{Keywords: Query algorithms and complexity, Decision trees, Composition theorem, XOR lemma, Hardness amplification}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.76
Optimal Bounds for Parity-Oblivious Random Access Codes with Applications

Authors: André Chailloux, Iordanis Kerenidis, Srijita Kundu, and Jamie Sikora

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Abstract
Random Access Codes is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an n-bit string x, and wishes to encode x into a quantum state rho_x, such that Bob, when receiving the state rho_x, can choose any bit i in [n] and recover the input bit x_i with high probability. Here we study a variant called parity-oblivious random acres codes, where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input, apart form the single bits x_i. We provide the optimal quantum parity-oblivious random access codes and show that they are asymptotically better than the optimal classical ones. For this, we relate such encodings to a non-local game and provide tight bounds for the success probability of the non-local game via semi-definite programming. Our results provide a large non-contextuality inequality violation and resolve the main open question in [Spekkens et al., Phys. Review Letters, 2009].
Cite as

André Chailloux, Iordanis Kerenidis, Srijita Kundu, and Jamie Sikora. Optimal Bounds for Parity-Oblivious Random Access Codes with Applications. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 76-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chailloux_et_al:LIPIcs.TQC.2014.76,
  author =	{Chailloux, Andr\'{e} and Kerenidis, Iordanis and Kundu, Srijita and Sikora, Jamie},
  title =	{{Optimal Bounds for Parity-Oblivious Random Access Codes with Applications}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{76--87},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.76},
  URN =		{urn:nbn:de:0030-drops-48084},
  doi =		{10.4230/LIPIcs.TQC.2014.76},
  annote =	{Keywords: quantum information theory, contextuality, semidefinite programming}
}
  • Refine by Author
  • 5 Kundu, Srijita
  • 3 Sanyal, Swagato
  • 2 Anshu, Anurag
  • 2 Gavinsky, Dmitry
  • 2 Jain, Rahul
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Communication complexity
  • 2 Theory of computation → Oracles and decision trees
  • 2 Theory of computation → Quantum complexity theory
  • 1 Security and privacy → Cryptography
  • 1 Theory of computation → Cryptographic primitives

  • Refine by Keyword
  • 3 communication complexity
  • 2 Decision trees
  • 2 query complexity
  • 2 semidefinite programming
  • 1 Composition theorem
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2021
  • 1 2014
  • 1 2018
  • 1 2019
  • 1 2020
  • Show More...

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