6 Search Results for "Iyer, Siddharth"

Document
DOI: 10.4230/LIPIcs.CCC.2025.16
Direct Sums for Parity Decision Trees

Authors: Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, and Weiqiang Yuan

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Direct sum theorems state that the cost of solving k instances of a problem is at least Ω(k) times the cost of solving a single instance. We prove the first such results in the randomised parity decision tree model. We show that a direct sum theorem holds whenever (1) the lower bound for parity decision trees is proved using the discrepancy method; or (2) the lower bound is proved relative to a product distribution.
Cite as

Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, and Weiqiang Yuan. Direct Sums for Parity Decision Trees. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 16:1-16:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{besselman_et_al:LIPIcs.CCC.2025.16,
  author =	{Besselman, Tyler and G\"{o}\"{o}s, Mika and Guo, Siyao and Maystre, Gilbert and Yuan, Weiqiang},
  title =	{{Direct Sums for Parity Decision Trees}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{16:1--16:38},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.16},
  URN =		{urn:nbn:de:0030-drops-237105},
  doi =		{10.4230/LIPIcs.CCC.2025.16},
  annote =	{Keywords: direct sum, parity decision trees, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.59
Error Correction for Message Streams

Authors: Meghal Gupta and Rachel Yun Zhang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In the setting of error correcting codes, Alice wants to send a message x ∈ {0,1}ⁿ to Bob via an encoding enc(x) that is resilient to error. In this work, we investigate the scenario where Bob is a low space decoder. More precisely, he receives Alice’s encoding enc(x) bit-by-bit and desires to compute some function f(x) in low space. A generic error-correcting code does not accomplish this because decoding is a very global process and requires at least linear space. Locally decodable codes partially solve this problem as they allow Bob to learn a given bit of x in low space, but not compute a generic function f. Our main result is an encoding and decoding procedure where Bob is still able to compute any such function f in low space when a constant fraction of the stream is corrupted. More precisely, we describe an encoding function enc(x) of length poly(n) so that for any decoder (streaming algorithm) A that on input x computes f(x) in space s, there is an explicit decoder B that computes f(x) in space s ⋅ polylog(n) as long as there were not more than 1/4 - ε fraction of (adversarial) errors in the input stream enc(x).
Cite as

Meghal Gupta and Rachel Yun Zhang. Error Correction for Message Streams. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ITCS.2025.59,
  author =	{Gupta, Meghal and Zhang, Rachel Yun},
  title =	{{Error Correction for Message Streams}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.59},
  URN =		{urn:nbn:de:0030-drops-226875},
  doi =		{10.4230/LIPIcs.ITCS.2025.59},
  annote =	{Keywords: error-correcting codes, streaming algorithms, space-efficient algorithms}
}
Document
Survey
DOI: 10.4230/TGDK.1.1.4
Knowledge Graph Embeddings: Open Challenges and Opportunities

Authors: Russa Biswas, Lucie-Aimée Kaffee, Michael Cochez, Stefania Dumbrava, Theis E. Jendal, Matteo Lissandrini, Vanessa Lopez, Eneldo Loza Mencía, Heiko Paulheim, Harald Sack, Edlira Kalemi Vakaj, and Gerard de Melo

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
While Knowledge Graphs (KGs) have long been used as valuable sources of structured knowledge, in recent years, KG embeddings have become a popular way of deriving numeric vector representations from them, for instance, to support knowledge graph completion and similarity search. This study surveys advances as well as open challenges and opportunities in this area. For instance, the most prominent embedding models focus primarily on structural information. However, there has been notable progress in incorporating further aspects, such as semantics, multi-modal, temporal, and multilingual features. Most embedding techniques are assessed using human-curated benchmark datasets for the task of link prediction, neglecting other important real-world KG applications. Many approaches assume a static knowledge graph and are unable to account for dynamic changes. Additionally, KG embeddings may encode data biases and lack interpretability. Overall, this study provides an overview of promising research avenues to learn improved KG embeddings that can address a more diverse range of use cases.
Cite as

Russa Biswas, Lucie-Aimée Kaffee, Michael Cochez, Stefania Dumbrava, Theis E. Jendal, Matteo Lissandrini, Vanessa Lopez, Eneldo Loza Mencía, Heiko Paulheim, Harald Sack, Edlira Kalemi Vakaj, and Gerard de Melo. Knowledge Graph Embeddings: Open Challenges and Opportunities. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 4:1-4:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{biswas_et_al:TGDK.1.1.4,
  author =	{Biswas, Russa and Kaffee, Lucie-Aim\'{e}e and Cochez, Michael and Dumbrava, Stefania and Jendal, Theis E. and Lissandrini, Matteo and Lopez, Vanessa and Menc{\'\i}a, Eneldo Loza and Paulheim, Heiko and Sack, Harald and Vakaj, Edlira Kalemi and de Melo, Gerard},
  title =	{{Knowledge Graph Embeddings: Open Challenges and Opportunities}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{4:1--4:32},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.4},
  URN =		{urn:nbn:de:0030-drops-194783},
  doi =		{10.4230/TGDK.1.1.4},
  annote =	{Keywords: Knowledge Graphs, KG embeddings, Link prediction, KG applications}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.83
Searching for Regularity in Bounded Functions

Authors: Siddharth Iyer and Michael Whitmeyer

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Given a function f on F₂ⁿ, we study the following problem. What is the largest affine subspace 𝒰 such that when restricted to 𝒰, all the non-trivial Fourier coefficients of f are very small? For the natural class of bounded Fourier degree d functions f: F₂ⁿ → [-1,1], we show that there exists an affine subspace of dimension at least Ω(n^{1/d!} k^{-2}), wherein all of f’s nontrivial Fourier coefficients become smaller than 2^{-k}. To complement this result, we show the existence of degree d functions with coefficients larger than 2^{-d log n} when restricted to any affine subspace of dimension larger than Ω(d n^{1/(d-1)}). In addition, we give explicit examples of functions with analogous but weaker properties. Along the way, we provide multiple characterizations of the Fourier coefficients of functions restricted to subspaces of F₂ⁿ that may be useful in other contexts. Finally, we highlight applications and connections of our results to parity kill number and affine dispersers.
Cite as

Siddharth Iyer and Michael Whitmeyer. Searching for Regularity in Bounded Functions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{iyer_et_al:LIPIcs.ICALP.2023.83,
  author =	{Iyer, Siddharth and Whitmeyer, Michael},
  title =	{{Searching for Regularity in Bounded Functions}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{83:1--83:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.83},
  URN =		{urn:nbn:de:0030-drops-181351},
  doi =		{10.4230/LIPIcs.ICALP.2023.83},
  annote =	{Keywords: regularity, bounded function, Boolean function, Fourier analysis}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.13
Interactive Coding Resilient to an Unknown Number of Erasures

Authors: Ran Gelles and Siddharth Iyer

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

Abstract
We consider distributed computations between two parties carried out over a noisy channel that may erase messages. Following a noise model proposed by Dani et al. (2018), the noise level observed by the parties during the computation in our setting is arbitrary and a priori unknown to the parties. We develop interactive coding schemes that adapt to the actual level of noise and correctly execute any two-party computation. Namely, in case the channel erases T transmissions, the coding scheme will take N+2T transmissions using an alphabet of size 4 (alternatively, using 2N+4T transmissions over a binary channel) to correctly simulate any binary protocol that takes N transmissions assuming a noiseless channel. We can further reduce the communication to N+T by relaxing the communication model and allowing parties to remain silent rather than forcing them to communicate in every round of the coding scheme. Our coding schemes are efficient, deterministic, have linear overhead both in their communication and round complexity, and succeed (with probability 1) regardless of the number of erasures T.
Cite as

Ran Gelles and Siddharth Iyer. Interactive Coding Resilient to an Unknown Number of Erasures. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gelles_et_al:LIPIcs.OPODIS.2019.13,
  author =	{Gelles, Ran and Iyer, Siddharth},
  title =	{{Interactive Coding Resilient to an Unknown Number of Erasures}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{13:1--13:16},
  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.13},
  URN =		{urn:nbn:de:0030-drops-117999},
  doi =		{10.4230/LIPIcs.OPODIS.2019.13},
  annote =	{Keywords: Interactive coding, erasure channels, distributed computation with noise, unbounded noise}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.19
Shortest k-Disjoint Paths via Determinants

Authors: Samir Datta, Siddharth Iyer, Raghav Kulkarni, and Anish Mukherjee

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
The well-known k-disjoint path problem (k-DPP) asks for pairwise vertex-disjoint paths between k specified pairs of vertices (s_i, t_i) in a given graph, if they exist. The decision version of the shortest k-DPP asks for the length of the shortest (in terms of total length) such paths. Similarly, the search and counting versions ask for one such and the number of such shortest set of paths, respectively. We restrict attention to the shortest k-DPP instances on undirected planar graphs where all sources and sinks lie on a single face or on a pair of faces. We provide efficient sequential and parallel algorithms for the search versions of the problem answering one of the main open questions raised by Colin de Verdière and Schrijver [Éric Colin de Verdière and Alexander Schrijver, 2011] for the general one-face problem. We do so by providing a randomised NC^2 algorithm along with an O(n^{omega/2}) time randomised sequential algorithm, for any fixed k. We also obtain deterministic algorithms with similar resource bounds for the counting and search versions. In contrast, previously, only the sequential complexity of decision and search versions of the "well-ordered" case has been studied. For the one-face case, sequential versions of our routines have better running times for constantly many terminals. The algorithms are based on a bijection between a shortest k-tuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to non-trivially modify established techniques relating counting cycle covers to the determinant. We further need to do a controlled inclusion-exclusion to produce a polynomial sum of determinants such that all "bad" cycle covers cancel out in the sum allowing us to count "pure" cycle covers.
Cite as

Samir Datta, Siddharth Iyer, Raghav Kulkarni, and Anish Mukherjee. Shortest k-Disjoint Paths via Determinants. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.FSTTCS.2018.19,
  author =	{Datta, Samir and Iyer, Siddharth and Kulkarni, Raghav and Mukherjee, Anish},
  title =	{{Shortest k-Disjoint Paths via Determinants}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.19},
  URN =		{urn:nbn:de:0030-drops-99183},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.19},
  annote =	{Keywords: disjoint paths, planar graph, parallel algorithm, cycle cover, determinant, inclusion-exclusion}
}
  • Refine by Type
  • 6 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 2 2023
  • 1 2020
  • 1 2018

  • Refine by Author
  • 3 Iyer, Siddharth
  • 1 Besselman, Tyler
  • 1 Biswas, Russa
  • 1 Cochez, Michael
  • 1 Datta, Samir
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 2 Mathematics of computing → Coding theory
  • 1 Computing methodologies → Distributed algorithms
  • 1 Computing methodologies → Machine learning approaches
  • 1 Computing methodologies → Semantic networks
  • 1 Mathematics of computing
  • Show More...

  • Refine by Keyword
  • 1 Boolean function
  • 1 Fourier analysis
  • 1 Interactive coding
  • 1 KG applications
  • 1 KG embeddings
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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