Search Results

Documents authored by Srinivasan, Akshaya

Found 2 Possible Name Variants:

Srinivasan, Akshaya

Document
DOI: 10.4230/LIPIcs.OPODIS.2019.26
Lower Bounds for Shoreline Searching With 2 or More Robots

Authors: Sumi Acharjee, Konstantinos Georgiou, Somnath Kundu, and Akshaya Srinivasan

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Searching for a line on the plane with n unit speed robots is a classic online problem that dates back to the 50’s, and for which competitive ratio upper bounds are known for every n ≥ 1, see [Baeza-Yates and Schott, 1995]. In this work we improve the best lower bound known for n=2 robots [Baeza-Yates and Schott, 1995] from 1.5993 to 3. Moreover we prove that the competitive ratio is at least √{3} for n=3 robots, and at least 1/cos ({π/n}) for n ≥ 4 robots. Our lower bounds match the best upper bounds known for n ≥ 4, hence resolving these cases. To the best of our knowledge, these are the first lower bounds proven for the cases n ≥ 3 of this several decades old problem.
Cite as

Sumi Acharjee, Konstantinos Georgiou, Somnath Kundu, and Akshaya Srinivasan. Lower Bounds for Shoreline Searching With 2 or More Robots. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{acharjee_et_al:LIPIcs.OPODIS.2019.26,
  author =	{Acharjee, Sumi and Georgiou, Konstantinos and Kundu, Somnath and Srinivasan, Akshaya},
  title =	{{Lower Bounds for Shoreline Searching With 2 or More Robots}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{26:1--26:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.26},
  URN =		{urn:nbn:de:0030-drops-118121},
  doi =		{10.4230/LIPIcs.OPODIS.2019.26},
  annote =	{Keywords: 2-Dimensional Search, Online Algorithms, Competitive Analysis, Lower Bounds}
}

Srinivasan, Akshayaram

Document
DOI: 10.4230/LIPIcs.ITCS.2022.26
Bounded Indistinguishability for Simple Sources

Authors: Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
A pair of sources X, Y over {0,1}ⁿ are k-indistinguishable if their projections to any k coordinates are identically distributed. Can some AC^0 function distinguish between two such sources when k is big, say k = n^{0.1}? Braverman’s theorem (Commun. ACM 2011) implies a negative answer when X is uniform, whereas Bogdanov et al. (Crypto 2016) observe that this is not the case in general. We initiate a systematic study of this question for natural classes of low-complexity sources, including ones that arise in cryptographic applications, obtaining positive results, negative results, and barriers. In particular: - There exist Ω(√n)-indistinguishable X, Y, samplable by degree-O(log n) polynomial maps (over F₂) and by poly(n)-size decision trees, that are Ω(1)-distinguishable by OR. - There exists a function f such that all f(d, ε)-indistinguishable X, Y that are samplable by degree-d polynomial maps are ε-indistinguishable by OR for all sufficiently large n. Moreover, f(1, ε) = ⌈log(1/ε)⌉ + 1 and f(2, ε) = O(log^{10}(1/ε)). - Extending (weaker versions of) the above negative results to AC^0 distinguishers would require settling a conjecture of Servedio and Viola (ECCC 2012). Concretely, if every pair of n^{0.9}-indistinguishable X, Y that are samplable by linear maps is ε-indistinguishable by AC^0 circuits, then the binary inner product function can have at most an ε-correlation with AC^0 ◦ ⊕ circuits. Finally, we motivate the question and our results by presenting applications of positive results to low-complexity secret sharing and applications of negative results to leakage-resilient cryptography.
Cite as

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. Bounded Indistinguishability for Simple Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2022.26,
  author =	{Bogdanov, Andrej and Dinesh, Krishnamoorthy and Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Srinivasan, Akshayaram},
  title =	{{Bounded Indistinguishability for Simple Sources}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.26},
  URN =		{urn:nbn:de:0030-drops-156223},
  doi =		{10.4230/LIPIcs.ITCS.2022.26},
  annote =	{Keywords: Pseudorandomness, bounded indistinguishability, complexity of sampling, constant-depth circuits, secret sharing, leakage-resilient cryptography}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.71
Separating Two-Round Secure Computation From Oblivious Transfer

Authors: Benny Applebaum, Zvika Brakerski, Sanjam Garg, Yuval Ishai, and Akshayaram Srinivasan

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We consider the question of minimizing the round complexity of protocols for secure multiparty computation (MPC) with security against an arbitrary number of semi-honest parties. Very recently, Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) constructed such 2-round MPC protocols from minimal assumptions. This was done by showing a round preserving reduction to the task of secure 2-party computation of the oblivious transfer functionality (OT). These constructions made a novel non-black-box use of the underlying OT protocol. The question remained whether this can be done by only making black-box use of 2-round OT. This is of theoretical and potentially also practical value as black-box use of primitives tends to lead to more efficient constructions. Our main result proves that such a black-box construction is impossible, namely that non-black-box use of OT is necessary. As a corollary, a similar separation holds when starting with any 2-party functionality other than OT. As a secondary contribution, we prove several additional results that further clarify the landscape of black-box MPC with minimal interaction. In particular, we complement the separation from 2-party functionalities by presenting a complete 4-party functionality, give evidence for the difficulty of ruling out a complete 3-party functionality and for the difficulty of ruling out black-box constructions of 3-round MPC from 2-round OT, and separate a relaxed "non-compact" variant of 2-party homomorphic secret sharing from 2-round OT.
Cite as

Benny Applebaum, Zvika Brakerski, Sanjam Garg, Yuval Ishai, and Akshayaram Srinivasan. Separating Two-Round Secure Computation From Oblivious Transfer. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 71:1-71:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{applebaum_et_al:LIPIcs.ITCS.2020.71,
  author =	{Applebaum, Benny and Brakerski, Zvika and Garg, Sanjam and Ishai, Yuval and Srinivasan, Akshayaram},
  title =	{{Separating Two-Round Secure Computation From Oblivious Transfer}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{71:1--71:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.71},
  URN =		{urn:nbn:de:0030-drops-117560},
  doi =		{10.4230/LIPIcs.ITCS.2020.71},
  annote =	{Keywords: Oracle Separation, Oblivious Transfer, Secure Multiparty Computation}
}
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 About DROPS Imprint Privacy Contact