DROPS

Volume

LIPIcs, Volume 245

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference)

Editors: Amit Chakrabarti and Chaitanya Swamy

Document

DOI: 10.4230/LIPIcs.SEA.2026.4

Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance

Authors: Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract

The Median String Problem calls for finding a string that minimizes the average distance from a given set of strings. Under the Levenshtein (or edit) metric, the problem is NP-hard even for binary strings. We devised two novel integer linear programming models for this case and tested them against the only formulation we are aware of in the literature. Our numerical experiments attest to the efficacy of the proposed approach.

Cite as

Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti. Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{arbib_et_al:LIPIcs.SEA.2026.4,
  author =	{Arbib, Claudio and D'Ascenzo, Andrea and Kara\c{s}an, Oya E. and Pizzuti, Andrea},
  title =	{{Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.4},
  URN =		{urn:nbn:de:0030-drops-260081},
  doi =		{10.4230/LIPIcs.SEA.2026.4},
  annote =	{Keywords: Levenshtein Distance, Median String Problem, Integer Programming}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.15

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming

Authors: Avinandan Das

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

This paper investigates the semi-streaming complexity of k-partial coloring, a generalization of proper graph coloring. For k ≥ 1, a k-partial coloring requires that each vertex v in an n-node graph is assigned a color such that at least min{k, deg(v)} of its neighbors are assigned colors different from its own. This framework naturally extends classical coloring problems: specifically, k-partial (k+1)-coloring and k-partial k-coloring generalize (Δ+1)-proper coloring and Δ-proper coloring, respectively. Prior works of Assadi, Chen, and Khanna [SODA 2019] and Assadi, Kumar, and Mittal [TheoretiCS 2023] show that both (Δ+1)-proper coloring and Δ-proper coloring admit one-pass randomized semi-streaming algorithms. We explore whether these efficiency gains extend to their partial coloring generalizations and reveal a sharp computational threshold: while k-partial (k+1)-coloring admits a one-pass randomized semi-streaming algorithm, the k-partial k-coloring remains semi-streaming intractable, effectively demonstrating a "dichotomy of one color" in the streaming model.

Cite as

Avinandan Das. One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{das:LIPIcs.SWAT.2026.15,
  author =	{Das, Avinandan},
  title =	{{One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.15},
  URN =		{urn:nbn:de:0030-drops-260515},
  doi =		{10.4230/LIPIcs.SWAT.2026.15},
  annote =	{Keywords: Graph Coloring, Semi-streaming algorithms, Lower bounds}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.32

Semirandom Planted Bipartite Subgraphs

Authors: Anand Louis and Kirtan Vora

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

There have been many recent works studying planted subgraphs problems. The semirandom planted bipartite subgraph problem is defined as follows. Starting with a vertex set V, an arbitrary subset S ⊂ V of size k is chosen, then an arbitrary bipartite graph is added on S. After this between each pair of vertices in S × (V ⧵ S) an edge is added independently with probability p, then an arbitrary graph is added on V⧵ S. The analogous semirandom planted clique problem, where S forms a clique, has been studied starting with the work of Fiege and Kilian [Uriel Feige and Joe Kilian, 2001]; recent work by [Blasiok et al., 2024; Venkatesan Guruswami and Hsin-Po Wang, 2025] gave an algorithm for this problem when k = Ω(√{n log n}). We give an algorithm for semirandom planted bipartite subgraph problem when k = Ω(√{n log n}) and the two color classes are roughly balanced. Our algorithms are essentially the same as the elegant greedy algorithm of [Blasiok et al., 2024]. We generalize their idea to our setting. Handling the arbitrary nature of the bipartite graph requires some new technical ideas and is our main technical contribution.

Cite as

Anand Louis and Kirtan Vora. Semirandom Planted Bipartite Subgraphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{louis_et_al:LIPIcs.SWAT.2026.32,
  author =	{Louis, Anand and Vora, Kirtan},
  title =	{{Semirandom Planted Bipartite Subgraphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.32},
  URN =		{urn:nbn:de:0030-drops-260681},
  doi =		{10.4230/LIPIcs.SWAT.2026.32},
  annote =	{Keywords: Semirandom Models, Spectral Algorithms, Planted Subgraphs, Random Graphs, Approximate Recovery Algorithms}
}

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.STACS.2026.13

Line Cover and Related Problems

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana

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

Abstract

We study several extensions of the classic Line Cover problem of covering a set of n points in the plane with k lines. Line Cover is known to be NP-hard and our focus is on two natural generalizations: (1) Line Clustering, where the objective is to find k lines in the plane that minimize the sum of squares of distances of a given set of input points to the closest line, and (2) Hyperplane Cover, where the goal is to cover n points in ℝ^d by k hyperplanes. We also consider the more general Projective Clustering problem, which unifies both of these and has numerous applications in machine learning, data mining, and computational geometry. In this problem one seeks k affine subspaces of dimension r minimizing the sum of squares of distances of a given set of n points in ℝ^d to the closest point within one of the k affine subspaces. Our main contributions reveal interesting differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable parameterized by the number k of lines in the solution, we show that Line Clustering is W[1]-hard when parameterized by k and rule out algorithms of running time n^{o(k)} under the Exponential Time Hypothesis. Hyperplane Cover is known to be NP-hard even when d = 2 and by the work of Langerman and Morin [Discrete & Computational Geometry, 2005], it is FPT parameterized by k and d. We complement this result by establishing that Hyperplane Cover is W[2]-hard when parameterized by only k. We complement our hardness results by presenting an algorithm for Projective Clustering. We show that this problem is solvable in n^{𝒪(dk(r+1))} time. Not only does this yield an upper bound for Line Clustering that asymptotically matches our lower bound, but it also significantly extends the seminal work on k-Means Clustering (the special case r = 0) by Inaba, Katoh, and Imai [SoCG 1994].

Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana. Line Cover and Related Problems. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.13,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Saha, Souvik and Seetharaman, Sanjay and Upasana, Anannya},
  title =	{{Line Cover and Related Problems}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{13:1--13:18},
  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.13},
  URN =		{urn:nbn:de:0030-drops-255023},
  doi =		{10.4230/LIPIcs.STACS.2026.13},
  annote =	{Keywords: Point Line Cover, Projective Clustering, W-hardness, XP algorithm}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.112

Lower Bounds Beyond DNF of Parities

Authors: Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We consider a subclass of AC⁰[2] circuits that simultaneously captures DNF∘Xor and depth-3 AC⁰ circuits. For this class we show a technique for proving lower bounds inspired by the top-down approach. We give lower bounds for the middle slice function, inner product function, and affine dispersers.

Cite as

Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov. Lower Bounds Beyond DNF of Parities. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 112:1-112:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{riazanov_et_al:LIPIcs.ITCS.2026.112,
  author =	{Riazanov, Artur and Sofronova, Anastasia and Sokolov, Dmitry},
  title =	{{Lower Bounds Beyond DNF of Parities}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{112:1--112:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.112},
  URN =		{urn:nbn:de:0030-drops-253996},
  doi =		{10.4230/LIPIcs.ITCS.2026.112},
  annote =	{Keywords: boolean circuits, top-down, unpredictability}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.40

A Simple and Robust Protocol for Distributed Counting

Authors: Edith Cohen, Moshe Shechner, and Uri Stemmer

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across k sites while minimizing communication. The communication complexity of this problem is known to be Θ(k/(ε)log N) for deterministic protocols. Huang, Yi, and Zhang (2012) showed that randomization can reduce this to Θ((√k)/ε log N), but their analysis is restricted to the oblivious setting, where the stream of events is independent of the protocol’s outputs. Xiong, Zhu, and Huang (2023) presented a robust protocol for distributed counting that removes the oblivious assumption. However, their communication complexity is suboptimal by a polylog(k) factor and their protocol is substantially more complex than the oblivious protocol of Huang et al. (2012). This left open a natural question: could it be that the simple protocol of Huang et al. (2012) is already robust? We resolve this question with two main contributions. First, we show that the protocol of Huang et al. (2012) is itself not robust by constructing an explicit adaptive attack that forces it to lose its accuracy. Second, we present a new, surprisingly simple, robust protocol for distributed counting that achieves the optimal communication complexity of O((√k)/ε log N). Our protocol is simpler than that of Xiong et al. (2023), perhaps even simpler than that of Huang et al. (2012), and is the first to match the optimal oblivious complexity in the adaptive setting.

Cite as

Edith Cohen, Moshe Shechner, and Uri Stemmer. A Simple and Robust Protocol for Distributed Counting. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ITCS.2026.40,
  author =	{Cohen, Edith and Shechner, Moshe and Stemmer, Uri},
  title =	{{A Simple and Robust Protocol for Distributed Counting}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{40:1--40:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.40},
  URN =		{urn:nbn:de:0030-drops-253272},
  doi =		{10.4230/LIPIcs.ITCS.2026.40},
  annote =	{Keywords: Distributed Streaming, Adversarial Streaming}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.98

Weighted Chairman Assignment and Flow-Time Scheduling

Authors: Siyue Liu and Victor Reis

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Given positive integers m, n, a fractional assignment x ∈ [0,1]^{m × n} and weights d ∈ ℝⁿ_{> 0}, we show that there exists an assignment y ∈ {0,1}^{m × n} so that for every i ∈ [m] and t ∈ [n], |∑_{j ∈ [t]} d_j (x_{ij} - y_{ij})| < max_{j ∈ [n]} d_j. This generalizes a result of Tijdeman (1973) on the unweighted version, known as the chairman assignment problem. This also confirms a special case of the single-source unsplittable flow conjecture with arc-wise lower and upper bounds due to Morell and Skutella (IPCO 2020). As an application, we consider a scheduling problem where jobs have release times and machines have closing times, and a job can only be scheduled on a machine if it is released before the machine closes. We give a 3-approximation algorithm for maximum flow-time minimization.

Cite as

Siyue Liu and Victor Reis. Weighted Chairman Assignment and Flow-Time Scheduling. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 98:1-98:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2026.98,
  author =	{Liu, Siyue and Reis, Victor},
  title =	{{Weighted Chairman Assignment and Flow-Time Scheduling}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{98:1--98:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.98},
  URN =		{urn:nbn:de:0030-drops-253858},
  doi =		{10.4230/LIPIcs.ITCS.2026.98},
  annote =	{Keywords: prefix discrepancy, flow-time scheduling, unsplittable flow}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.16

Robust Streaming Against Low-Memory Adversaries

Authors: Omri Ben-Eliezer, Krzysztof Onak, and Sandeep Silwal

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Robust streaming, the study of streaming algorithms that provably work when the stream is generated by an adaptive adversary, has seen tremendous progress in recent years. However, fundamental barriers remain: the best known algorithm for turnstile F_p-estimation in the robust streaming setting is exponentially worse than in the oblivious setting, and closing this gap seems difficult. Arguably, one possible cause of this barrier is the adversarial model, which may be too strong: unlike the space-bounded streaming algorithm, the adversary can memorize the entire history of the interaction with the algorithm. Can we then close the exponential gap if we insist that the adversary itself is an adaptive but low-memory entity, roughly as powerful as (or even weaker than) the algorithm? In this work we present the first set of models and results aimed towards this question. We design efficient robust streaming algorithms against adversaries that are fully adaptive but have no long-term memory ("memoryless") or very little memory of the history of interaction. Roughly speaking, a memoryless adversary only sees, at any given round, the last output of the algorithm (and does not even know the current time) and can generate an unlimited number of independent coin tosses. A low-memory adversary is similar, but maintains an additional small buffer. While these adversaries may seem quite limited at first glance, we show that this adversarial model is strong enough to produce streams that have high flip number and density in the context of F₂-estimation, which rules out most known robustification techniques. We then design a new simple approach, similar to the computation paths framework, to obtain efficient algorithms against memoryless and low-memory adversaries for a wide class of order-invariant problems. We conclude by posing various open questions proposing further exploration of the landscape of robust streaming against fully adaptive but computationally constrained adversaries.

Cite as

Omri Ben-Eliezer, Krzysztof Onak, and Sandeep Silwal. Robust Streaming Against Low-Memory Adversaries. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2026.16,
  author =	{Ben-Eliezer, Omri and Onak, Krzysztof and Silwal, Sandeep},
  title =	{{Robust Streaming Against Low-Memory Adversaries}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.16},
  URN =		{urn:nbn:de:0030-drops-253037},
  doi =		{10.4230/LIPIcs.ITCS.2026.16},
  annote =	{Keywords: robust streaming, adaptive robustness, bounded-space adversaries}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.64

Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length

Authors: Anna Gal, Gillat Kol, Raghuvansh R. Saxena, and Huacheng Yu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

The space complexity of deterministic streaming algorithms for approximating the length of the longest increasing subsequence (LIS) in a string of length n has been known to be Θ̃(√n) for almost two decades. In contrast, the space complexity of this problem for randomized streaming algorithms remains one of the few longstanding open problems in one-pass streaming. In fact, no better than Ω(log n) lower bounds are known, and the best upper bounds are no better than their deterministic counterparts. In this paper, we push the limits of our understanding of the streaming space complexity of the approximate LIS length problem by studying it in the white-box adversarial streaming model. This model is an intermediate model between deterministic and randomized streaming algorithms that has recently attracted attention. In the white-box model, the streaming algorithm can draw fresh randomness when processing each incoming element, but an adversary generating the stream observes all previously used randomness and adaptively chooses the subsequent elements of the stream. We prove a tight (up to logarithmic factors) Ω(√n) space lower bound for any white-box streaming algorithm that approximates the length of the LIS of a stream of length n to within a factor better than 1.1. Thus, for this problem, white-box algorithms offer no improvement over deterministic ones.

Cite as

Anna Gal, Gillat Kol, Raghuvansh R. Saxena, and Huacheng Yu. Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 64:1-64:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:LIPIcs.ITCS.2026.64,
  author =	{Gal, Anna and Kol, Gillat and Saxena, Raghuvansh R. and Yu, Huacheng},
  title =	{{Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{64:1--64:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.64},
  URN =		{urn:nbn:de:0030-drops-253519},
  doi =		{10.4230/LIPIcs.ITCS.2026.64},
  annote =	{Keywords: White-bos streaming, Longest increasing subsequence}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.105

Fixed-Parameter Tractable Submodular Maximization over a Matroid

Authors: Shamisa Nematollahi, Adrian Vladu, and Junyao Zhao

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

In this paper, we design fixed-parameter tractable (FPT) algorithms for (non-monotone) submodular maximization subject to a matroid constraint, where the matroid rank r is treated as a fixed parameter that is independent of the total number of elements n. We provide two FPT algorithms: one for the offline setting and another for the random-order streaming setting. Our streaming algorithm achieves a 1/2-ε approximation using Õ(r/poly(ε)) memory, while our offline algorithm obtains a 1-(1)/(e)-ε approximation with n⋅ 2^{Õ(r/poly(ε))} runtime and Õ(r/poly(ε)) memory. Both approximation factors are near-optimal in their respective settings, given existing hardness results. In particular, our offline algorithm demonstrates that - unlike in the polynomial-time regime - there is essentially no separation between monotone and non-monotone submodular maximization under a matroid constraint in the FPT framework.

Cite as

Shamisa Nematollahi, Adrian Vladu, and Junyao Zhao. Fixed-Parameter Tractable Submodular Maximization over a Matroid. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 105:1-105:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{nematollahi_et_al:LIPIcs.ITCS.2026.105,
  author =	{Nematollahi, Shamisa and Vladu, Adrian and Zhao, Junyao},
  title =	{{Fixed-Parameter Tractable Submodular Maximization over a Matroid}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{105:1--105:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.105},
  URN =		{urn:nbn:de:0030-drops-253924},
  doi =		{10.4230/LIPIcs.ITCS.2026.105},
  annote =	{Keywords: Submodular maximization, matroids, parameterized complexity, streaming algorithms}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.79

Range Avoidance and Remote Point: New Algorithms and Hardness

Authors: Shengtang Huang, Xin Li, and Yan Zhong

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

The Range Avoidance (Avoid) problem C-Avoid[n,m(n)] asks that, given a circuit in a class C with input length n and output length m(n) > n, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks for proving circuit lower bounds and constructing explicit combinatorial objects. Previous work by Korten (FOCS' 21) and by Ren, Santhanam, and Wang (FOCS' 22) showed that algorithms for Avoid are closely related to circuit lower bounds. In particular, Korten’s work reinterpreted an earlier result from bounded arithmetic, originally proved by Jeřábek (Ann. Pure Appl. Log. 2004), as an equivalence in computational complexity between the existence of FP^NP algorithms for the general Avoid problem and 2^{Ω(n)} lower bounds against general Boolean circuits for the class 𝐄^NP. In this work, we significantly complement these works by generalizing the equivalence result to restricted circuit classes and obtain the following: - For any constant depth unbounded fan-in circuit class C ⊇ AC⁰, there is an FP^NP algorithm for C-Avoid[n,n^{1+ε}] (for any constant ε > 0) if and only if 𝐄^NP cannot be computed by C circuits of size 2^{o(n)}. This addresses an open problem by Korten (Bulletin of EATCS' 25). - If 𝐄^NP cannot be computed by o(2ⁿ/n) size formulas, then there is an FP^NP algorithm for NC⁰-Avoid[n,2n]. Note that by an extension of Ren, Santhanam, and Wang (FOCS' 22), an FP^NP algorithm for NC⁰₄-Avoid[n,n+n^δ] for any constant δ ∈ (0,1) implies 𝐄^NP cannot be computed by o(2ⁿ/n) size formulas. These results yield the first characterizations of FP^NP C-Avoid algorithms for low-complexity circuit classes such as AC⁰. We also consider the average-case analog of Avoid, the Remote Point (Remote-Point) problem, and establish: - For some suitable function c(n) and constant γ > 0, there is an FP^NP algorithm for Remote-Point[n,n^{6+γ},c(O_{γ}(log n))] if and only if 𝐄^NP cannot be (1/2-c(n))-approximated by circuits of size 2^{o(n)}. Finally, we also present two improved algorithms for NC⁰-Avoid: - A family of 2^{n^{1 - ε/(k-1) +o(1)}} time algorithms for NC⁰_k-Avoid[n,n^{1+ε}] for any ε > 0, exhibiting the first subexponential-time algorithm for any super-linear stretch. - Faster local algorithms for NC⁰_k-Avoid[n,n+1] running in time O(n2^{(k-2)/(k-1) n}), improving the naive 2ⁿ⋅ poly(n) bound.

Cite as

Shengtang Huang, Xin Li, and Yan Zhong. Range Avoidance and Remote Point: New Algorithms and Hardness. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 79:1-79:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ITCS.2026.79,
  author =	{Huang, Shengtang and Li, Xin and Zhong, Yan},
  title =	{{Range Avoidance and Remote Point: New Algorithms and Hardness}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{79:1--79:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.79},
  URN =		{urn:nbn:de:0030-drops-253662},
  doi =		{10.4230/LIPIcs.ITCS.2026.79},
  annote =	{Keywords: Circuit Lower Bounds, Range Avoidance Problem, Remote Point Problem}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2025.36

Hardness of Finding Kings and Strong Kings

Authors: Ziad Ismaili Alaoui and Nikhil Mande

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract

A king in a directed graph is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament (a complete graph where each edge has a direction) has at least one king. Our contributions in this work are: - We show that the query complexity of determining existence of a king in arbitrary n-vertex digraphs is Θ(n²). This is in stark contrast to the case where the input is a tournament, where Shen, Sheng, and Wu [SICOMP'03] showed that a king can be found in O(n^{3/2}) queries. - In an attempt to increase the "fairness" in the definition of tournament winners, Ho and Chang [IPL'03] defined a strong king to be a king k such that, for every v that dominates k, the number of length-2 paths from k to v is strictly larger than the number of length-2 paths from v to k. We show that the query complexity of finding a strong king in a tournament is Θ(n²). This answers a question of Biswas, Jayapaul, Raman, and Satti [DAM'22] in the negative. A key component in our proofs is the design of specific tournaments where every vertex is a king, and analyzing certain properties of these tournaments. We feel these constructions and properties are independently interesting and may lead to more interesting results about tournament solutions.

Cite as

Ziad Ismaili Alaoui and Nikhil Mande. Hardness of Finding Kings and Strong Kings. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ismailialaoui_et_al:LIPIcs.FSTTCS.2025.36,
  author =	{Ismaili Alaoui, Ziad and Mande, Nikhil},
  title =	{{Hardness of Finding Kings and Strong Kings}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{36:1--36:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.36},
  URN =		{urn:nbn:de:0030-drops-250856},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.36},
  annote =	{Keywords: Tournaments, kings, query complexity}
}

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 Õ(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}
}

108 Search Results for "Chakrabarti, Amit"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message