Research

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

You can find an informal summary on a selection of 5 of my papers ==>HERE<==.

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 Preprint)

Conference

  • Clementi, Andrea; Gualà, Luciano; Pasquale, Francesco; Scornavacca, Giacomo; Natale, Emanuele; Ghaffari, Mohsen. A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors. To appear in MFCS 2018 (ArXiv Preprint)
  • Becchetti, Luca; Clementi, Andrea; Manurangsi, Pasin; Natale, Emanuele; Pasquale, Francesco; Raghavendra, Prasad; Trevisan, Luca. Average whenever you meet: Opportunistic protocols for community detection. To appear in ESA 2018 (ArXiv Preprint)
  • Cruciani, Emilio; Natale, Emanuele; Nusser, André; Scornavacca, Giacomo. Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks - AAMAS 2018. (Published version, ArXiv preprint)
  • Becchetti, Luca; Bonifaci, Vincenzo; Natale, Emanuele. Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation - AAMAS 2018. (Published version, ArXiv preprint)
  • Boczkowski, Lucas; Feinerman, Ofer; Korman, Amos; Natale, Emanuele. Limits for Rumor Spreading in stochastic populations - ITCS 2018. (Published version, ArXiv preprint 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 and ArXiv preprint)
  • 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 preprint)
  • Boczkowski, Lucas; Korman, Amos; Natale, Emanuele. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits - SODA 2017. Brief announcement version presented at PODC 2016. (Published version and ArXiv preprint)
  • Borassi, Michele; Natale, Emanuele. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation - ESA 2016. (Published version and ArXiv preprint)
  • Kaaser, Dominik; Mallmann-Trenn, Frederik; Natale, Emanuele. On the Voting Time of the Deterministic Majority Process - MFCS 2016. Brief announcement version presented at DISC 2015. (Published version and ArXiv preprint)
  • Fraigniaud, Pierre; Natale, Emanuele. Noisy Information Spreading and Plurality Consensus - PODC 2016. (Published version and ArXiv preprint)
  • Gualà, Luciano; Leucci, Stefano; Natale, Emanuele; Tauraso, Roberto. Large Peg-Army Maneuvers - FUN 2016. (Published version and ArXiv preprint)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Trevisan, Luca. Stabilizing Consensus with Many Opinions - SODA 2016. (Published version and ArXiv preprint)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Posta, Gustavo. Self-Stabilizing Repeated Balls-into-Bins - SPAA 2015. (Published version and ArXiv preprint)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo. Plurality Consensus in the Gossip Model - SODA 2015. (Published version and ArXiv preprint)
  • Gualà, Luciano; Leucci, Stefano; Natale, Emanuele. Bejeweled, Candy Crush and other Match-Three Games are (NP-) Hard - CIG 2014. (Published version and ArXiv preprint)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo; Trevisan, Luca. Simple dynamics for plurality consensus - SPAA 2014. (Published version and ArXiv preprint)
  • Clementi, Andrea; Di Ianni, Miriam; Gambosi, Giorgio; Natale, Emanuele; Silvestri, Riccardo. Distributed community detection in dynamic graphs - SIROCCO 2013. (Published version and ArXiv preprint)

Journal

  • Borassi, Michele; Natale, Emanuele. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation - To appear in Journal of Experimental Algorithmics. Extended abstract in ESA 2016.
  • 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. Extended abstract in ITCS 2018. (Link to journal version)
  • Fraigniaud, Pierre; Natale, Emanuele. Noisy Information Spreading and Plurality Consensus - Distributed Computing 2018. Extended abstract in PODC 2016. (Link to journal version)
  • Boczkowski, Lucas; Korman, Amos; Natale, Emanuele. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits - Distributed Computing 2018, Springer. Extended abstract in SODA 2017. Brief announcement in PODC 2016. (Link to journal version)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Posta, Gustavo. Self-Stabilizing Repeated Balls-into-Bins - Distributed Computing 2017, Springer. Extended abstract in SPAA 2015. (Link to journal version)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo; Trevisan, Luca. Simple dynamics for plurality consensus - Distributed Computing 2017, Springer. Extended abstract in SPAA 2014. (Link to journal version)
  • Clementi, Andrea; Di Ianni, Miriam; Gambosi, Giorgio; Natale, Emanuele; Silvestri, Riccardo. Distributed Community Detection in Dynamic Graphs - Theoretical Computer Science 2015, Springer. Extended abstract in SIROCCO 2013. (Link to journal version)

Thematic Publication List

Dynamics

  • Clementi, Andrea; Gualà, Luciano; Pasquale, Francesco; Scornavacca, Giacomo; Natale, Emanuele; Ghaffari, Mohsen. A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors. To appear in MFCS 2018 (ArXiv Preprint)
  • Becchetti, Luca; Clementi, Andrea; Manurangsi, Pasin; Natale, Emanuele; Pasquale, Francesco; Raghavendra, Prasad; Trevisan, Luca. Average whenever you meet: Opportunistic protocols for community detection. To appear in ESA 2018 (ArXiv Preprint)
  • 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 Preprint)
  • 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 preprint)
  • 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 preprint)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Trevisan, Luca. Stabilizing Consensus with Many Opinions - SODA 2016. (Published version and ArXiv preprint)
  • Kaaser, Dominik; Mallmann-Trenn, Frederik; Natale, Emanuele. On the Voting Time of the Deterministic Majority Process - MFCS 2016. Brief announcement version presented at DISC 2015. (Published version and ArXiv preprint)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo. Plurality Consensus in the Gossip Model - SODA 2015. (Published version and ArXiv preprint)
  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo; Trevisan, Luca. Simple dynamics for plurality consensus - SPAA 2014 (Published version and ArXiv preprint), 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 preprint)
  • Boczkowski, Lucas; Feinerman, Ofer; Korman, Amos; Natale, Emanuele. Limits on reliable information flows through stochastic populations - PLOS Computational Biology 2018. Extended abstract in ITCS 2018. (Link to journal version, ArXiv preprint and Talk by Lucas)
  • Boczkowski, Lucas; Korman, Amos; Natale, Emanuele. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits - Distributed Computing 2018, Springer. Extended abstract in SODA 2017. Brief announcement in PODC 2016. (Published version and ArXiv preprint)
  • Fraigniaud, Pierre; Natale, Emanuele. Noisy Information Spreading and Plurality Consensus - Distributed Computing 2018. Extended abstract in PODC 2016. (Link to journal version and ArXiv preprint)

Algorithms Engineering

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

Distributed Algorithms

  • Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Posta, Gustavo. Self-Stabilizing Repeated Balls-into-Bins - Conference version in SPAA 2015 (Published version and ArXiv preprint), journal version in Distributed Computing 2017, Springer. (Published version).
  • Clementi, Andrea; Di Ianni, Miriam; Gambosi, Giorgio; Natale, Emanuele; Silvestri, Riccardo. Distributed community detection in dynamic graphs - SIROCCO 2013. (Published version and ArXiv preprint), journal version in Theoretical Computer Science 2015, Springer. (Published version).

Combinatorial Games

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