2 Search Results for "Tetali, Prasad"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.78
Modularity and Graph Expansion

Authors: Baptiste Louf, Colin McDiarmid, and Fiona Skerman

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We relate two important notions in graph theory: expanders which are highly connected graphs, and modularity a parameter of a graph that is primarily used in community detection. More precisely, we show that a graph having modularity bounded below 1 is equivalent to it having a large subgraph which is an expander. We further show that a connected component H will be split in an optimal partition of the host graph G if and only if the relative size of H in G is greater than an expansion constant of H. This is a further exploration of the resolution limit known for modularity, and indeed recovers the bound that a connected component H in the host graph G will not be split if e(H) < √{2e(G)}.
Cite as

Baptiste Louf, Colin McDiarmid, and Fiona Skerman. Modularity and Graph Expansion. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 78:1-78:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{louf_et_al:LIPIcs.ITCS.2024.78,
  author =	{Louf, Baptiste and McDiarmid, Colin and Skerman, Fiona},
  title =	{{Modularity and Graph Expansion}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{78:1--78:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.78},
  URN =		{urn:nbn:de:0030-drops-196063},
  doi =		{10.4230/LIPIcs.ITCS.2024.78},
  annote =	{Keywords: edge expansion, modularity, community detection, resolution limit, conductance}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.16
Mutation, Sexual Reproduction and Survival in Dynamic Environments

Authors: Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
A new approach to understanding evolution [Valiant, JACM 2009], namely viewing it through the lens of computation, has already started yielding new insights, e.g., natural selection under sexual reproduction can be interpreted as the Multiplicative Weight Update (MWU) Algorithm in coordination games played among genes [Chastain, Livnat, Papadimitriou, Vazirani, PNAS 2014]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [Wolf, Vazirani, Arkin, J. Theor. Biology], we model changing environments via a Markov chain, with the states representing environments, each with its own fitness matrix. In this setting, we show that in the absence of mutation, the population goes extinct, but in the presence of mutation, the population survives with positive probability. On the way to proving the above theorem, we need to establish some facts about dynamics in games. We provide the first, to our knowledge, polynomial convergence bound for noisy MWU in a coordination game. Finally, we also show that in static environments, sexual evolution with mutation converges, for any level of mutation.
Cite as

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani. Mutation, Sexual Reproduction and Survival in Dynamic Environments. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 16:1-16:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mehta_et_al:LIPIcs.ITCS.2017.16,
  author =	{Mehta, Ruta and Panageas, Ioannis and Piliouras, Georgios and Tetali, Prasad and Vazirani, Vijay V.},
  title =	{{Mutation, Sexual Reproduction and Survival in Dynamic Environments}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{16:1--16:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.16},
  URN =		{urn:nbn:de:0030-drops-81655},
  doi =		{10.4230/LIPIcs.ITCS.2017.16},
  annote =	{Keywords: Evolution, Non-linear dynamics, Mutation}
}
  • Refine by Author
  • 1 Louf, Baptiste
  • 1 McDiarmid, Colin
  • 1 Mehta, Ruta
  • 1 Panageas, Ioannis
  • 1 Piliouras, Georgios
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Extremal graph theory
  • 1 Mathematics of computing → Spectra of graphs
  • 1 Theory of computation → Theory and algorithms for application domains

  • Refine by Keyword
  • 1 Evolution
  • 1 Mutation
  • 1 Non-linear dynamics
  • 1 community detection
  • 1 conductance
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2024

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