Andrea Clementi

Arthur Carvalho Walraven da Cunha

Swarm Intell., 2022

On the Multidimensional Random Subset Sum Problem.

[BibT_eX]

[DOI]

Luca Becchetti

CoRR, 2022

Percolation and Epidemic Processes in One-Dimensional Small-World Networks - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the LATIN 2022: Theoretical Informatics, 2022

2021

Parallel Load Balancing on constrained client-server topologies.

[BibT_eX]

[DOI]

Isabella Ziccardi

Theor. Comput. Sci., 2021

Sharp Thresholds for a SIR Model on One-Dimensional Small-World Networks.

[BibT_eX]

[DOI]

CoRR, 2021

Search via Parallel Lévy Walks on Z2.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

2020

Consensus Dynamics: An Overview.

[BibT_eX]

[DOI]

Luca Becchetti

SIGACT News, 2020

Find Your Place: Simple Distributed Algorithms for Community Detection.

[BibT_eX]

[DOI]

Luca Becchetti

SIAM J. Comput., 2020

Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions.

[BibT_eX]

[DOI]

Francesco D'Amore

CoRR, 2020

On the Search Efficiency of Parallel Lévy Walks on Z2.

[BibT_eX]

[DOI]

CoRR, 2020

Finding a Bounded-Degree Expander Inside a Dense One.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions - (Extended Abstract).

[BibT_eX]

[DOI]

Francesco D'Amore

Proceedings of the Structural Information and Communication Complexity, 2020

Consensus vs Broadcast, with and Without Noise (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Self-stabilizing repeated balls-into-bins.

[BibT_eX]

[DOI]

Distributed Comput., 2019

2018

Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise.

[BibT_eX]

[DOI]

CoRR, 2018

A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Average Whenever You Meet: Opportunistic Protocols for Community Detection.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Simple dynamics for plurality consensus.

[BibT_eX]

[DOI]

Distributed Comput., 2017

On the Parallel Undecided-State Dynamics with Two Colors.

[BibT_eX]

[DOI]

CoRR, 2017

Friend or Foe? Population Protocols can perform Community Detection.

[BibT_eX]

[DOI]

CoRR, 2017

Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Ignore or Comply?: On Breaking Symmetry in Consensus.

[BibT_eX]

[DOI]

Frederik Mallmann-Trenn

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Rational Fair Consensus in the Gossip Model.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium, 2017

2016

Rumor spreading in random evolving graphs.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

Stabilizing Consensus with Many Opinions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Distributed community detection in dynamic graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Parsimonious flooding in geometric random-walks.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

Information spreading in dynamic graphs.

[BibT_eX]

[DOI]

Distributed Comput., 2015

Probabilistic Self-Stabilization.

[BibT_eX]

[DOI]

CoRR, 2015

Plurality Consensus in the Gossip Model.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Flooding Time in Opportunistic Networks under Power Law and Exponential Intercontact Times.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 2014

2013

Opportunistic MANETs: Mobility Can Make Up for Low Transmission Power.

[BibT_eX]

[DOI]

IEEE/ACM Trans. Netw., 2013

Fast flooding over Manhattan.

[BibT_eX]

[DOI]

Distributed Comput., 2013

Simple Dynamics for Majority Consensus.

[BibT_eX]

[DOI]

CoRR, 2013

Distributed Community Detection in Dynamic Graphs - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2013

Rumor Spreading in Random Evolving Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2013, 2013

2012

Optimal gossiping in geometric radio networks in the presence of dynamical faults.

[BibT_eX]

[DOI]

Networks, 2012

2011

Information Spreading in Dynamic Networks: An Analytical Approach.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Aspects of Distributed Computing in Sensor Networks, 2011

Information Spreading in Stationary Markovian Evolving Graphs.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 2011

Maximizing the Number of Broadcast Operations in Random Geometric Ad Hoc Wireless Networks.

[BibT_eX]

[DOI]

Emanuele G. Fusco

IEEE Trans. Parallel Distributed Syst., 2011

Information Spreading in Opportunistic Networks is Fast

[BibT_eX]

[DOI]

CoRR, 2011

Modelling mobility: A discrete revolution.

[BibT_eX]

[DOI]

Ad Hoc Networks, 2011

Parsimonious Flooding in Geometric Random-Walks - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 25th International Symposium, 2011

2010

Flooding Time of Edge-Markovian Evolving Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2010

Modelling Mobility: A Discrete Revolution.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Broadcasting in dynamic radio networks.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2009

MANETS: High Mobility Can Make Up for Low Transmission Power.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

2008

Minimum-Energy Broadcast and disk cover in grid wireless networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

Flooding time in edge-Markovian dynamic graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

Minimum-energy broadcast in random-grid ad-hoc networks: approximation and distributed algorithms.

[BibT_eX]

[DOI]

Proceedings of the 11th International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems, 2008

2007

On the bounded-hop MST problem on random Euclidean instances.

[BibT_eX]

Theor. Comput. Sci., 2007

Communication in dynamic radio networks.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

Maximizing the Number of Broadcast Operations in Static Random Geometric Ad-Hoc Networks.

[BibT_eX]

[DOI]

Emanuele G. Fusco

Proceedings of the Principles of Distributed Systems, 11th International Conference, 2007

Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

2006

A Distributed Protocol for the Bounded-Hops Converge-Cast in Ad-Hoc Networks.

[BibT_eX]

[DOI]

Proceedings of the Ad-Hoc, Mobile, and Wireless Networks, 5th International Conference, 2006

2005

On the approximability of the range assignment problem on radio networks in presence of selfish agents.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Divide and Conquer Is Almost Optimal for the Bounded-Hop MST Problem on Random Euclidean Instances.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2005

Experimental Analysis of Practically Efficient Algorithms for Bounded-Hop Accumulation in Ad-Hoc Wireless Networks.

[BibT_eX]

[DOI]

Proceedings of the 19th International Parallel and Distributed Processing Symposium (IPDPS 2005), 2005

2004

On the Power Assignment Problem in Radio Networks.

[BibT_eX]

[DOI]

Mob. Networks Appl., 2004

Round Robin is optimal for fault-tolerant broadcasting on wireless networks.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2004

Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

The Range Assignment Problem in Non-Homogeneous Static Ad-Hoc Networks.

[BibT_eX]

[DOI]

Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), 2004

