Research

All my papers are on HAL.

As customary in the field of theoretical computer science, in all publications below authors are listed alphabetically.

Here is my PhD thesis. You can find an informal summary on a selection of 5 of my papers here (2017). For a more technical summary of some work I did during my PhD, you may have a look at an older description of some results on self-stabilizing broadcast and clock synchronization in the pull model, some results on performing clustering via a very simple rule, some results on plurality consensus.

Chronological Publication List

Work in Progress

  • Clementi, Andrea; Gualà, Luciano; Natale, Emanuele; Pasquale, Francesco; Scornavacca, Giacomo; Trevisan, Luca. Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise. (ArXiv, HAL)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Trevisan, Luca. Finding a Bounded-Degree Expander Inside a Dense One (ArXiv, HAL).

Conference

  • Natale, Emanuele; Ramezani, Iliad. On the Necessary Memory to Compute the Plurality in Multi-Agent Systems - CIAC 2019 (Published version, ArXiv, HAL).
  • Cruciani, Emilio; Natale, Emanuele; Scornavacca, Giacomo. Distributed Community Detection via Metastability of the 2-Choices Dynamics - AAAI 2019 (ArXiv, HAL, Poster courtesy of Emilio Cruciani).
  • Clementi, Andrea; Gualà, Luciano; Pasquale, Francesco; Scornavacca, Giacomo; Natale, Emanuele; Ghaffari, Mohsen. A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors - MFCS 2018 (Published version, ArXiv, HAL)
  • Becchetti, Luca; Clementi, Andrea; Manurangsi, Pasin; Natale, Emanuele; Pasquale, Francesco; Raghavendra, Prasad; Trevisan, Luca. Average whenever you meet: Opportunistic protocols for community detection - ESA 2018 (Published version, ArXiv, HAL)
  • Cruciani, Emilio; Natale, Emanuele; Nusser, André; Scornavacca, Giacomo. Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks - AAMAS 2018. (Published version, ArXiv, HAL)
  • Becchetti, Luca; Bonifaci, Vincenzo; Natale, Emanuele. Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation - AAMAS 2018. (Published version, ArXiv, HAL)
  • Boczkowski, Lucas; Feinerman, Ofer; Korman, Amos; Natale, Emanuele. Limits for Rumor Spreading in stochastic populations - ITCS 2018. (Published version, ArXiv, HAL and Talk by Lucas)
  • Berenbrink, Petra; Clementi, Andrea; Elsässer, Robert; Kling, Peter; Mallmann-Trenn, Frederik; Natale, Emanuele. Ignore or Comply? On Breaking Symmetry in Consensus - PODC 2017. (Published version, ArXiv, HAL)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Trevisan, Luca. Find Your Place: Simple Distributed Algorithms for Community Detection - SODA 2017. (Published version, ArXiv, HAL)
  • Boczkowski, Lucas; Korman, Amos; Natale, Emanuele. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits - SODA 2017 (Published version, ArXiv, HAL). Brief announcement version presented at PODC 2016 (HAL).
  • Borassi, Michele; Natale, Emanuele. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation - ESA 2016. (Published version and ArXiv, HAL)
  • Kaaser, Dominik; Mallmann-Trenn, Frederik; Natale, Emanuele. On the Voting Time of the Deterministic Majority Process - MFCS 2016 (Published version, ArXiv, HAL). Brief announcement version presented at DISC 2015 (HAL).
  • Fraigniaud, Pierre; Natale, Emanuele. Noisy Information Spreading and Plurality Consensus - PODC 2016. (Published version, ArXiv, HAL)
  • Gualà, Luciano; Leucci, Stefano; Natale, Emanuele; Tauraso, Roberto. Large Peg-Army Maneuvers - FUN 2016. (Published version, ArXiv, HAL)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Trevisan, Luca. Stabilizing Consensus with Many Opinions - SODA 2016. (Published version, ArXiv, HAL)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Posta, Gustavo. Self-Stabilizing Repeated Balls-into-Bins - SPAA 2015. (Published version, ArXiv, HAL)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo. Plurality Consensus in the Gossip Model - SODA 2015. (Published version, ArXiv, HAL)
  • Gualà, Luciano; Leucci, Stefano; Natale, Emanuele. Bejeweled, Candy Crush and other Match-Three Games are (NP-) Hard - CIG 2014. (Published version, ArXiv, HAL)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo; Trevisan, Luca. Simple dynamics for plurality consensus - SPAA 2014. (Published version, ArXiv, HAL)
  • Clementi, Andrea; Di Ianni, Miriam; Gambosi, Giorgio; Natale, Emanuele; Silvestri, Riccardo. Distributed community detection in dynamic graphs - SIROCCO 2013. (Published version, ArXiv, HAL)

