3 Search Results for "Ziv, Chen"

Document

DOI: 10.4230/LIPIcs.CCC.2024.7

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy

Authors: Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract

The following question arises naturally in the study of graph streaming algorithms: Is there any graph problem which is "not too hard", in that it can be solved efficiently with total communication (nearly) linear in the number n of vertices, and for which, nonetheless, any streaming algorithm with Õ(n) space (i.e., a semi-streaming algorithm) needs a polynomial n^Ω(1) number of passes? Assadi, Chen, and Khanna [STOC 2019] were the first to prove that this is indeed the case. However, the lower bounds that they obtained are for rather non-standard graph problems. Our first main contribution is to present the first polynomial-pass lower bounds for natural "not too hard" graph problems studied previously in the streaming model: k-cores and degeneracy. We devise a novel communication protocol for both problems with near-linear communication, thus showing that k-cores and degeneracy are natural examples of "not too hard" problems. Indeed, previous work have developed single-pass semi-streaming algorithms for approximating these problems. In contrast, we prove that any semi-streaming algorithm for exactly solving these problems requires (almost) Ω(n^{1/3}) passes. The lower bound follows by a reduction from a generalization of the hidden pointer chasing (HPC) problem of Assadi, Chen, and Khanna, which is also the basis of their earlier semi-streaming lower bounds. Our second main contribution is improved round-communication lower bounds for the underlying communication problems at the basis of these reductions: - We improve the previous lower bound of Assadi, Chen, and Khanna for HPC to achieve optimal bounds for this problem. - We further observe that all current reductions from HPC can also work with a generalized version of this problem that we call MultiHPC, and prove an even stronger and optimal lower bound for this generalization. These two results collectively allow us to improve the resulting pass lower bounds for semi-streaming algorithms by a polynomial factor, namely, from n^{1/5} to n^{1/3} passes.

Cite as

Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7,
  author =	{Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik},
  title =	{{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.7},
  URN =		{urn:nbn:de:0030-drops-204035},
  doi =		{10.4230/LIPIcs.CCC.2024.7},
  annote =	{Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy}
}

Document

DOI: 10.4230/LIPIcs.CCC.2024.19

Information Dissemination via Broadcasts in the Presence of Adversarial Noise

Authors: Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, and Raghuvansh R. Saxena

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract

We initiate the study of error correcting codes over the multi-party adversarial broadcast channel. Specifically, we consider the classic information dissemination problem where n parties, each holding an input bit, wish to know each other’s input. For this, they communicate in rounds, where, in each round, one designated party sends a bit to all other parties over a channel governed by an adversary that may corrupt a constant fraction of the received communication. We mention that the dissemination problem was studied in the stochastic noise model since the 80’s. While stochastic noise in multi-party channels has received quite a bit of attention, the case of adversarial noise has largely been avoided, as such channels cannot handle more than a 1/n-fraction of errors. Indeed, this many errors allow an adversary to completely corrupt the incoming or outgoing communication for one of the parties and fail the protocol. Curiously, we show that by eliminating these "trivial" attacks, one can get a simple protocol resilient to a constant fraction of errors. Thus, a model that rules out such attacks is both necessary and sufficient to get a resilient protocol. The main shortcoming of our dissemination protocol is its length: it requires Θ(n²) communication rounds whereas n rounds suffice in the absence of noise. Our main result is a matching lower bound of Ω(n²) on the length of any dissemination protocol in our model. Our proof first "gets rid" of the channel noise by converting it to a form of "input noise", showing that a noisy dissemination protocol implies a (noiseless) protocol for a version of the direct sum gap-majority problem. We conclude the proof with a tight lower bound for the latter problem, which may be of independent interest.

Cite as

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, and Raghuvansh R. Saxena. Information Dissemination via Broadcasts in the Presence of Adversarial Noise. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 19:1-19:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{efremenko_et_al:LIPIcs.CCC.2024.19,
  author =	{Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Raz, Ran and Saxena, Raghuvansh R.},
  title =	{{Information Dissemination via Broadcasts in the Presence of Adversarial Noise}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{19:1--19:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.19},
  URN =		{urn:nbn:de:0030-drops-204159},
  doi =		{10.4230/LIPIcs.CCC.2024.19},
  annote =	{Keywords: Radio Networks, Interactive Coding, Error Correcting Codes}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2019.62

On the Complexity of the k-Level in Arrangements of Pseudoplanes

Authors: Micha Sharir and Chen Ziv

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract

A classical open problem in combinatorial geometry is to obtain tight asymptotic bounds on the maximum number of k-level vertices in an arrangement of n hyperplanes in R^d (vertices with exactly k of the hyperplanes passing below them). This is essentially a dual version of the k-set problem, which, in a primal setting, seeks bounds for the maximum number of k-sets determined by n points in R^d, where a k-set is a subset of size k that can be separated from its complement by a hyperplane. The k-set problem is still wide open even in the plane. In three dimensions, the best known upper and lower bounds are, respectively, O(nk^{3/2}) [M. Sharir et al., 2001] and nk * 2^{Omega(sqrt{log k})} [G. Tóth, 2000]. In its dual version, the problem can be generalized by replacing hyperplanes by other families of surfaces (or curves in the planes). Reasonably sharp bounds have been obtained for curves in the plane [M. Sharir and J. Zahl, 2017; H. Tamaki and T. Tokuyama, 2003], but the known upper bounds are rather weak for more general surfaces, already in three dimensions, except for the case of triangles [P. K. Agarwal et al., 1998]. The best known general bound, due to Chan [T. M. Chan, 2012] is O(n^{2.997}), for families of surfaces that satisfy certain (fairly weak) properties. In this paper we consider the case of pseudoplanes in R^3 (defined in detail in the introduction), and establish the upper bound O(nk^{5/3}) for the number of k-level vertices in an arrangement of n pseudoplanes. The bound is obtained by establishing suitable (and nontrivial) extensions of dual versions of classical tools that have been used in studying the primal k-set problem, such as the Lovász Lemma and the Crossing Lemma.

Cite as

Micha Sharir and Chen Ziv. On the Complexity of the k-Level in Arrangements of Pseudoplanes. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{sharir_et_al:LIPIcs.SoCG.2019.62,
  author =	{Sharir, Micha and Ziv, Chen},
  title =	{{On the Complexity of the k-Level in Arrangements of Pseudoplanes}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.62},
  URN =		{urn:nbn:de:0030-drops-104662},
  doi =		{10.4230/LIPIcs.SoCG.2019.62},
  annote =	{Keywords: k-level, pseudoplanes, arrangements, three dimensions, k-sets}
}

Refine by Author
1 Assadi, Sepehr
1 Efremenko, Klim
1 Ghosh, Prantar
1 Kol, Gillat
1 Loff, Bruno
Show More...

Refine by Classification
1 Mathematics of computing → Combinatorics
1 Theory of computation → Communication complexity
1 Theory of computation → Computational geometry
1 Theory of computation → Graph algorithms analysis
1 Theory of computation → Lower bounds and information complexity
Show More...

Refine by Keyword
1 Communication complexity
1 Error Correcting Codes
1 Graph streaming
1 Interactive Coding
1 Lower bounds
Show More...

Refine by Type
3 document

Refine by Publication Year
2 2024
1 2019