14 Search Results for "Dark, Jacques"

Document
DOI: 10.4230/LIPIcs.STACS.2026.4
Unit Interval Selection in Random Order Streams

Authors: Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson, Christian Konrad, and Kheeran K. Naidu

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We consider the Unit Interval Selection problem in the one-pass random order streaming model. In this setting, an algorithm is presented with a sequence of n unit-length intervals on the line that arrive in uniform random order, one at a time, and the objective is to output (an approximation of) a largest set of disjoint intervals using space linear in the size of an optimal solution. Previous work only considered adversarially ordered streams and established that, within these space constraints, a (2/3)-approximation can be achieved in such streams, and this is best possible, in that going beyond such an approximation factor requires space Ω(n) [Emek et al., TALG'16]. In this work, we show that an improved expected approximation factor can be achieved if the input stream is in uniform random order, where the expectation is taken over the stream order. More specifically, we give a one-pass streaming algorithm with expected approximation factor 0.7401 that uses space O(|OPT|), where OPT denotes an optimal solution. We also show that random order algorithms with expected approximation factor above 8/9 require space Ω(n), and algorithms that compute a better than 2/3-approximation with probability above 2/3 also require Ω(n) space. On a technical level, we design an algorithm for the restricted domain [0, Δ), for some constant Δ, and use standard techniques to obtain an algorithm for unrestricted domains. For the restricted domain [0, Δ), we run O(Δ) recursive instances of our algorithm, with each instance targeting the situation where a specific interval of an optimal solution arrives first. We establish the interesting property of our algorithm that it performs worst when the input stream consists solely of a set of independent intervals. It then remains to analyse the algorithm on these simple instances. Our lower bound is proved via communication complexity arguments, similar in spirit to the robust communication lower bounds established by [Chakrabarti et al., Theory Comput. 2016].
Cite as

Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson, Christian Konrad, and Kheeran K. Naidu. Unit Interval Selection in Random Order Streams. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alexandru_et_al:LIPIcs.STACS.2026.4,
  author =	{Alexandru, Cezar-Mihail and Diddapur, Adithya and Halld\'{o}rsson, Magn\'{u}s M. and Konrad, Christian and Naidu, Kheeran K.},
  title =	{{Unit Interval Selection in Random Order Streams}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.4},
  URN =		{urn:nbn:de:0030-drops-254933},
  doi =		{10.4230/LIPIcs.STACS.2026.4},
  annote =	{Keywords: Random order streaming algorithms, unit interval selection}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.22
Constructing Long Paths in Graph Streams

Authors: Christian Konrad and Chhaya Trehan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In the graph stream model of computation, an algorithm processes the edges of an n-vertex input graph in one or more sequential passes while using a memory that is sublinear in the input size. The streaming model poses significant challenges for algorithmically constructing long paths. Many known algorithms that are tasked with extending an existing path as a subroutine require an entire pass over the input to add a single additional edge. This raises a fundamental question: Are multiple passes inherently necessary to construct paths of non-trivial lengths, or can a single pass suffice? To address this question, we systematically study the Longest Path problem in the one-pass streaming model. In this problem, given a desired approximation factor α, the objective is to compute a path of length at least lp(G)/α, where lp(G) is the length of a longest path in the input graph G. We study the problem in the insertion-only and the insertion-deletion streaming models, and we give algorithms as well as space lower bounds for both undirected and directed graphs. Our results are: 1) We show that for undirected graphs, in both the insertion-only and the insertion-deletion models, there are semi-streaming algorithms, i.e., algorithms that use space O(n poly log n), that compute a path of length at least d/3 with high probability, where d is the average degree of the input graph. These algorithms can also yield an α-approximation to Longest Path using space Õ(n²/α). 2) Next, we show that such a result cannot be achieved for directed graphs, even in the insertion-only model. We show that computing a (n^{1-o(1)})-approximation to Longest Path in directed graphs in the insertion-only model requires space Ω(n²). This result is in line with recent results that demonstrate that processing directed graphs is often significantly harder than undirected graphs in the streaming model. 3) We further complement our results with two additional lower bounds. First, we show that semi-streaming space is insufficient for small constant factor approximations to Longest Path for undirected graphs in the insertion-only model. Last, in undirected graphs in the insertion-deletion model, we show that computing an α-approximation requires space Ω(n²/α³).
Cite as

