Publications HAL

2022

Journal articles

ref_biblio
Francesco d'Amore, Andrea Clementi, Emanuele Natale. Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions. Swarm Intelligence, 2022, ⟨10.1007/s11721-022-00217-w⟩. ⟨hal-02487650v3⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02487650/file/undecided-dynamics.pdf BibTex

Conference papers

ref_biblio
Arthur da Cunha, Emanuele Natale, Laurent Viennot. Proving the Strong Lottery Ticket Hypothesis for Convolutional Neural Networks. ICLR 2022 - 10th International Conference on Learning Representations, Apr 2022, Virtual, France. ⟨hal-03548226⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03548226/file/SLTHforCNNs.pdf BibTex
ref_biblio
Francesco d'Amore, Daniel Mitropolsky, Pierluigi Crescenzi, Emanuele Natale, Christos Papadimitriou. Planning with Biological Neurons and Synapses. Proceedings of the AAAI Conference on Artificial Intelligence 2022, Feb 2022, Vancouver, Canada. ⟨10.1609/aaai.v36i1.19875⟩. ⟨hal-03479582v2⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03479582/file/Planning_in_AC.pdf BibTex

Poster communications

ref_biblio
Aurora Rossi, Pierluigi Crescenzi, Samuel Deslauriers-Gauthier, Emanuele Natale. Hyperbolic Model Captures Temporal Small Worldness of Brain Dynamics. NeuroMod meeting 2022, Jun 2022, Antibes, France. ⟨hal-03685173⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03685173/file/NeuroMod_poster.pdf BibTex
ref_biblio
Francesco d'Amore, Daniel Mitropolsky, Pierluigi Crescenzi, Emanuele Natale, Christos H Papadimitriou. Planning with Biological Neurons and Synapses - AAAI22 Poster. AAAI 2022 - 36th AAAI Conference on Artificial Intelligence, Feb 2022, Vancouver, Canada. ⟨hal-03596672⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03596672/file/assembly_aaai22_poster1_boxes.pdf BibTex

Preprints, Working Papers, ...

ref_biblio
Luca Becchetti, Arthur Carvalho Walraven da Cunha, Andrea Clementi, Francesco d'Amore, Hicham Lesfari, et al.. On the Multidimensional Random Subset Sum Problem. {date}. ⟨hal-03738204v3⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03738204/file/multidim-rssp.pdf BibTex
ref_biblio
Arthur da Cunha, Francesco d'Amore, Frédéric Giroire, Hicham Lesfari, Emanuele Natale, et al.. Revisiting the Random Subset Sum problem. {date}. ⟨hal-03654720⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03654720/file/RandomSubsetSum.pdf BibTex

2021

Journal articles

ref_biblio
Andrea Clementi, Emanuele Natale, Isabella Ziccardi. Parallel Load Balancing on constrained client-server topologies. Theoretical Computer Science, 2021, 895, pp.16-33. ⟨10.1016/j.tcs.2021.09.026⟩. ⟨hal-03548136⟩
Accès au bibtex
https://arxiv.org/pdf/2005.13583 BibTex
ref_biblio
Emilio Cruciani, Emanuele Natale, André Nusser, Giacomo Scornavacca. Phase transition of the 2-Choices dynamics on core–periphery networks. Distributed Computing, Springer Verlag, 2021, 34 (3), pp.207-225. ⟨10.1007/s00446-021-00396-5⟩. ⟨hal-03548134⟩
Accès au bibtex
https://arxiv.org/pdf/1804.07223 BibTex
ref_biblio
Matteo Frigo, Emilio Cruciani, David Coudert, Rachid Deriche, Samuel Deslauriers-Gauthier, et al.. Network alignment and similarity reveal atlas-based topological differences in structural connectomes. Network Neuroscience, MIT Press, 2021, ⟨10.1162/netn_a_00199⟩. ⟨hal-03033777v2⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03033777/file/netn-manuscript.pdf BibTex

Conference papers

ref_biblio
Andrea Clementi, Francesco d'Amore, George Giakkoupis, Emanuele Natale. Search via Parallel Lévy Walks on ${\mathbb Z}^2$. PODC 2021 - ACM Symposium on Principles of Distributed Computing, Jul 2021, Salerno, Italy. pp.81-91, ⟨10.1145/3465084.3467921⟩. ⟨hal-02530253v5⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02530253/file/levy.pdf BibTex

Special issue

ref_biblio
David Coudert, Emanuele Natale. 19th International Symposium on Experimental Algorithms (SEA 2021). David Coudert; Emanuele Natale. 19th International Symposium on Experimental Algorithms (SEA 2021), Jun 2021, Nice, France. Leibniz International Proceedings in Informatics , 190, Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, pp.434, 2021, 978-3-95977-185-6. ⟨10.4230/LIPIcs.SEA.2021⟩. ⟨hal-03250984⟩
Accès au bibtex
BibTex

