Search Results

Documents authored by Bera, Suman K.

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.11
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models

Authors: Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We study the problem of coloring a given graph using a small number of colors in several well-established models of computation for big data. These include the data streaming model, the general graph query model, the massively parallel communication (MPC) model, and the CONGESTED-CLIQUE and the LOCAL models of distributed computation. On the one hand, we give algorithms with sublinear complexity, for the appropriate notion of complexity in each of these models. Our algorithms color a graph G using κ(G)⋅(1+o(1)) colors, where κ(G) is the degeneracy of G: this parameter is closely related to the arboricity α(G). As a function of κ(G) alone, our results are close to best possible, since the optimal number of colors is κ(G)+1. For several classes of graphs, including real-world "big graphs," our results improve upon the number of colors used by the various (Δ(G)+1)-coloring algorithms known for these models, where Δ(G) is the maximum degree in G, since Δ(G) ⩾ κ(G) and can in fact be arbitrarily larger than κ(G). On the other hand, we establish certain lower bounds indicating that sublinear algorithms probably cannot go much further. In particular, we prove that any randomized coloring algorithm that uses at most κ(G)+O(1) colors would require Ω(n²) storage in the one pass streaming model, and Ω(n²) many queries in the general graph query model, where n is the number of vertices in the graph. These lower bounds hold even when the value of κ(G) is known in advance; at the same time, our upper bounds do not require κ(G) to be given in advance.
Cite as

Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bera_et_al:LIPIcs.ICALP.2020.11,
  author =	{Bera, Suman K. and Chakrabarti, Amit and Ghosh, Prantar},
  title =	{{Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.11},
  URN =		{urn:nbn:de:0030-drops-124182},
  doi =		{10.4230/LIPIcs.ICALP.2020.11},
  annote =	{Keywords: Data streaming, Graph coloring, Sublinear algorithms, Massively parallel communication, Distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.38
Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six

Authors: Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We consider the problem of counting all k-vertex subgraphs in an input graph, for any constant k. This problem (denoted SUB-CNT_k) has been studied extensively in both theory and practice. In a classic result, Chiba and Nishizeki (SICOMP 85) gave linear time algorithms for clique and 4-cycle counting for bounded degeneracy graphs. This is a rich class of sparse graphs that contains, for example, all minor-free families and preferential attachment graphs. The techniques from this result have inspired a number of recent practical algorithms for SUB-CNT_k. Towards a better understanding of the limits of these techniques, we ask: for what values of k can SUB_CNT_k be solved in linear time? We discover a chasm at k=6. Specifically, we prove that for k < 6, SUB_CNT_k can be solved in linear time. Assuming a standard conjecture in fine-grained complexity, we prove that for all k ⩾ 6, SUB-CNT_k cannot be solved even in near-linear time.
Cite as

Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri. Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bera_et_al:LIPIcs.ITCS.2020.38,
  author =	{Bera, Suman K. and Pashanasangi, Noujan and Seshadhri, C.},
  title =	{{Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.38},
  URN =		{urn:nbn:de:0030-drops-117239},
  doi =		{10.4230/LIPIcs.ITCS.2020.38},
  annote =	{Keywords: Subgraph counting, bounded degeneracy graphs, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.11
Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams

Authors: Suman K. Bera and Amit Chakrabarti

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We revisit the much-studied problem of space-efficiently estimating the number of triangles in a graph stream, and extensions of this problem to counting fixed-sized cliques and cycles. For the important special case of counting triangles, we give a 4-pass, (1 +/- epsilon)-approximate, randomized algorithm using O-tilde(epsilon^(-2) m^(3/2) / T) space, where m is the number of edges and T is a promised lower bound on the number of triangles. This matches the space bound of a recent algorithm (McGregor et al., PODS 2016), with an arguably simpler and more general technique. We give an improved multi-pass lower bound of Omega(min{m^(3/2)/T , m/sqrt(T)}), applicable at essentially all densities Omega(n) <= m <= O(n^2). We prove other multi-pass lower bounds in terms of various structural parameters of the input graph. Together, our results resolve a couple of open questions raised in recent work (Braverman et al., ICALP 2013). Our presentation emphasizes more general frameworks, for both upper and lower bounds. We give a sampling algorithm for counting arbitrary subgraphs and then improve it via combinatorial means in the special cases of counting odd cliques and odd cycles. Our results show that these problems are considerably easier in the cash-register streaming model than in the turnstile model, where previous work had focused. We use Turán graphs and related gadgets to derive lower bounds for counting cliques and cycles, with triangle-counting lower bounds following as a corollary.
Cite as

Suman K. Bera and Amit Chakrabarti. Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bera_et_al:LIPIcs.STACS.2017.11,
  author =	{Bera, Suman K. and Chakrabarti, Amit},
  title =	{{Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.11},
  URN =		{urn:nbn:de:0030-drops-70222},
  doi =		{10.4230/LIPIcs.STACS.2017.11},
  annote =	{Keywords: data streaming, graph algorithms, triangles, subgraph counting, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2015.183
A Depth-Five Lower Bound for Iterated Matrix Multiplication

Authors: Suman K. Bera and Amit Chakrabarti

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)

Abstract
We prove that certain instances of the iterated matrix multiplication (IMM) family of polynomials with N variables and degree n require N^(Omega(sqrt(n))) gates when expressed as a homogeneous depth-five Sigma Pi Sigma Pi Sigma arithmetic circuit with the bottom fan-in bounded by N^(1/2-epsilon). By a depth-reduction result of Tavenas, this size lower bound is optimal and can be achieved by the weaker class of homogeneous depth-four Sigma Pi Sigma Pi circuits. Our result extends a recent result of Kumar and Saraf, who gave the same N^(Omega(sqrt(n))) lower bound for homogeneous depth-four Sigma Pi Sigma Pi circuits computing IMM. It is analogous to a recent result of Kayal and Saha, who gave the same lower bound for homogeneous Sigma Pi Sigma Pi Sigma circuits (over characteristic zero) with bottom fan-in at most N^(1-epsilon), for the harder problem of computing certain polynomials defined by Nisan-Wigderson designs.
Cite as

Suman K. Bera and Amit Chakrabarti. A Depth-Five Lower Bound for Iterated Matrix Multiplication. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 183-197, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bera_et_al:LIPIcs.CCC.2015.183,
  author =	{Bera, Suman K. and Chakrabarti, Amit},
  title =	{{A Depth-Five Lower Bound for Iterated Matrix Multiplication}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{183--197},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.183},
  URN =		{urn:nbn:de:0030-drops-50622},
  doi =		{10.4230/LIPIcs.CCC.2015.183},
  annote =	{Keywords: arithmetic circuits, iterated matrix multiplication, depth five circuits, lower bound}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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