Search Results

Documents authored by Zhang, Zhijun

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.87
White-Box Adversarial Streaming Lower Bounds Beyond Two-Party Communication

Authors: Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, and Zhijun Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
Streaming algorithms in adversarial settings have attracted considerable attention recently. We show that, in the white-box adversarial streaming model [Miklós Ajtai et al., 2022], the fundamental problem of estimating the F_p moment to within any constant factor requires Ω(n) memory. In this model, the internal state of the (randomized) streaming algorithm is visible to an adversary, who can exploit this information when constructing subsequent stream updates. As a corollary, we also obtain a white-box lower bound for the well-studied problem of estimating the maximum matching size in graphs. [Miklós Ajtai et al., 2022] proved that two-party white-box communication protocols can be derandomized. This allows them to prove deterministic communication lower bounds and automatically derive white-box (communication and streaming) lower bounds. However, such two-party lower bounds can only rule out approximation of the F_p moment within a specific constant factor. Ruling out approximation within any constant factor typically requires proving a lower bound for a multi-party communication problem. We show that white-box communication protocols involving any number of parties can be derandomized, provided they compute a total function. However, this derandomization fails entirely when extended to partial functions and, consequently, to approximation problems. We are therefore compelled to prove our moment estimation lower bound for the white-box model directly. Our proof introduces a novel hybrid technique that, instead of taking hybrids over input distributions, constructs hybrids over white-box adversaries.
Cite as

Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, and Zhijun Zhang. White-Box Adversarial Streaming Lower Bounds Beyond Two-Party Communication. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 87:1-87:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{efremenko_et_al:LIPIcs.ICALP.2026.87,
  author =	{Efremenko, Klim and Kol, Gillat and Saxena, Raghuvansh R. and Zhang, Zhijun},
  title =	{{White-Box Adversarial Streaming Lower Bounds Beyond Two-Party Communication}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{87:1--87:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.87},
  URN =		{urn:nbn:de:0030-drops-264760},
  doi =		{10.4230/LIPIcs.ICALP.2026.87},
  annote =	{Keywords: White-box streaming, moment estimation, hybrid argument}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.105
Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness

Authors: Bernhard Haeupler, Antti Roeyskoe, and Zhijun Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
All parallel algorithms for directed reachability and shortest paths crucially rely on efficient shortcut constructions. These constructions find directed paths and shortcut them by adding edges, with the goal to reduce the diameter of the graph. A long sequence of works has studied (efficient) shortcut constructions as well as impossibility results on the best diameter and therefore the best parallelism that can be achieved via this approach. This paper introduces a new conceptual tool for this line of research in the form of a simple and natural structural criterion: A shortcut H for a graph G is certified if for any shortcut edge (u, v) ∈ H, there exists a vertex w such that the edges (u, w) and (w, v) are also in G ∪ H. We show that this criterion captures constructiveness in the following sense: A shortcut H can be constructed in t time by repeatedly spending 𝓁 time on shortcutting a path of length 𝓁, if and only if, there exists a certified shortcut H' ⊇ H of size Õ(t). Furthermore, all known shortcut constructions with efficient algorithms can be extended to produce certified shortcuts of size Õ(m). On the other hand, for shortcut constructions for which attempts to find efficient implementations have failed, we can show that this is impossible. We also obtain stronger diameter lower bounds for certified shortcuts and hopsets. For example, no certified shortcut construction with almost-linear size can reduce a graph’s diameter below n^{1/4-o(1)}. This seems to be the best bound one can hope for with current techniques.
Cite as

Bernhard Haeupler, Antti Roeyskoe, and Zhijun Zhang. Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 105:1-105:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{haeupler_et_al:LIPIcs.ICALP.2026.105,
  author =	{Haeupler, Bernhard and Roeyskoe, Antti and Zhang, Zhijun},
  title =	{{Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{105:1--105:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.105},
  URN =		{urn:nbn:de:0030-drops-264942},
  doi =		{10.4230/LIPIcs.ICALP.2026.105},
  annote =	{Keywords: Certified shortcuts, directed reachability, parallel shortest paths}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.55
Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs

Authors: Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, and Zhijun Zhang

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

Abstract
Sampling a random walk is a fundamental primitive in many graph applications. In the streaming model, it is known that sampling an L-step random walk on an n-vertex directed graph requires Ω(n L) space, implying that no sublinear-space streaming algorithm exists for general graphs. We show that sublinear algorithms are possible for the case of dense graphs, where every vertex has out-degree at least Ω(n). In particular, we give a one-pass turnstile streaming algorithm that uses only 𝒪̃(L) memory for such graphs. More broadly, for graphs with minimum out-degree at least d, our streaming algorithm samples a random walk using 𝒪̃(n/d ⋅ L) memory. We show that our algorithm is optimal in a strong "beyond worst-case" sense. To formalize this, we introduce the notion of universal optimality for graph streaming algorithms. Informally, a streaming algorithm is universally optimal if it performs (almost) as well as possible on every graph, assuming a worst-case choice of the streaming order. This notion of universal optimality is a key conceptual contribution of our work.
Cite as

Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, and Zhijun Zhang. Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 55:1-55:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{efremenko_et_al:LIPIcs.ITCS.2026.55,
  author =	{Efremenko, Klim and Kol, Gillat and Saxena, Raghuvansh R. and Zhang, Zhijun},
  title =	{{Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{55:1--55:20},
  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.55},
  URN =		{urn:nbn:de:0030-drops-253423},
  doi =		{10.4230/LIPIcs.ITCS.2026.55},
  annote =	{Keywords: Random Walk, streaming Algorithm, universal Optimality}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.22
Round-Vs-Resilience Tradeoffs for Binary Feedback Channels

Authors: Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, and Zhijun Zhang

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

Abstract
In a celebrated result from the 60’s, Berlekamp showed that feedback can be used to increase the maximum fraction of adversarial noise that can be tolerated by binary error correcting codes from 1/4 to 1/3. However, his result relies on the assumption that feedback is "continuous", i.e., after every utilization of the channel, the sender gets the symbol received by the receiver. While this assumption is natural in some settings, in other settings it may be unreasonable or too costly to maintain. In this work, we initiate the study of round-restricted feedback channels, where the number r of feedback rounds is possibly much smaller than the number of utilizations of the channel. Error correcting codes for such channels are protocols where the sender can ask for feedback at most r times, and, upon a feedback request, it obtains all the symbols received since its last feedback request. We design such error correcting protocols for both the adversarial binary erasure channel and for the adversarial binary corruption (bit flip) channel. For the erasure channel, we give an exact characterization of the round-vs-resilience tradeoff by designing a (constant rate) protocol with r feedback rounds, for every r, and proving that its noise resilience is optimal. Designing such error correcting protocols for the corruption channel is substantially more involved. We show that obtaining the optimal resilience, even with one feedback round (r = 1), requires settling (proving or disproving) a new, seemingly unrelated, "clean" combinatorial conjecture, about the maximum cut in weighted graphs versus the "imbalance" of an average cut. Specifically, we prove an upper bound on the optimal resilience (impossibility result), and show that the existence of a matching lower bound (a protocol) is equivalent to the correctness of our conjecture.
Cite as

Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, and Zhijun Zhang. Round-Vs-Resilience Tradeoffs for Binary Feedback Channels. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.ITCS.2025.22,
  author =	{Braverman, Mark and Efremenko, Klim and Kol, Gillat and Saxena, Raghuvansh R. and Zhang, Zhijun},
  title =	{{Round-Vs-Resilience Tradeoffs for Binary Feedback Channels}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{22:1--22:23},
  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.22},
  URN =		{urn:nbn:de:0030-drops-226506},
  doi =		{10.4230/LIPIcs.ITCS.2025.22},
  annote =	{Keywords: Round-restricted feedback channel, error correcting code, noise resilience}
}
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