Poster communications

ref_biblio
Emilio Cruciani, Francesco d'Amore, Emanuele Natale. On some Opinion Dynamics in Multi-Agent Systems. MOMI2021: Le Monde des Mathematiques Industrielles, Mar 2021, Sophia-Antipolis, France. ⟨hal-03483921⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03483921/file/poster_momi.pdf BibTex

Reports

ref_biblio
Arthur da Cunha, Emanuele Natale, Laurent Viennot. Neural Network Information Leakage through Hidden Learning. [Research Report] Inria; CNRS; I3S; Université Côte d'Azur. 2021. ⟨hal-03157141⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03157141/file/hidden_learning.pdf BibTex

2020

Journal articles

ref_biblio
Luca Becchetti, Andrea Clementi, Emanuele Natale. Consensus Dynamics: An Overview. ACM SIGACT News, 2020, 51 (1), pp.57. ⟨10.1145/3388392.3388402⟩. ⟨hal-02507613⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02507613/file/preprint_Dynamics_Survey.pdf BibTex
ref_biblio
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan. Find Your Place: Simple Distributed Algorithms for Community Detection. SIAM Journal on Computing, 2020, 49 (4), pp.821-864. ⟨10.1137/19M1243026⟩. ⟨hal-03025943⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-03025943/file/find_your_place_preprint.pdf BibTex

Conference papers

ref_biblio
Andrea Clementi, Emanuele Natale, Isabella Ziccardi. Parallel Load Balancing on Constrained Client-Server Topologies. SPAA 2020 - 32nd ACM Symposium on Parallelism in Algorithms and Architectures Proceedings, Jul 2020, Philadelphia, United States. ⟨10.1145/3350755.3400232⟩. ⟨hal-02648649⟩
Accès au bibtex
https://arxiv.org/pdf/2005.13583 BibTex
ref_biblio
Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, et al.. Consensus vs Broadcast, with and without Noise. ITCS 2020 - 11th Annual Innovations in Theoretical Computer Science, Jan 2020, Seattle, United States. pp.42 - 43, ⟨10.4230/LIPIcs.ITCS.2020.42⟩. ⟨hal-01958994v2⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01958994/file/ITCS20__Final_Version_.pdf BibTex
ref_biblio
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan. Finding a Bounded-Degree Expander Inside a Dense One. SODA 2020 - ACM SIAM Symposium on Discrete Algorithms, Jan 2020, Salt Lake City, United States. ⟨10.1137/1.9781611975994.80⟩. ⟨hal-02002377v2⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02002377/file/Finding_a_Bounded_Degree_Expander_Inside_a_Dense_One.pdf BibTex

2019

Journal articles

ref_biblio
Lucas Boczkowski, Amos Korman, Emanuele Natale. Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits. Distributed Computing, Springer Verlag, In press, ⟨10.1007/s00446-018-0330-x⟩. ⟨hal-01965945⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01965945/file/dc.pdf BibTex
ref_biblio
Michele Borassi, Emanuele Natale. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. ACM Journal of Experimental Algorithmics, Association for Computing Machinery, 2019, 24 (1), ⟨10.1145/3284359⟩. ⟨hal-02043367⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02043367/file/kadabra_1604.08553.pdf BibTex
ref_biblio
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Gustavo Posta. Self-stabilizing repeated balls-into-bins. Distributed Computing, Springer Verlag, 2019, 32 (1), pp.59-68. ⟨10.1007/s00446-017-0320-4⟩. ⟨hal-02948569⟩
Accès au bibtex
https://arxiv.org/pdf/1501.04822 BibTex
ref_biblio
Pierre Fraigniaud, Emanuele Natale. Noisy rumor spreading and plurality consensus. Distributed Computing, Springer Verlag, 2019, 32 (4), pp.257-276. ⟨10.1007/s00446-018-0335-5⟩. ⟨hal-02001830⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02001830/file/Noisy_Plurality_Consensus.pdf BibTex

Conference papers

ref_biblio
Emanuele Natale, Iliad Ramezani. On the Necessary Memory to Compute the Plurality in Multi-Agent Systems. CIAC 2019 - 11th International Conference Algorithms and Complexity, May 2019, Rome, Italy. pp.323-338, ⟨10.1007/978-3-030-17402-6_27⟩. ⟨hal-02002448⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02002448/file/ciac_1901.06549.pdf BibTex
ref_biblio
Emilio Cruciani, Emanuele Natale, Giacomo Scornavacca. Distributed Community Detection via Metastability of the 2-Choices Dynamics. AAAI 2019 - 33th AAAI Conference Association for the Advancement of Artificial Intelligence, Jan 2019, Honolulu, United States. pp.6046-6053, ⟨10.1609/aaai.v33i01.33016046⟩. ⟨hal-02002462⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02002462/file/2_Choices_Metastability___AAAI19___HAL_version.pdf BibTex