Christian Konrad and Chhaya Trehan. Constructing Long Paths in Graph Streams. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.ESA.2025.22,
  author =	{Konrad, Christian and Trehan, Chhaya},
  title =	{{Constructing Long Paths in Graph Streams}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.22},
  URN =		{urn:nbn:de:0030-drops-244902},
  doi =		{10.4230/LIPIcs.ESA.2025.22},
  annote =	{Keywords: Longest Path Problem, Streaming Algorithms, One-way Two-party Communication Complexity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.40
Sublinear Space Graph Algorithms in the Continual Release Model

Authors: Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, and Felix Zhou

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of edge updates where new private solutions are released after each update. Thus far, previously known edge-differentially private algorithms for most graph problems including densest subgraph and matchings in the continual release setting only output real-value estimates (not vertex subset solutions) and do not use sublinear space. Instead, they rely on computing exact graph statistics on the input [Hendrik Fichtenberger et al., 2021; Shuang Song et al., 2018]. In this paper, we leverage sparsification to address the above shortcomings for edge-insertion streams. Our edge-differentially private algorithms use sublinear space with respect to the number of edges in the graph while some also achieve sublinear space in the number of vertices in the graph. In addition, for the densest subgraph problem, we also output edge-differentially private vertex subset solutions; no previous graph algorithms in the continual release model output such subsets. We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms literature to achieve new results in the sublinear space, continual release setting. This includes algorithms for densest subgraph, maximum matching, as well as the first continual release k-core decomposition algorithm. We also develop a novel sparse level data structure for k-core decomposition that may be of independent interest. To complement our insertion-only algorithms, we conclude with polynomial additive error lower bounds for edge-privacy in the fully dynamic setting, where only logarithmic lower bounds were previously known.
Cite as

Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, and Felix Zhou. Sublinear Space Graph Algorithms in the Continual Release Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 40:1-40:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{epasto_et_al:LIPIcs.APPROX/RANDOM.2025.40,
  author =	{Epasto, Alessandro and Liu, Quanquan C. and Mukherjee, Tamalika and Zhou, Felix},
  title =	{{Sublinear Space Graph Algorithms in the Continual Release Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{40:1--40:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.40},
  URN =		{urn:nbn:de:0030-drops-244064},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.40},
  annote =	{Keywords: Differential Privacy, Continual Release, Densest Subgraph, k-Core Decomposition, Maximum Matching}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.33
A Min-Entropy Approach to Multi-Party Communication Lower Bounds

Authors: Mi-Ying (Miryam) Huang, Xinyu Mao, Shuo Wang, Guangxu Yang, and Jiapeng Zhang

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

Abstract
Information complexity is one of the most powerful techniques to prove information-theoretical lower bounds, in which Shannon entropy plays a central role. Though Shannon entropy has some convenient properties, such as the chain rule, it still has inherent limitations. One of the most notable barriers is the square-root loss, which appears in the square-root gap between entropy gaps and statistical distances, e.g., Pinsker’s inequality. To bypass this barrier, we introduce a new method based on min-entropy analysis. Building on this new method, we prove the following results. - An Ω(N^{∑_i α_i - max_i {α_i}}/k) randomized communication lower bound of the k-party set-intersection problem where the i-th party holds a random set of size ≈ N^{1-α_i}. - A tight Ω(n/k) randomized lower bound of the k-party Tree Pointer Jumping problems, improving an Ω(n/k²) lower bound by Chakrabarti, Cormode, and McGregor (STOC 08). - An Ω(n/k+√n) lower bound of the Chained Index problem, improving an Ω(n/k²) lower bound by Cormode, Dark, and Konrad (ICALP 19). Since these problems served as hard problems for numerous applications in streaming lower bounds and cryptography, our new lower bounds directly improve these streaming lower bounds and cryptography lower bounds. On the technical side, min-entropy does not have nice properties such as the chain rule. To address this issue, we enhance the structure-vs-pseudorandomness decomposition used by Göös, Pitassi, and Watson (FOCS 17) and Yang and Zhang (STOC 24); both papers used this decomposition to prove communication lower bounds. In this paper, we give a new breath to this method in the multi-party setting, presenting a new toolkit for proving multi-party communication lower bounds.
Cite as

Mi-Ying (Miryam) Huang, Xinyu Mao, Shuo Wang, Guangxu Yang, and Jiapeng Zhang. A Min-Entropy Approach to Multi-Party Communication Lower Bounds. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 33:1-33:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.CCC.2025.33,
  author =	{Huang, Mi-Ying (Miryam) and Mao, Xinyu and Wang, Shuo and Yang, Guangxu and Zhang, Jiapeng},
  title =	{{A Min-Entropy Approach to Multi-Party Communication Lower Bounds}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{33:1--33:29},
  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.33},
  URN =		{urn:nbn:de:0030-drops-237273},
  doi =		{10.4230/LIPIcs.CCC.2025.33},
  annote =	{Keywords: communication complexity, lifting theorems, set intersection, chained index}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.106
Streaming Maximal Matching with Bounded Deletions

Authors: Sanjeev Khanna, Christian Konrad, and Jacques Dark

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We initiate the study of the Maximal Matching problem in bounded-deletion graph streams. In this setting, a graph G is revealed as an arbitrary sequence of edge insertions and deletions, where the number of insertions is unrestricted but the number of deletions is guaranteed to be at most K, for some given parameter K. The single-pass streaming space complexity of this problem is known to be Θ(n²) when K is unrestricted, where n is the number of vertices of the input graph. In this work, we present new randomized and deterministic algorithms and matching lower bound results that together give a tight understanding (up to poly-log factors) of how the space complexity of Maximal Matching evolves as a function of the parameter K: The randomized space complexity of this problem is Θ̃(n ⋅ √K), while the deterministic space complexity is Θ̃(n ⋅ K). We further show that if we relax the maximal matching requirement to an α-approximation to Maximum Matching, for any constant α > 2, then the space complexity for both, deterministic and randomized algorithms, strikingly changes to Θ̃(n + K). A key conceptual contribution of our work that underlies all our algorithmic results is the introduction of the hierarchical maximal matching data structure, which computes a hierarchy of L maximal matchings on the substream of edge insertions, for an integer L. This deterministic data structure allows recovering a Maximal Matching even in the presence of up to L-1 edge deletions, which immediately yields an optimal deterministic algorithm with space Õ(n ⋅ K). To reduce the space to Õ(n ⋅ √K), we compute only √K levels of our hierarchical matching data structure and utilize a randomized linear sketch, i.e., our matching repair data structure, to repair any damage due to edge deletions. Using our repair data structure, we show that the level that is least affected by deletions can be repaired back to be globally maximal. The repair data structure is computed independently of the hierarchical maximal matching data structure and stores information for vertices at different scales with a gradually smaller set of vertices storing more and more information about their incident edges. The repair process then makes progress either by rematching a vertex to a previously unmatched vertex, or by strategically matching it to another matched vertex whose current mate is in a better position to find a new mate in that we have stored more information about its incident edges. Our lower bound result for randomized algorithms is obtained by establishing a lower bound for a generalization of the well-known Augmented-Index problem in the one-way two-party communication setting that we refer to as Embedded-Augmented-Index, and then showing that an instance of Embedded-Augmented-Index reduces to computing a maximal matching in bounded-deletion streams. To obtain our lower bound for deterministic algorithms, we utilize a compression argument to show that a deterministic algorithm with space o(n ⋅ K) would yield a scheme to compress a suitable class of graphs below the information-theoretic threshold.
Cite as

Sanjeev Khanna, Christian Konrad, and Jacques Dark. Streaming Maximal Matching with Bounded Deletions. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 106:1-106:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.ICALP.2025.106,
  author =	{Khanna, Sanjeev and Konrad, Christian and Dark, Jacques},
  title =	{{Streaming Maximal Matching with Bounded Deletions}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{106:1--106:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.106},
  URN =		{urn:nbn:de:0030-drops-234834},
  doi =		{10.4230/LIPIcs.ICALP.2025.106},
  annote =	{Keywords: Streaming Algorithms, Maximal Matching, Maximum Matching, Bounded-Deletion Streams}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.135
Deterministic Independent Sets in the Semi-Streaming Model

Authors: Daniel Ye

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We consider the independent set problem in the semi-streaming model. For any input graph G = (V, E) with n vertices, an independent set is a set of vertices with no edges between any two elements. In the semi-streaming model, G is presented as a stream of edges and any algorithm must use Õ(n) bits of memory to output a large independent set at the end of the stream. Prior work has designed various semi-streaming algorithms for finding independent sets. Due to the hardness of finding maximum and maximal independent sets in the semi-streaming model, the focus has primarily been on finding independent sets in terms of certain parameters, such as the maximum degree Δ. In particular, there is a simple randomized algorithm that obtains independent sets of size n/(Δ+1) in expectation, which can also be achieved with high probability using more complicated algorithms. For deterministic algorithms, the best bounds are significantly weaker. The best we know is a straightforward algorithm that finds an Ω̃(n/(Δ²)) size independent set. We show that this straightforward algorithm is nearly optimal by proving that any deterministic semi-streaming algorithm can only output an Õ(n/(Δ²)) size independent set. Our result proves a strong separation between the power of deterministic and randomized semi-streaming algorithms for the independent set problem.
Cite as

Daniel Ye. Deterministic Independent Sets in the Semi-Streaming Model. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 135:1-135:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ye:LIPIcs.ICALP.2025.135,
  author =	{Ye, Daniel},
  title =	{{Deterministic Independent Sets in the Semi-Streaming Model}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{135:1--135:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.135},
  URN =		{urn:nbn:de:0030-drops-235129},
  doi =		{10.4230/LIPIcs.ICALP.2025.135},
  annote =	{Keywords: Sublinear Algorithms, Derandomization, Semi-Streaming Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.66
One-Way Communication Complexity of Minimum Vertex Cover in General Graphs

Authors: Mahsa Derakhshan, Andisheh Ghasemi, and Rajmohan Rajaraman

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the communication complexity of the Minimum Vertex Cover (MVC) problem on general graphs within the k-party one-way communication model. Edges of an arbitrary n-vertex graph are distributed among k parties. The objective is for the parties to collectively find a small vertex cover of the graph while adhering to a communication protocol where each party sequentially sends a message to the next until the last party outputs a valid vertex cover of the whole graph. We are particularly interested in the trade-off between the size of the messages sent and the approximation ratio of the output solution. It is straightforward to see that any constant approximation protocol for MVC requires communicating Ω(n) bits. Additionally, there exists a trivial 2-approximation protocol where the parties collectively find a maximal matching of the graph greedily and return the subset of vertices matched. This raises a natural question: What is the best approximation ratio achievable using optimal communication of O(n)? We design a protocol with an approximation ratio of (2-2^{-k+1}+ε) and O(n) communication for any desirably small constant ε > 0, which is strictly better than 2 for any constant number of parties. Moreover, we show that achieving an approximation ratio smaller than 3/2 for the two-party case requires n^{1 + Ω(1/lg lg n)} communication, thereby establishing the tightness of our protocol for two parties. A notable aspect of our protocol is that no edges are communicated between the parties. Instead, for any 1 ≤ i < k, the i-th party only communicates a constant number of vertex covers for all edges assigned to the first i parties. An interesting consequence is that the communication cost of our protocol is O(n) bits, as opposed to the typical Ω(nlog n) bits required for many graph problems, such as maximum matching, where protocols commonly involve communicating edges.
Cite as

Mahsa Derakhshan, Andisheh Ghasemi, and Rajmohan Rajaraman. One-Way Communication Complexity of Minimum Vertex Cover in General Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 66:1-66:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derakhshan_et_al:LIPIcs.ICALP.2025.66,
  author =	{Derakhshan, Mahsa and Ghasemi, Andisheh and Rajaraman, Rajmohan},
  title =	{{One-Way Communication Complexity of Minimum Vertex Cover in General Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{66:1--66:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.66},
  URN =		{urn:nbn:de:0030-drops-234430},
  doi =		{10.4230/LIPIcs.ICALP.2025.66},
  annote =	{Keywords: Communication Complexity, Minimum Vertex Cover}
}
Document
Replication Paper
DOI: 10.4230/LIPIcs.ECOOP.2025.40
Scaling Up: Revisiting Mining Android Sandboxes at Scale for Malware Classification (Replication Paper)

Authors: Francisco Handrick Tomaz da Costa, Ismael Medeiros, Leandro Oliveira, João Calássio, Rodrigo Bonifácio, Krishna Narasimhan, Mira Mezini, and Márcio Ribeiro

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
The widespread use of smartphones in daily life has raised concerns about privacy and security among researchers and practitioners. Privacy issues are generally highly prevalent in mobile applications, particularly targeting the Android platform - the most popular mobile operating system. For this reason, several techniques have been proposed to identify malicious behavior in Android applications, including the Mining Android Sandbox approach (MAS approach), which aims to identify malicious behavior in repackaged Android applications (apps). However, previous empirical studies evaluated the MAS approach using a small dataset consisting of only 102 pairs of original and repackaged apps. This limitation raises questions about the external validity of their findings and whether the MAS approach can be generalized to larger datasets. To address these concerns, this paper presents the results of a replication study focused on evaluating the performance of the MAS approach regarding its capabilities of correctly classifying malware from different families. Unlike previous studies, our research employs a dataset that is an order of magnitude larger, comprising 4,076 pairs of apps covering a more diverse range of Android malware families. Surprisingly, our findings indicate a poor performance of the MAS approach for identifying malware, with the F1-score decreasing from 0.90 for the small dataset used in the previous studies to 0.54 in our more extensive dataset. Upon closer examination, we discovered that certain malware families partially account for the low accuracy of the MAS approach, which fails to classify a repackaged version of an app as malware correctly. Our findings highlight the limitations of the MAS approach, particularly when scaled, and underscore the importance of complementing it with other techniques to detect a broader range of malware effectively. This opens avenues for further discussion on addressing the blind spots that affect the accuracy of the MAS approach.
Cite as

Francisco Handrick Tomaz da Costa, Ismael Medeiros, Leandro Oliveira, João Calássio, Rodrigo Bonifácio, Krishna Narasimhan, Mira Mezini, and Márcio Ribeiro. Scaling Up: Revisiting Mining Android Sandboxes at Scale for Malware Classification (Replication Paper). In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 40:1-40:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{handricktomazdacosta_et_al:LIPIcs.ECOOP.2025.40,
  author =	{Handrick Tomaz da Costa, Francisco and Medeiros, Ismael and Oliveira, Leandro and Cal\'{a}ssio, Jo\~{a}o and Bonif\'{a}cio, Rodrigo and Narasimhan, Krishna and Mezini, Mira and Ribeiro, M\'{a}rcio},
  title =	{{Scaling Up: Revisiting Mining Android Sandboxes at Scale for Malware Classification}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{40:1--40:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.40},
  URN =		{urn:nbn:de:0030-drops-233320},
  doi =		{10.4230/LIPIcs.ECOOP.2025.40},
  annote =	{Keywords: Android Malware Detection, Dynamic Analysis, Mining Android Sandboxes}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.89
Optimal Communication Complexity of Chained Index

Authors: Janani Sundaresan

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

Abstract
We study the chain communication problem introduced by Cormode et al. [ICALP 2019]. For k ≥ 1, in the chain_{n,k} problem, there are k string and index pairs (X_i, σ_i) for i ∈ [k] such that the value at position σ_i in string X_i is the same bit for all k pairs. The input is shared between k+1 players as follows. Player 1 has the first string X₁ ∈ {0,1}ⁿ, player 2 has the first index σ₁ ∈ [n] and the second string X₂ ∈ {0,1}ⁿ, player 3 has the second index σ₂ ∈ [n] along with the third string X₃ ∈ {0,1}ⁿ, and so on. Player k+1 has the last index σ_k ∈ [n]. The communication is one way from each player to the next, starting from player 1 to player 2, then from player 2 to player 3 and so on. Player k+1, after receiving the message from player k, has to output a single bit which is the value at position σ_i in X_i for any i ∈ [k]. It is a generalization of the well-studied index problem, which is equivalent to chain_{n, 2}. Cormode et al. proved that the chain_{n,k} problem requires Ω(n/k²) communication, and they used it to prove streaming lower bounds for the approximation of maximum independent sets. Subsequently, Feldman et al. [STOC 2020] used it to prove lower bounds for streaming submodular maximization. However, it is not known whether the Ω(n/k²) lower bound used in these works is optimal for the problem, and in fact, it was conjectured by Cormode et al. that Ω(n) bits are necessary. We prove the optimal lower bound of Ω(n) for chain_{n,k} when k = o(n/log n) as our main result. This settles the open conjecture of Cormode et al., barring the range of k = Ω(n /log n). The main technique is a reduction to a non-standard index problem where the input to the players is such that the answer is biased away from uniform. This biased version of index is analyzed using tools from information theory. As a corollary, we get an improved lower bound for approximation of maximum independent set in vertex arrival streams via a reduction from chain directly.
Cite as

Janani Sundaresan. Optimal Communication Complexity of Chained Index. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 89:1-89:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sundaresan:LIPIcs.ITCS.2025.89,
  author =	{Sundaresan, Janani},
  title =	{{Optimal Communication Complexity of Chained Index}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{89:1--89: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.89},
  URN =		{urn:nbn:de:0030-drops-227172},
  doi =		{10.4230/LIPIcs.ITCS.2025.89},
  annote =	{Keywords: communication complexity, index communciation problem}
}
Document
Survey
DOI: 10.4230/TGDK.1.1.11
How Does Knowledge Evolve in Open Knowledge Graphs?

Authors: Axel Polleres, Romana Pernisch, Angela Bonifati, Daniele Dell'Aglio, Daniil Dobriy, Stefania Dumbrava, Lorena Etcheverry, Nicolas Ferranti, Katja Hose, Ernesto Jiménez-Ruiz, Matteo Lissandrini, Ansgar Scherp, Riccardo Tommasini, and Johannes Wachs

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
Openly available, collaboratively edited Knowledge Graphs (KGs) are key platforms for the collective management of evolving knowledge. The present work aims t o provide an analysis of the obstacles related to investigating and processing specifically this central aspect of evolution in KGs. To this end, we discuss (i) the dimensions of evolution in KGs, (ii) the observability of evolution in existing, open, collaboratively constructed Knowledge Graphs over time, and (iii) possible metrics to analyse this evolution. We provide an overview of relevant state-of-the-art research, ranging from metrics developed for Knowledge Graphs specifically to potential methods from related fields such as network science. Additionally, we discuss technical approaches - and their current limitations - related to storing, analysing and processing large and evolving KGs in terms of handling typical KG downstream tasks.
Cite as

Axel Polleres, Romana Pernisch, Angela Bonifati, Daniele Dell'Aglio, Daniil Dobriy, Stefania Dumbrava, Lorena Etcheverry, Nicolas Ferranti, Katja Hose, Ernesto Jiménez-Ruiz, Matteo Lissandrini, Ansgar Scherp, Riccardo Tommasini, and Johannes Wachs. How Does Knowledge Evolve in Open Knowledge Graphs?. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 11:1-11:59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{polleres_et_al:TGDK.1.1.11,
  author =	{Polleres, Axel and Pernisch, Romana and Bonifati, Angela and Dell'Aglio, Daniele and Dobriy, Daniil and Dumbrava, Stefania and Etcheverry, Lorena and Ferranti, Nicolas and Hose, Katja and Jim\'{e}nez-Ruiz, Ernesto and Lissandrini, Matteo and Scherp, Ansgar and Tommasini, Riccardo and Wachs, Johannes},
  title =	{{How Does Knowledge Evolve in Open Knowledge Graphs?}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{11:1--11:59},
  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.11},
  URN =		{urn:nbn:de:0030-drops-194855},
  doi =		{10.4230/TGDK.1.1.11},
  annote =	{Keywords: KG evolution, temporal KG, versioned KG, dynamic KG}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.24
Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting

Authors: Jacques Dark, Adithya Diddapur, and Christian Konrad

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
We study the Interval Selection problem in data streams: Given a stream of n intervals on the line, the objective is to compute a largest possible subset of non-overlapping intervals using O(|OPT|) space, where |OPT| is the size of an optimal solution. Previous work gave a 3/2-approximation for unit-length and a 2-approximation for arbitrary-length intervals [Emek et al., ICALP'12]. We extend this line of work to weighted intervals as well as to insertion-deletion streams. Our results include: 1) When considering weighted intervals, a (3/2+ε)-approximation can be achieved for unit intervals, but any constant factor approximation for arbitrary-length intervals requires space Ω(n). 2) In the insertion-deletion setting where intervals can both be added and deleted, we prove that, even without weights, computing a constant factor approximation for arbitrary-length intervals requires space Ω(n), whereas in the weighted unit-length intervals case a (2+ε)-approximation can be obtained. Our lower bound results are obtained via reductions to the recently introduced Chained-Index communication problem, further demonstrating the strength of this problem in the context of streaming geometric independent set problems.
Cite as

Jacques Dark, Adithya Diddapur, and Christian Konrad. Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dark_et_al:LIPIcs.FSTTCS.2023.24,
  author =	{Dark, Jacques and Diddapur, Adithya and Konrad, Christian},
  title =	{{Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.24},
  URN =		{urn:nbn:de:0030-drops-193976},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.24},
  annote =	{Keywords: Streaming Algorithms, Interval Selection, Weighted Intervals, Insertion-deletion Streams}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.30
Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams

Authors: Jacques Dark and Christian Konrad

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
In this paper, we give simple optimal lower bounds on the one-way two-party communication complexity of approximate Maximum Matching and Minimum Vertex Cover with deletions. In our model, Alice holds a set of edges and sends a single message to Bob. Bob holds a set of edge deletions, which form a subset of Alice’s edges, and needs to report a large matching or a small vertex cover in the graph spanned by the edges that are not deleted. Our results imply optimal space lower bounds for insertion-deletion streaming algorithms for Maximum Matching and Minimum Vertex Cover. Previously, Assadi et al. [SODA 2016] gave an optimal space lower bound for insertion-deletion streaming algorithms for Maximum Matching via the simultaneous model of communication. Our lower bound is simpler and stronger in several aspects: The lower bound of Assadi et al. only holds for algorithms that (1) are able to process streams that contain a triple exponential number of deletions in n, the number of vertices of the input graph; (2) are able to process multi-graphs; and (3) never output edges that do not exist in the input graph when the randomized algorithm errs. In contrast, our lower bound even holds for algorithms that (1) rely on short (O(n²)-length) input streams; (2) are only able to process simple graphs; and (3) may output non-existing edges when the algorithm errs.
Cite as

Jacques Dark and Christian Konrad. Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dark_et_al:LIPIcs.CCC.2020.30,
  author =	{Dark, Jacques and Konrad, Christian},
  title =	{{Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.30},
  URN =		{urn:nbn:de:0030-drops-125824},
  doi =		{10.4230/LIPIcs.CCC.2020.30},
  annote =	{Keywords: Maximum matching, Minimum vertex cover, Dynamic graph streams, Communication complexity, Lower bounds}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.45
Independent Sets in Vertex-Arrival Streams

Authors: Graham Cormode, Jacques Dark, and Christian Konrad

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

Abstract
We consider the maximal and maximum independent set problems in three models of graph streams: - In the edge model we see a stream of edges which collectively define a graph; this model is well-studied for a variety of problems. We show that the space complexity for a one-pass streaming algorithm to find a maximal independent set is quadratic (i.e. we must store all edges). We further show that it is not much easier if we only require approximate maximality. This contrasts strongly with the other two vertex-based models, where one can greedily find an exact solution in only the space needed to store the independent set. - In the "explicit" vertex model, the input stream is a sequence of vertices making up the graph. Every vertex arrives along with its incident edges that connect to previously arrived vertices. Various graph problems require substantially less space to solve in this setting than in edge-arrival streams. We show that every one-pass c-approximation streaming algorithm for maximum independent set (MIS) on explicit vertex streams requires Omega({n^2}/{c^6}) bits of space, where n is the number of vertices of the input graph. It is already known that Theta~({n^2}/{c^2}) bits of space are necessary and sufficient in the edge arrival model (Halldórsson et al. 2012), thus the MIS problem is not significantly easier to solve under the explicit vertex arrival order assumption. Our result is proved via a reduction from a new multi-party communication problem closely related to pointer jumping. - In the "implicit" vertex model, the input stream consists of a sequence of objects, one per vertex. The algorithm is equipped with a function that maps pairs of objects to the presence or absence of edges, thus defining the graph. This model captures, for example, geometric intersection graphs such as unit disc graphs. Our final set of results consists of several improved upper and lower bounds for interval and square intersection graphs, in both explicit and implicit streams. In particular, we show a gap between the hardness of the explicit and implicit vertex models for interval graphs.
Cite as

Graham Cormode, Jacques Dark, and Christian Konrad. Independent Sets in Vertex-Arrival Streams. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cormode_et_al:LIPIcs.ICALP.2019.45,
  author =	{Cormode, Graham and Dark, Jacques and Konrad, Christian},
  title =	{{Independent Sets in Vertex-Arrival Streams}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{45:1--45:14},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.45},
  URN =		{urn:nbn:de:0030-drops-106212},
  doi =		{10.4230/LIPIcs.ICALP.2019.45},
  annote =	{Keywords: streaming algorithms, independent set size, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2018.13
Fast Sketch-based Recovery of Correlation Outliers

Authors: Graham Cormode and Jacques Dark

Published in: LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018)

Abstract
Many data sources can be interpreted as time-series, and a key problem is to identify which pairs out of a large collection of signals are highly correlated. We expect that there will be few, large, interesting correlations, while most signal pairs do not have any strong correlation. We abstract this as the problem of identifying the highly correlated pairs in a collection of n mostly pairwise uncorrelated random variables, where observations of the variables arrives as a stream. Dimensionality reduction can remove dependence on the number of observations, but further techniques are required to tame the quadratic (in n) cost of a search through all possible pairs. We develop a new algorithm for rapidly finding large correlations based on sketch techniques with an added twist: we quickly generate sketches of random combinations of signals, and use these in concert with ideas from coding theory to decode the identity of correlated pairs. We prove correctness and compare performance and effectiveness with the best LSH (locality sensitive hashing) based approach.
Cite as

Graham Cormode and Jacques Dark. Fast Sketch-based Recovery of Correlation Outliers. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cormode_et_al:LIPIcs.ICDT.2018.13,
  author =	{Cormode, Graham and Dark, Jacques},
  title =	{{Fast Sketch-based Recovery of Correlation Outliers}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Kimelfeld, Benny and Amsterdamer, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.13},
  URN =		{urn:nbn:de:0030-drops-86094},
  doi =		{10.4230/LIPIcs.ICDT.2018.13},
  annote =	{Keywords: correlation, sketching, streaming, dimensionality reduction}
}
  • Refine by Type
  • 14 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 8 2025
  • 2 2023
  • 1 2020
  • 1 2019
  • Show More...

  • Refine by Author
  • 6 Konrad, Christian
  • 5 Dark, Jacques
  • 2 Cormode, Graham
  • 2 Diddapur, Adithya
  • 1 Alexandru, Cezar-Mihail
  • Show More...

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

  • Refine by Classification
  • 5 Theory of computation → Streaming models
  • 4 Theory of computation → Communication complexity
  • 3 Theory of computation → Lower bounds and information complexity
  • 3 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 1 Information systems → Data streaming
  • Show More...

  • Refine by Keyword
  • 3 Streaming Algorithms
  • 2 Maximum Matching
  • 2 communication complexity
  • 1 Android Malware Detection
  • 1 Bounded-Deletion Streams
  • 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