Journal

  • Cruciani, Emilio; Natale, Emanuele; Nusser, André; Scornavacca, Giacomo. Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks - Bulletin of the EATCS 2018 (Link to journal version, HAL). Brief announcement of the version appeared in AAMAS 2018 (HAL).
  • Cruciani, Emilio; Natale, Emanuele; Scornavacca, Giacomo. On the Metastability of Quadratic Majority Dynamics on Clustered Graphs and its Biological Implications - Bulletin of the EATCS 2018. (Link to journal version)
  • Borassi, Michele; Natale, Emanuele. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation - Journal of Experimental Algorithmics (Link to journal version, HAL). Extended abstract in ESA 2016 (HAL).
  • Natale, Emanuele. On the Computational Power of Simple Dynamics - Bulletin of the EATCS 2018. (Link to journal version)
  • Boczkowski, Lucas; Feinerman, Ofer; Korman, Amos; Natale, Emanuele. Limits on reliable information flows through stochastic populations - PLOS Computational Biology 2018 (Link to journal version, HAL). Extended abstract in ITCS 2018 (HAL).
  • Fraigniaud, Pierre; Natale, Emanuele. Noisy Information Spreading and Plurality Consensus - Distributed Computing 2018 (Link to journal version, HAL). Extended abstract in PODC 2016 (HAL).
  • Boczkowski, Lucas; Korman, Amos; Natale, Emanuele. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits - Distributed Computing 2018, Springer (Link to journal version, HAL). Extended abstract in SODA 2017 (HAL). Brief announcement in PODC 2016 (HAL).
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Posta, Gustavo. Self-Stabilizing Repeated Balls-into-Bins - Distributed Computing 2017, Springer (Journal version, HAL). Extended abstract in SPAA 2015. (HAL)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo; Trevisan, Luca. Simple dynamics for plurality consensus - Distributed Computing 2017, Springer (Journal version, HAL). Extended abstract in SPAA 2014. (HAL)
  • Clementi, Andrea; Di Ianni, Miriam; Gambosi, Giorgio; Natale, Emanuele; Silvestri, Riccardo. Distributed Community Detection in Dynamic Graphs - Theoretical Computer Science 2015, Springer (Journal version, HAL). Extended abstract in SIROCCO 2013 (HAL).

Thematic Publication List

Distributed Algorithms

  • Natale, Emanuele; Ramezani, Iliad. On the Necessary Memory to Compute the Plurality in Multi-Agent Systems - To appear in CIAC 2018. (ArXiv, HAL).
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Posta, Gustavo. Self-Stabilizing Repeated Balls-into-Bins - Distributed Computing 2017, Springer. (Published version, HAL). Conference version in SPAA 2015 (HAL).
  • Kaaser, Dominik; Mallmann-Trenn, Frederik; Natale, Emanuele. On the Voting Time of the Deterministic Majority Process - MFCS 2016 (Published version and ArXiv). Brief announcement version presented at DISC 2015 (HAL).
  • Clementi, Andrea; Di Ianni, Miriam; Gambosi, Giorgio; Natale, Emanuele; Silvestri, Riccardo. Distributed community detection in dynamic graphs - SIROCCO 2013. (Published version, ArXiv, HAL), journal version in Theoretical Computer Science 2015, Springer. (Published version).

Dynamics

  • Cruciani, Emilio; Natale, Emanuele; Scornavacca, Giacomo. Distributed Community Detection via Metastability of the 2-Choices Dynamics - AAAI 2019 (ArXiv, HAL, Poster courtesy of Emilio Cruciani).
  • Clementi, Andrea; Gualà, Luciano; Pasquale, Francesco; Scornavacca, Giacomo; Natale, Emanuele; Ghaffari, Mohsen. A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors - MFCS 2018 (Published version, ArXiv, HAL)
  • Becchetti, Luca; Clementi, Andrea; Manurangsi, Pasin; Natale, Emanuele; Pasquale, Francesco; Raghavendra, Prasad; Trevisan, Luca. Average whenever you meet: Opportunistic protocols for community detection - ESA 2018 (Published version, ArXiv)
  • Natale, Emanuele. On the Computational Power of Simple Dynamics - Bulletin of the EATCS 2018. (Link to journal version)
  • Cruciani, Emilio; Natale, Emanuele; Nusser, André; Scornavacca, Giacomo. Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks - AAMAS 2018. (ArXiv)
  • Berenbrink, Petra; Clementi, Andrea; Elsässer, Robert; Kling, Peter; Mallmann-Trenn, Frederik; Natale, Emanuele. Ignore or Comply? On Breaking Symmetry in Consensus - PODC 2017. (Published version and ArXiv)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Trevisan, Luca. Find Your Place: Simple Distributed Algorithms for Community Detection - SODA 2017. (Published version and ArXiv)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Trevisan, Luca. Stabilizing Consensus with Many Opinions - SODA 2016. (Published version and ArXiv)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo. Plurality Consensus in the Gossip Model - SODA 2015. (Published version and ArXiv)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo; Trevisan, Luca. Simple dynamics for plurality consensus - SPAA 2014 (Published version, ArXiv, HAL), journal version in Distributed Computing 2017, Springer (Published version).

Natural Algorithms

  • Becchetti, Luca; Bonifaci, Vincenzo; Natale, Emanuele. Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation - AAMAS 2018. (ArXiv)
  • Boczkowski, Lucas; Feinerman, Ofer; Korman, Amos; Natale, Emanuele. Limits on reliable information flows through stochastic populations - PLOS Computational Biology 2018 (Link to journal version, ArXiv, HAL, Talk by Lucas). Extended abstract in ITCS 2018 (HAL).
  • Boczkowski, Lucas; Korman, Amos; Natale, Emanuele. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits - Distributed Computing 2018, Springer (Published version, ArXiv, HAL). Extended abstract in SODA 2017 (HAL). Brief announcement in PODC 2016 (HAL).
  • Fraigniaud, Pierre; Natale, Emanuele. Noisy Information Spreading and Plurality Consensus - Distributed Computing 2018 (Link to journal version, ArXiv, HAL). Extended abstract in PODC 2016 (HAL).

Algorithms Engineering

  • Borassi, Michele; Natale, Emanuele. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation - ESA 2016. (Published version, ArXiv, HAL)

Combinatorial Games

  • Gualà, Luciano; Leucci, Stefano; Natale, Emanuele; Tauraso, Roberto. Large Peg-Army Maneuvers - FUN 2016. (Published version and ArXiv)
  • Gualà, Luciano; Leucci, Stefano; Natale, Emanuele. Bejeweled, Candy Crush and other Match-Three Games are (NP-) Hard - CIG 2014. (Published version and ArXiv preprint)