Reports

ref_biblio
Hossein Baktash, Emanuele Natale, Laurent Viennot. A Comparative Study of Neural Network Compression. [Research Report] INRIA Sophia Antipolis - I3S. 2019. ⟨hal-02321581⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02321581/file/A_Comparative_Study_of_Neural_Network_Compression.pdf BibTex

2018

Journal articles

ref_biblio
Lucas Boczkowski, Emanuele Natale, Ofer Feinerman, Amos Korman. Limits on reliable information flows through stochastic populations. PLoS Computational Biology, Public Library of Science, 2018, 14 (6), ⟨10.1371/journal.pcbi.1006195⟩. ⟨hal-01953778v2⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01953778/file/limits.pdf BibTex

Conference papers

ref_biblio
Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, et al.. A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Aug 2018, Liverpool, United Kingdom. ⟨10.4230/LIPIcs.MFCS.2018.28⟩. ⟨hal-02002476⟩
Accès au bibtex
https://arxiv.org/pdf/1707.05135 BibTex
ref_biblio
Luca Becchetti, Vincenzo Bonifaci, Emanuele Natale. Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS '18), Jul 2018, Stockholm, Sweden. ⟨10.5555/3237383.3237935⟩. ⟨hal-02002536⟩
Accès au bibtex
https://arxiv.org/pdf/1804.06127 BibTex
ref_biblio
Emilio Cruciani, Emanuele Natale, André Nusser, Giacomo Scornavacca. Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks. 17th International Conference on Autonomous Agents and MultiAgent Systems, Jul 2018, Stockholm, Sweden. ⟨10.5555/3237383.3237499⟩. ⟨hal-02002658⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02002658/file/EATCS18-542-2135-1-PB.pdf BibTex
ref_biblio
Lucas Boczkowski, Ofer Feinerman, Amos Korman, Emanuele Natale. Limits for Rumor Spreading in Stochastic Populations. ITCS 2018 - 9th Innovations in Theoretical Computer Science Conference, Jan 2018, Cambridge, United States. pp.1-27. ⟨hal-01958152⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01958152/file/itcs18_noisypull.pdf BibTex
ref_biblio
Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, et al.. Average Whenever You Meet: Opportunistic Protocols for Community Detection. 26th Annual European Symposium on Algorithms (ESA 2018), 2018, Helsinki, Finland. pp.1 - 7, ⟨10.4230/LIPIcs.ESA.2018.7⟩. ⟨hal-02002513⟩
Accès au bibtex
https://arxiv.org/pdf/1703.05045 BibTex

Other publications

ref_biblio
Lucas Boczkowski, Emanuele Natale, Ofer Feinerman, Amos Korman. Supplementary Information for "Limits on Reliable Information Flows through Stochastic Populations". 2018. ⟨hal-01848636v2⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01848636/file/S1_Text_hal.pdf BibTex

2017

Journal articles

ref_biblio
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, et al.. Simple dynamics for plurality consensus. Distributed Computing, 2017, 30 (4), pp.293-306. ⟨10.1007/s00446-016-0289-4⟩. ⟨hal-02002637⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02002637/file/draft-dc-3maj.pdf BibTex

Conference papers

ref_biblio
Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, et al.. Ignore or Comply? On Breaking Symmetry in Consensus. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC '17), Jul 2017, Washington, United States. pp.335-344, ⟨10.1145/3087801.3087817⟩. ⟨hal-02002544⟩
Accès au bibtex
https://arxiv.org/pdf/1702.04921 BibTex
ref_biblio
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan. Find Your Place: Simple Distributed Algorithms for Community Detection. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), Jan 2017, Barcelona, Spain. pp.940-959, ⟨10.1137/1.9781611974782.59⟩. ⟨hal-02002592⟩
Accès au bibtex
https://arxiv.org/pdf/1511.03927 BibTex
ref_biblio
Lucas Boczkowski, Amos Korman, Emanuele Natale. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits. ACM-SIAM Symposium on Discrete Algorithms (SODA17), Jan 2017, Barcelona, Spain. ⟨hal-01447435⟩
Accès au bibtex
https://arxiv.org/pdf/1602.04419 BibTex

Theses

ref_biblio
Emanuele Natale. On the Computational Power of Simple Dynamics. Distributed, Parallel, and Cluster Computing [cs.DC]. Sapienza University of Rome, 2017. English. ⟨NNT : ⟩. ⟨tel-02002681⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/tel-02002681/file/phd_thesis.pdf BibTex