2003

Distributed broadcast in radio networks of unknown topology.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

The minimum broadcast range assignment problem on linear multi-hop wireless networks.

[BibT_eX]

[DOI]

Miriam Di Ianni

Theor. Comput. Sci., 2003

The Minimum Range Assignment Problem on Linear Radio Networks.

[BibT_eX]

[DOI]

Algorithmica, 2003

Energy Consumption in Radio Networks: Selfish Agents and Rewarding Mechanisms.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, First International Workshop, 2003

On the Approximation Ratio of the MST-Based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 2003

2002

Optimal F-Reliable Protocols for the Do-All Problem on Single-Hop Wireless Networks.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

2001

Distributed Broadcast in Wireless Networks with Unknown Topology

[BibT_eX]

[DOI]

CoRR, 2001

On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs.

[BibT_eX]

[DOI]

Proceedings of the STACS 2001, 2001

Selective families, superimposed codes, and broadcasting on unknown radio networks.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

On Computing Ad-hoc Selective Families.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

Distributed multi-broadcast in unknown radio networks.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

2000

Parallel Read Operations Without Memory Contention

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

The Power Range Assignment Problem in Radio Networks on the Plane.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

A Note on Parallel Read Operations on Large Public Databases.

[BibT_eX]

Gian Carlo Bongiovanni

Proceedings of the ICALP Workshops 2000, 2000

1999

Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1999

Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-offs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1999

Weak Random Sources, Hitting Sets, and BPP Simulations.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines.

[BibT_eX]

[DOI]

Proceedings of the STACS 99, 1999

Hardness Results for the Power Range Assignmet Problem in Packet Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the Randomization, 1999

Small Pseudo-Random Sets Yield Hard Functions: New Tight Explict Lower Bounds for Branching Programs.

[BibT_eX]

[DOI]

Juri L. Baskakov

Proceedings of the Automata, 1999

On the Complexity of Approximating Colored-Graph Problems.

[BibT_eX]

[DOI]

Pierluigi Crescenzi

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

The Parallel Complexity of Approximating the High Degree Subgraph Problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

A New General Derandomization Method.

[BibT_eX]

[DOI]

J. ACM, 1998

Recent Advances Towards Proving P = BPP.

[BibT_eX]

Bull. EATCS, 1998

1997

Optimal Bounds for the Approximation of Boolean Functions and Some Applications.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1997

Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs

[BibT_eX]

[DOI]

Juri L. Baskakov

Electron. Colloquium Comput. Complex., 1997

Efficient Construction of Hitting Sets for Systems of Linear Functions.

[BibT_eX]

[DOI]

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

1996

On the hardness of approximating optimum schedule problems in store and forward networks.

[BibT_eX]

[DOI]

Miriam Di Ianni

IEEE/ACM Trans. Netw., 1996

Constructing the Highest Degree Subgraph for Dense Graphs is in NCAS.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Hitting Properties of Hard Boolean Operators and their Consequences on BPP

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

Towards efficient constructions of hitting sets that derandomize BPP

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

Optimal Bounds on the Approximation of Boolean Functions with Consequences on the Concept of Hardware.

[BibT_eX]

[DOI]

Proceedings of the STACS 96, 1996

Randomized parallel algorithms.

[BibT_eX]

[DOI]

Erik Urland

Proceedings of the Solving Combinatorial Optimization Problems in Parallel, 1996

Parallel approximation of optimization problems.

[BibT_eX]

[DOI]

Proceedings of the Solving Combinatorial Optimization Problems in Parallel, 1996

On the Parallel Computation of Boolean Functions on Unrelated inputs.

[BibT_eX]

Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

Improved Non-approximability Results for Vertex Cover with Density Constraints.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995

The Reachability Problem for Finite Cellular Automata.

[BibT_eX]

[DOI]

Russell Impagliazzo

Inf. Process. Lett., 1995

Optimum Schedule Problems in Store and Forward Networks.

[BibT_eX]

[DOI]

Miriam Di Ianni

Int. J. Found. Comput. Sci., 1995

Hitting Sets Derandomize BPP

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

Some Results on Invertible Cellular Automata.

[BibT_eX]

[DOI]

Patrizia Mentrasti

Pierluigi Pierini

Complex Syst., 1995

1994

Fast Parallel Arithmetic on Cellular Automata.

[BibT_eX]

[DOI]

Giuseppe A. De Biase

Annalisa Massini

Complex Syst., 1994

Graph Theory and Interactive Protocols for Reachability Problems on Finite Cellular Automata.

[BibT_eX]

[DOI]