2016

Conference papers

ref_biblio
Michele Borassi, Emanuele Natale. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. 24th Annual European Symposium on Algorithms (ESA 2016), Aug 2016, Aarhus, Denmark. ⟨10.4230/LIPIcs.ESA.2016.20⟩. ⟨hal-02002600⟩
Accès au bibtex
https://arxiv.org/pdf/1604.08553 BibTex
ref_biblio
Dominik Kaaser, Frederik Mallmann-Trenn, Emanuele Natale. On the Voting Time of the Deterministic Majority Process. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Aug 2016, Krakow, Poland. ⟨10.4230/LIPIcs.MFCS.2016.55⟩. ⟨hal-02001816⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02001816/file/LIPIcs-MFCS-2016-55.pdf BibTex
ref_biblio
Lucas Boczkowski, Amos Korman, Emanuele Natale. Brief Announcement: Self-stabilizing Clock Synchronization with 3-bit Messages. Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC'16), Jul 2016, Chicago, United States. pp.207-209, ⟨10.1145/2933057.2933075⟩. ⟨hal-02001859⟩
Accès au bibtex
BibTex
ref_biblio
Luciano Gualà, Stefano Leucci, Emanuele Natale, Roberto Tauraso. Large Peg-Army Maneuvers. 8th International Conference on Fun with Algorithms (FUN 2016), Jun 2016, La Maddalena, Maddalena Islands, Italy. ⟨10.4230/LIPIcs.FUN.2016.18⟩. ⟨hal-02002603⟩
Accès au bibtex
https://arxiv.org/pdf/1603.00898 BibTex
ref_biblio
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan. Stabilizing Consensus with Many Opinions. Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA'16), Jan 2016, Arlington, Virginia, United States. ⟨hal-02002615⟩
Accès au bibtex
https://arxiv.org/pdf/1508.06782 BibTex
ref_biblio
Pierre Fraigniaud, Emanuele Natale. Noisy Rumor Spreading and Plurality Consensus. ACM Symposium on Principles of Distributed Computing (PODC), 2016, Chicago, United States. ⟨10.1145/2933057.2933089⟩. ⟨hal-01423686⟩
Accès au bibtex
https://arxiv.org/pdf/1507.05796 BibTex

2015

Journal articles

ref_biblio
Andrea Clementi, Miriam Di Ianni, Giorgio Gambosi, Emanuele Natale, Riccardo Silvestri. Distributed community detection in dynamic graphs. Theoretical Computer Science, 2015, 584, pp.19-41. ⟨hal-02002691⟩
Accès au bibtex
BibTex

Conference papers

ref_biblio
Dominik Kaaser, Frederik Mallmann-Trenn, Emanuele Natale. Brief Announcement: On the Voting Time of the Deterministic Majority Process. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨hal-01207836⟩
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-01207836/file/13-BA.pdf BibTex
ref_biblio
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Gustavo Posta. Self-Stabilizing Repeated Balls-into-Bins. Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA '15), Jun 2015, Portland, United States. pp.332-339, ⟨10.1145/2755573.2755584⟩. ⟨hal-02002632⟩
Accès au bibtex
https://arxiv.org/pdf/1501.04822 BibTex
ref_biblio
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri. Plurality Consensus in the Gossip Model. Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms (SODA '15), Jan 2015, San Diego, California, United States. ⟨10.1137/1.9781611973730.27⟩. ⟨hal-02002629⟩
Accès au bibtex
https://arxiv.org/pdf/1407.2565 BibTex

2014

Conference papers

ref_biblio
Luciano Gualà, Stefano Leucci, Emanuele Natale. Bejeweled, Candy Crush and other match-three games are (NP-)hard. 2014 IEEE Conference on Computational Intelligence and Games (CIG), Aug 2014, Dortmund, France. pp.1-8. ⟨hal-02002623⟩
Accès au bibtex
https://arxiv.org/pdf/1403.5830 BibTex
ref_biblio
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, et al.. Simple dynamics for plurality consensus. Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (SPAA '14), Jun 2014, Prague, Czech Republic. pp.247-256, ⟨10.1145/2612669.2612677⟩. ⟨hal-02002640⟩
Accès au bibtex
https://arxiv.org/pdf/1310.2858v1 BibTex

2013

Conference papers

ref_biblio
Andrea Clementi, Miriam Di Ianni, Giorgio Gambosi, Emanuele Natale, Riccardo Silvestri. Distributed Community Detection in Dynamic Graphs. International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013), Jul 2013, Ischia, Italy. pp 1-12, ⟨10.1007/978-3-319-03578-9_29⟩. ⟨hal-02002648⟩
Accès au bibtex
https://arxiv.org/pdf/1302.5607 BibTex