Edit Profile (opens in new tab) Fraigniaud, Pierre Co-Author Distance Author ID: fraigniaud.pierre Published as: Fraigniaud, Pierre; Fraigniaud, P. Homepage: https://www.irif.fr/users/pierref/index External Links: MGP · ORCID · Wikidata · Google Scholar · dblp · IdRef · theses.fr Documents Indexed: 175 Publications since 1990 12 Contributions as Editor Co-Authors: 131 Co-Authors with 176 Joint Publications 3,397 Co-Co-Authors all top 5 Co-Authors 11 single-authored 22 Pelc, Andrzej 20 Korman, Amos 18 Gavoille, Cyril 17 Ilcinkas, David 16 Rajsbaum, Sergio 12 Peleg, David 12 Travers, Corentin 11 Todinca, Ioan 10 Nisse, Nicolas 10 Paz, Ami 9 Feuilloley, Laurent 9 Rapaport, Ivan 8 Fomin, Fedor V. 8 Lotker, Zvi 8 Montealegre, Pedro 7 Lebhar, Emmanuelle 6 Barrière, Lali 6 Castañeda, Armando 6 Crescenzi, Pierluigi 6 Hirvonen, Juho 6 Rosén, Adi 6 Roy, Matthieu 5 Baumann, Hervé 5 Cohen, Johanne 5 Halldórsson, Magnús Mar 5 Mans, Bernard 5 Thilikos, Dimitrios M. 4 Balliu, Alkida 4 Cohen, Reuven Zev 4 Emek, Yuval 4 Harutyunyan, Hovhannes A. 4 Olivetti, Dennis 4 Patt-Shamir, Boaz 3 Arfaoui, Heger 3 Giakkoupis, George 3 Golovach, Petr A. 3 Kowalski, Dariusz R. 3 Kranakis, Evangelos Konstantinou 3 Mitjana, Margarida 3 Perry, Mor 3 Rémila, Eric 3 Santoro, Nicola 3 Suomela, Jukka 2 Bermond, Jean-Claude 2 Blin, Lélia 2 Bonakdarpour, Borzoo 2 Clementi, Andrea E. F. 2 Cormen, Tom 2 D’Angelo, Gianlorenzo 2 De Verclos, Rémi De Joannis 2 Dehne, Frank 2 Dessmark, Anders 2 Diks, Krzysztof 2 Doerr, Carola 2 Esparza, Javier 2 Fleury, Eric 2 Flocchini, Paola 2 Gafni, Eli M. 2 Gąsieniec, Leszek Antoni 2 Gelles, Ran 2 Göös, Mika 2 Husfeldt, Thore 2 Koutsoupias, Elias 2 Kuznetsov, Petr 2 Lazard, Emmanuel 2 Luce, Maël 2 Mathieu, Fabien 2 Matias, Yossi 2 Natale, Emanuele 2 Oshman, Rotem 2 Parter, Merav 2 Pasquale, Francesco 2 Paul, Christophe 2 Peer, Guy 2 Pérennes, Stéphane 2 Peters, Joseph G. 2 Rabie, Mikaël 2 Rawitz, Dror 2 Rieutord, Thibault 2 Robert, Yves 2 Rodeh, Yoav 2 Rosenberg, Arnold Leonard 2 Rosenblueth, David A. 2 Silvestri, Riccardo 2 Vial, Sandrine 1 Amato, Nancy M. 1 Angelopoulos, Spyros 1 Baruch, Mor 1 Bastide, Paul 1 Bougé, Luc 1 Bournez, Olivier 1 Cappello, Franck 1 Chaintreau, Augustin 1 Collet, Simon 1 Cosnard, Michel Y. 1 Delporte-Gallet, Carole 1 Even, Guy 1 Fauconnier, Hugues 1 Fischer, Orr 1 Gauron, Philippe ...and 31 more Co-Authors all top 5 Serials 18 Theoretical Computer Science 14 Distributed Computing 7 Algorithmica 6 Theory of Computing Systems 5 Discrete Applied Mathematics 5 Networks 5 Information and Computation 4 Information Processing Letters 4 Journal of the ACM 3 Journal of Parallel and Distributed Computing 3 Lecture Notes in Computer Science 3 Journal of Applied and Computational Topology 2 Journal of Computer and System Sciences 2 Parallel Computing 2 ACM Transactions on Algorithms 1 Discrete Mathematics 1 BIT 1 SIAM Journal on Computing 1 Journal of Algorithms 1 Mathematical Social Sciences 1 SIAM Journal on Discrete Mathematics 1 Random Structures & Algorithms 1 International Journal of Foundations of Computer Science 1 Bulletin of the European Association for Theoretical Computer Science EATCS 1 Computer Networks 1 LIPIcs – Leibniz International Proceedings in Informatics all top 5 Fields 169 Computer science (68-XX) 52 Combinatorics (05-XX) 15 Operations research, mathematical programming (90-XX) 12 General and overarching topics; collections (00-XX) 11 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 4 Probability theory and stochastic processes (60-XX) 4 Information and communication theory, circuits (94-XX) 3 Numerical analysis (65-XX) 2 Mathematical logic and foundations (03-XX) 2 Order, lattices, ordered algebraic structures (06-XX) 2 Field theory and polynomials (12-XX) 2 Functions of a complex variable (30-XX) 1 Real functions (26-XX) 1 Quantum theory (81-XX) 1 Biology and other natural sciences (92-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 154 Publications have been cited 1,749 times in 919 Documents Cited by ▼ Year ▼ Methods and problems of communication in usual networks. Zbl 0818.94029 Fraigniaud, Pierre; Lazard, Emmanuel 121 1994 Online computation with advice. Zbl 1218.68200 Emek, Yuval; Fraigniaud, Pierre; Korman, Amos; Rosén, Adi 66 2011 Deterministic rendezvous in graphs. Zbl 1100.68077 Dessmark, Anders; Fraigniaud, Pierre; Kowalski, Dariusz R.; Pelc, Andrzej 65 2006 Graph exploration by a finite automaton. Zbl 1081.68045 Fraigniaud, Pierre; Ilcinkas, David; Peer, Guy; Pelc, Andrzej; Peleg, David 61 2005 Routing in trees. Zbl 0987.68001 Fraigniaud, Pierre; Gavoille, Cyril 59 2001 Collective tree exploration. Zbl 1107.68065 Fraigniaud, Pierre; Ģasieniec, Leszek; Kowalski, Dariusz R.; Pelc, Andrzej 53 2006 Towards a complexity theory for local distributed computing. Zbl 1281.68133 Fraigniaud, Pierre; Korman, Amos; Peleg, David 48 2013 Tree exploration with little memory. Zbl 1067.68100 Diks, Krzysztof; Fraigniaud, Pierre; Kranakis, Evangelos; Pelc, Andrzej 41 2004 Antepenultimate broadcasting. Zbl 0856.90046 Bermond, Jean-Claude; Fraigniaud, Pierre; Peters, Joseph G. 35 1995 Delays induce an exponential memory gap for rendezvous in trees. Zbl 1301.68203 Fraigniaud, Pierre; Pelc, Andrzej 26 2013 Searching is not jumping. Zbl 1255.68105 Barrière, Lali; Fraigniaud, Pierre; Santoro, Nicola; Thilikos, Dimitrios M. 25 2003 Finding the roots of a polynomial on an MIMD multicomputer. Zbl 0734.65042 Cosnard, Michel; Fraigniaud, Pierre 25 1990 Local MST computation with short advice. Zbl 1213.68123 Fraigniaud, Pierre; Korman, Amos; Lebhar, Emmanuelle 25 2010 Efficient routing in networks with long range contacts. Zbl 1024.68501 Barrière, Lali; Fraigniaud, Pierre; Kranakis, Evangelos; Krizanc, Danny 24 2001 Connected graph searching. Zbl 1252.91026 Barrière, Lali; Flocchini, Paola; Fomin, Fedor V.; Fraigniaud, Pierre; Nisse, Nicolas; Santoro, Nicola; Thilikos, Dimitrios M. 23 2012 Digraphs exploration with little memory. Zbl 1122.68676 Fraigniaud, Pierre; Ilcinkas, David 23 2004 Connected treewidth and connected graph searching. Zbl 1145.68473 Fraigniaud, Pierre; Nisse, Nicolas 23 2006 Survey of distributed decision. Zbl 1409.68043 Feuilloley, Laurent; Fraigniaud, Pierre 22 2016 Deterministic rendezvous in trees with little memory. Zbl 1161.68336 Fraigniaud, Pierre; Pelc, Andrzej 22 2008 Tree exploration with advice. Zbl 1169.68047 Fraigniaud, Pierre; Ilcinkas, David; Pelc, Andrzej 22 2008 Label-guided graph exploration by a finite automaton. Zbl 1445.68157 Cohen, Reuven; Fraigniaud, Pierre; Ilcinkas, David; Korman, Amos; Peleg, David 22 2008 Parsimonious flooding in dynamic graphs. Zbl 1291.68292 Baumann, Hervé; Crescenzi, Pierluigi; Fraigniaud, Pierre 21 2009 Minimum linear gossip graphs and maximal linear \((\Delta,k)\)-gossip graphs. Zbl 0993.94026 Fraigniaud, Pierre; Peters, Joseph G. 19 2001 On the impact of identifiers on local decision. Zbl 1323.68032 Fraigniaud, Pierre; Halldórsson, Magnús M.; Korman, Amos 18 2012 Local distributed decision. Zbl 1292.68027 Fraigniaud, Pierre; Korman, Amos; Peleg, David 18 2011 Rendezvous and election of mobile agents: Impact of sense of direction. Zbl 1107.68022 Barriere, Lali; Flocchini, Paola; Fraigniaud, Pierre; Santoro, Nicola 18 2007 Label-guided graph exploration by a finite automaton. Zbl 1082.68588 Cohen, Reuven; Fraigniaud, Pierre; Ilcinkas, David; Korman, Amos; Peleg, David 18 2005 Oracle size, a new measure of difficulty for communication tasks. Zbl 1314.68023 Fraigniaud, Pierre; Ilcinkas, David; Pelc, Andrzej 18 2006 Communication algorithms with advice. Zbl 1201.68017 Fraigniaud, Pierre; Ilcinkas, David; Pelc, Andrzej 18 2010 Distributed computing with advice: information sensitivity of graph coloring. Zbl 1267.05118 Fraigniaud, Pierre; Gavoille, Cyril; Ilcinkas, David; Pelc, Andrzej 17 2009 Randomized proof-labeling schemes. Zbl 1452.68024 Fraigniaud, Pierre; Patt-Shamir, Boaz; Perry, Mor 17 2019 Three notes on distributed property testing. Zbl 1515.68365 Even, Guy; Fischer, Orr; Fraigniaud, Pierre; Gonen, Tzlil; Levi, Reut; Medina, Moti; Montealegre, Pedro; Olivetti, Dennis; Oshman, Rotem; Rapaport, Ivan; Todinca, Ioan 17 2017 Interval routing schemes. Zbl 0896.68005 Fraigniaud, P.; Gavoille, C. 16 1998 What can be decided locally without identifiers? Zbl 1323.68031 Fraigniaud, Pierre; Göös, Mika; Korman, Amos; Suomela, Jukka 16 2013 Broadcasting and gossiping in de Bruijn networks. Zbl 0802.68094 Bermond, Jean-Claude; Fraigniaud, Pierre 15 1994 Online computation with advice. Zbl 1248.68571 Emek, Yuval; Fraigniaud, Pierre; Korman, Amos; Rosén, Adi 15 2009 Trade-offs in distributed interactive proofs. Zbl 1515.68140 Crescenzi, Pierluigi; Fraigniaud, Pierre; Paz, Ami 15 2019 Distributedly testing cycle-freeness. Zbl 1417.68278 Arfaoui, Heger; Fraigniaud, Pierre; Ilcinkas, David; Mathieu, Fabien 14 2014 Memory requirement for universal routing schemes. Zbl 1373.68044 Fraigniaud, Pierre; Gavoille, Cyril 14 1995 Deterministic rendezvous in graphs. Zbl 1266.68143 Dessmark, Anders; Fraigniaud, Pierre; Pelc, Andrzej 14 2003 Distributed testing of excluded subgraphs. Zbl 1393.68133 Fraigniaud, Pierre; Rapaport, Ivan; Salo, Ville; Todinca, Ioan 14 2016 Distributed computing with advice: Information sensitivity of graph coloring. Zbl 1171.68859 Fraigniaud, Pierre; Gavoille, Cyril; Ilcinkas, David; Pelc, Andrzej 13 2007 A space lower bound for routing in trees. Zbl 1054.68100 Fraigniaud, Pierre; Gavoille, Cyril 13 2002 Distributed chasing of network intruders. Zbl 1146.68013 Blin, Lélia; Fraigniaud, Pierre; Nisse, Nicolas; Vial, Sandrine 13 2008 Eclecticism shrinks even small worlds. Zbl 1321.05246 Fraigniaud, Pierre; Gavoille, Cyril; Paul, Christophe 12 2004 Locality and checkability in wait-free computing. Zbl 1311.68026 Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin 12 2013 Greedy routing in tree-decomposed graphs. Zbl 1142.68457 Fraigniaud, Pierre 12 2005 A hierarchy of local decision. Zbl 1388.68062 Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho 12 2016 Monotony properties of connected visible graph searching. Zbl 1152.91383 Fraigniaud, Pierre; Nisse, Nicolas 12 2008 Parsimonious flooding in dynamic graphs. Zbl 1231.68175 Baumann, Hervé; Crescenzi, Pierluigi; Fraigniaud, Pierre 12 2011 Broadcasting in a hypercube when some calls fail. Zbl 0735.68005 Fraigniaud, Pierre; Peyrat, Claudine 11 1991 Rumor spreading in random evolving graphs. Zbl 1381.05065 Clementi, Andrea; Crescenzi, Pierluigi; Doerr, Carola; Fraigniaud, Pierre; Pasquale, Francesco; Silvestri, Riccardo 10 2016 Randomized proof-labeling schemes. Zbl 1333.68044 Baruch, Mor; Fraigniaud, Pierre; Patt-Shamir, Boaz 10 2015 D2B: A de Bruijn based content-addressable network. Zbl 1088.68016 Fraigniaud, Pierre; Gauron, Philippe 10 2006 The Durand-Kerner polynomials roots-finding method in case of multiple roots. Zbl 0719.65039 Fraigniaud, Pierre 10 1991 Collective tree exploration. Zbl 1196.68171 Fraigniaud, Pierre; Gasieniec, Leszek; Kowalski, Dariusz R.; Pelc, Andrzej 10 2004 Nondeterministic graph searching: from pathwidth to treewidth. Zbl 1172.68046 Fomin, Fedor V.; Fraigniaud, Pierre; Nisse, Nicolas 10 2009 A doubling dimension threshold \(\Theta (\log \log n)\) for augmented graph navigability. Zbl 1131.68486 Fraigniaud, Pierre; Lebhar, Emmanuelle; Lotker, Zvi 10 2006 On distributed Merlin-Arthur decision protocols. Zbl 1534.68069 Fraigniaud, Pierre; Montealegre, Pedro; Oshman, Rotem; Rapaport, Ivan; Todinca, Ioan 10 2019 What can be verified locally? Zbl 1398.68167 Balliu, Alkida; D’Angelo, Gianlorenzo; Fraigniaud, Pierre; Olivetti, Dennis 10 2018 Universal augmentation schemes for network navigability. Zbl 1168.68006 Fraigniaud, Pierre; Gavoille, Cyril; Kosowski, Adrian; Lebhar, Emmanuelle; Lotker, Zvi 9 2009 Approximation algorithms for minimum-time broadcast under the vertex-disjoint paths mode. Zbl 1006.68959 Fraigniaud, Pierre 9 2001 Tree exploration with little memory. Zbl 1093.68615 Diks, Krzysztof; Fraigniaud, Pierre; Kranakis, Evangelos; Pelc, Andrzej 9 2002 On the searchability of small-world networks with arbitrary underlying structure. Zbl 1293.05359 Fraigniaud, Pierre; Giakkoupis, George 9 2010 Tree exploration with an oracle. Zbl 1132.68507 Fraigniaud, Pierre; Ilcinkas, David; Pelc, Andrzej 9 2006 Node labels in local decision. Zbl 1409.68044 Fraigniaud, Pierre; Hirvonen, Juho; Suomela, Jukka 8 2015 Nondeterministic graph searching: From pathwidth to treewidth. Zbl 1156.68506 Fomin, Fedor V.; Fraigniaud, Pierre; Nisse, Nicolas 8 2005 Decidability classes for mobile agents computing. Zbl 1353.68090 Fraigniaud, Pierre; Pelc, Andrzej 8 2012 Redundancy in distributed proofs. Zbl 1510.68024 Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho; Paz, Ami; Perry, Mor 8 2021 Compact distributed certification of planar graphs. Zbl 1515.68238 Feuilloley, Laurent; Fraigniaud, Pierre; Montealegre, Pedro; Rapaport, Ivan; Rémila, Éric; Todinca, Ioan 8 2021 Randomized distributed decision. Zbl 1320.68223 Fraigniaud, Pierre; Göös, Mika; Korman, Amos; Parter, Merav; Peleg, David 7 2014 A characterization of networks supporting linear interval routing. Zbl 1373.68043 Fraigniaud, Pierre; Gavoille, Cyril 7 1994 Rumor spreading in random evolving graphs. Zbl 1394.68026 Clementi, Andrea; Crescenzi, Pierluigi; Doerr, Carola; Fraigniaud, Pierre; Isopi, Marco; Panconesi, Alessandro; Pasquale, Francesco; Silvestri, Riccardo 7 2013 Error-sensitive proof-labeling schemes. Zbl 1515.68079 Feuilloley, Laurent; Fraigniaud, Pierre 7 2017 Networks become navigable as nodes move and forget. Zbl 1152.68326 Chaintreau, Augustin; Fraigniaud, Pierre; Lebhar, Emmanuelle 7 2008 Impact of memory size on graph exploration capability. Zbl 1155.68055 Fraigniaud, Pierre; Ilcinkas, David; Pelc, Andrzej 7 2008 Graph exploration by a finite automaton. Zbl 1096.68080 Fraigniaud, Pierre; Ilcinkas, David; Peer, Guy; Pelc, Andrzej; Peleg, David 6 2004 Labeling schemes for tree representation. Zbl 1170.05303 Cohen, Reuven; Fraigniaud, Pierre; Ilcinkas, David; Korman, Amos; Peleg, David 6 2005 Locality and checkability in wait-free computing. Zbl 1311.68025 Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin 6 2011 What can be verified locally? Zbl 1398.68166 Balliu, Alkida; D’Angelo, Gianlorenzo; Fraigniaud, Pierre; Olivetti, Dennis 6 2017 Decentralized asynchronous crash-resilient runtime verification. Zbl 1392.68234 Bonakdarpour, Borzoo; Fraigniaud, Pierre; Rajsbaum, Sergio; Rosenblueth, David A.; Travers, Corentin 6 2016 A hierarchy of local decision. Zbl 1476.68100 Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho 6 2021 A meta-theorem for distributed certification. Zbl 07615854 Fraigniaud, Pierre; Montealegre, Pedro; Rapaport, Ivan; Todinca, Ioan 6 2022 Small worlds as navigable augmented networks: Model, analysis, and validation. Zbl 1151.68317 Fraigniaud, Pierre 6 2007 Monotony properties of connected visible graph searching. Zbl 1167.68407 Fraigniaud, Pierre; Nisse, Nicolas 6 2006 Complexity analysis of broadcasting in hypercubes with restricted communication capabilities. Zbl 0763.68039 Fraigniaud, Pierre 5 1992 Minimizing the number of opinions for fault-tolerant distributed decision using well-quasi orderings. Zbl 1475.68205 Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin 5 2016 Parallel exhaustive search without coordination. Zbl 1373.68202 Fraigniaud, Pierre; Korman, Amos; Rodeh, Yoav 5 2016 Randomized distributed decision. Zbl 1377.68317 Fraigniaud, Pierre; Korman, Amos; Parter, Merav; Peleg, David 5 2012 Noisy rumor spreading and plurality consensus. Zbl 1452.68023 Fraigniaud, Pierre; Natale, Emanuele 5 2019 A topological perspective on distributed network algorithms. Zbl 1534.68023 Castañeda, Armando; Fraigniaud, Pierre; Paz, Ami; Rajsbaum, Sergio; Roy, Matthieu; Travers, Corentin 5 2019 Shrinking maxima, decreasing costs: new online packing and covering problems. Zbl 1339.68319 Fraigniaud, Pierre; Halldórsson, Magnús M.; Patt-Shamir, Boaz; Rawitz, Dror; Rosén, Adi 4 2016 Compact ancestry labeling schemes for XML trees. Zbl 1288.05270 Fraigniaud, Pierre; Korman, Amos 4 2010 An algorithmic model for heterogeneous hyper-clusters: rationale and experience. Zbl 1104.68308 Cappello, Franck; Fraigniaud, Pierre; Mans, Bernard; Rosenberg, Arnold L. 4 2005 The effect of power-law degrees on the navigability of small worlds (extended abstract). Zbl 1291.05190 Fraigniaud, Pierre; Giakkoupis, George 4 2009 Scattering on a ring of processors. Zbl 0695.68020 Fraigniaud, Pierre; Miguet, Serge; Robert, Yves 4 1990 Eclecticism shrinks even small worlds. Zbl 1264.05127 Fraigniaud, Pierre; Gavoille, Cyril; Paul, Christophe 4 2006 Computing with large populations using interactions. Zbl 1365.68254 Bournez, Olivier; Fraigniaud, Pierre; Koegler, Xavier 4 2012 Space lower bounds for graph exploration via reduced automata. Zbl 1085.68110 Fraigniaud, Pierre; Ilcinkas, David; Rajsbaum, Sergio; Tixeuil, Sébastien 4 2005 Assigning labels in unknown anonymous networks (extended abstract). Zbl 1314.68374 Fraigniaud, Pierre; Pelc, Andrzej; Peleg, David; Pérennes, Stéphane 4 2000 Parameterized complexity of broadcasting in graphs. Zbl 1548.68155 Fomin, Fedor V.; Fraigniaud, Pierre; Golovach, Petr A. 1 2024 Local certification of graphs with bounded genus. Zbl 07628632 Feuilloley, Laurent; Fraigniaud, Pierre; Montealegre, Pedro; Rapaport, Ivan; Rémila, Éric; Todinca, Ioan 4 2023 Parameterized complexity of broadcasting in graphs. Zbl 1544.68113 Fomin, Fedor V.; Fraigniaud, Pierre; Golovach, Petr A. 1 2023 Synchronous \(t\)-resilient consensus in arbitrary graphs. Zbl 07687221 Castañeda, Armando; Fraigniaud, Pierre; Paz, Ami; Rajsbaum, Sergio; Roy, Matthieu; Travers, Corentin 1 2023 A meta-theorem for distributed certification. Zbl 07615854 Fraigniaud, Pierre; Montealegre, Pedro; Rapaport, Ivan; Todinca, Ioan 6 2022 Present-biased optimization. Zbl 1497.91088 Fomin, Fedor V.; Fraigniaud, Pierre; Golovach, Petr A. 1 2022 11th international conference on fun with algorithms, FUN 2022, Island of Favignana, Sicily, Italy, May 30 – June 3, 2022. Zbl 1489.68013 1 2022 A speedup theorem for asynchronous computation with applications to consensus and approximate agreement. Zbl 07824299 Fraigniaud, Pierre; Paz, Ami; Rajsbaum, Sergio 1 2022 Decentralized asynchronous crash-resilient runtime verification. Zbl 07679902 Bonakdarpour, Borzoo; Fraigniaud, Pierre; Rajsbaum, Sergio; Rosenblueth, David; Travers, Corentin 1 2022 Redundancy in distributed proofs. Zbl 1510.68024 Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho; Paz, Ami; Perry, Mor 8 2021 Compact distributed certification of planar graphs. Zbl 1515.68238 Feuilloley, Laurent; Fraigniaud, Pierre; Montealegre, Pedro; Rapaport, Ivan; Rémila, Éric; Todinca, Ioan 8 2021 A hierarchy of local decision. Zbl 1476.68100 Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho 6 2021 A topological perspective on distributed network algorithms. Zbl 1464.68438 Castañeda, Armando; Fraigniaud, Pierre; Paz, Ami; Rajsbaum, Sergio; Roy, Matthieu; Travers, Corentin 4 2021 Brief annoucement: On extending Brandt’s speedup theorem from LOCAL to round-based full-information models. Zbl 07774298 Bastide, Paul; Fraigniaud, Pierre 1 2021 The topology of randomized symmetry-breaking distributed computing. Zbl 07824219 Fraigniaud, Pierre; Gelles, Ran; Lotker, Zvi 1 2021 Compact distributed certification of planar graphs. Zbl 07323205 Feuilloley, Laurent; Fraigniaud, Pierre; Montealegre, Pedro; Rapaport, Ivan; Rémila, Éric; Todinca, Ioan 4 2020 A lower bound on the number of opinions needed for fault-tolerant decentralized run-time monitoring. Zbl 1435.68196 Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin 4 2020 Distributed testing of distance-\(k\) colorings. Zbl 07581071 Fraigniaud, Pierre; Halldórsson, Magnús M.; Nolin, Alexandre 1 2020 Deciding and verifying network properties locally with few output bits. Zbl 1434.68343 Arfaoui, Heger; Fraigniaud, Pierre; Ilcinkas, David; Mathieu, Fabien; Pelc, Andrzej 1 2020 Randomized proof-labeling schemes. Zbl 1452.68024 Fraigniaud, Pierre; Patt-Shamir, Boaz; Perry, Mor 17 2019 Trade-offs in distributed interactive proofs. Zbl 1515.68140 Crescenzi, Pierluigi; Fraigniaud, Pierre; Paz, Ami 15 2019 On distributed Merlin-Arthur decision protocols. Zbl 1534.68069 Fraigniaud, Pierre; Montealegre, Pedro; Oshman, Rotem; Rapaport, Ivan; Todinca, Ioan 10 2019 Noisy rumor spreading and plurality consensus. Zbl 1452.68023 Fraigniaud, Pierre; Natale, Emanuele 5 2019 A topological perspective on distributed network algorithms. Zbl 1534.68023 Castañeda, Armando; Fraigniaud, Pierre; Paz, Ami; Rajsbaum, Sergio; Roy, Matthieu; Travers, Corentin 5 2019 Parallel Bayesian search with no coordination. Zbl 1427.68359 Fraigniaud, Pierre; Korman, Amos; Rodeh, Yoav 4 2019 Synchronous \(t\)-resilient consensus in arbitrary graphs. Zbl 1543.68031 Castañeda, Armando; Fraigniaud, Pierre; Paz, Ami; Rajsbaum, Sergio; Roy, Matthieu; Travers, Corentin 2 2019 What can be verified locally? Zbl 1398.68167 Balliu, Alkida; D’Angelo, Gianlorenzo; Fraigniaud, Pierre; Olivetti, Dennis 10 2018 Redundancy in distributed proofs. Zbl 1497.68297 Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho; Paz, Ami; Perry, Mor 4 2018 Node labels in local decision. Zbl 1409.68045 Fraigniaud, Pierre; Hirvonen, Juho; Suomela, Jukka 2 2018 Three notes on distributed property testing. Zbl 1515.68365 Even, Guy; Fischer, Orr; Fraigniaud, Pierre; Gonen, Tzlil; Levi, Reut; Medina, Moti; Montealegre, Pedro; Olivetti, Dennis; Oshman, Rotem; Rapaport, Ivan; Todinca, Ioan 17 2017 Error-sensitive proof-labeling schemes. Zbl 1515.68079 Feuilloley, Laurent; Fraigniaud, Pierre 7 2017 What can be verified locally? Zbl 1398.68166 Balliu, Alkida; D’Angelo, Gianlorenzo; Fraigniaud, Pierre; Olivetti, Dennis 6 2017 Survey of distributed decision. Zbl 1409.68043 Feuilloley, Laurent; Fraigniaud, Pierre 22 2016 Distributed testing of excluded subgraphs. Zbl 1393.68133 Fraigniaud, Pierre; Rapaport, Ivan; Salo, Ville; Todinca, Ioan 14 2016 A hierarchy of local decision. Zbl 1388.68062 Feuilloley, Laurent; Fraigniaud, Pierre; Hirvonen, Juho 12 2016 Rumor spreading in random evolving graphs. Zbl 1381.05065 Clementi, Andrea; Crescenzi, Pierluigi; Doerr, Carola; Fraigniaud, Pierre; Pasquale, Francesco; Silvestri, Riccardo 10 2016 Decentralized asynchronous crash-resilient runtime verification. Zbl 1392.68234 Bonakdarpour, Borzoo; Fraigniaud, Pierre; Rajsbaum, Sergio; Rosenblueth, David A.; Travers, Corentin 6 2016 Minimizing the number of opinions for fault-tolerant distributed decision using well-quasi orderings. Zbl 1475.68205 Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin 5 2016 Parallel exhaustive search without coordination. Zbl 1373.68202 Fraigniaud, Pierre; Korman, Amos; Rodeh, Yoav 5 2016 Shrinking maxima, decreasing costs: new online packing and covering problems. Zbl 1339.68319 Fraigniaud, Pierre; Halldórsson, Magnús M.; Patt-Shamir, Boaz; Rawitz, Dror; Rosén, Adi 4 2016 Perfect failure detection with very few bits. Zbl 1425.68040 Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin; Kuznetsov, Petr; Rieutord, Thibault 4 2016 Noisy rumor spreading and plurality consensus (extended abstract). Zbl 1373.68096 Fraigniaud, Pierre; Natale, Emanuele 2 2016 On the complexity of the shortest-path broadcast problem. Zbl 1326.05040 Crescenzi, Pierluigi; Fraigniaud, Pierre; Halldórsson, Magnus; Harutyunyan, Hovhannes A.; Pierucci, Chiara; Pietracaprina, Andrea; Pucci, Geppino 1 2016 Sparsifying congested cliques and core-periphery networks. Zbl 1482.68045 Balliu, Alkida; Fraigniaud, Pierre; Lotker, Zvi; Olivetti, Dennis 1 2016 Asynchronous coordination under preferences and constraints. Zbl 1482.68054 Castañeda, Armando; Fraigniaud, Pierre; Gafni, Eli; Rajsbaum, Sergio; Roy, Matthieu 1 2016 An optimal ancestry labeling scheme with applications to XML trees and universal posets. Zbl 1426.68078 Fraigniaud, Pierre; Korman, Amos 1 2016 Randomized proof-labeling schemes. Zbl 1333.68044 Baruch, Mor; Fraigniaud, Pierre; Patt-Shamir, Boaz 10 2015 Node labels in local decision. Zbl 1409.68044 Fraigniaud, Pierre; Hirvonen, Juho; Suomela, Jukka 8 2015 Distributedly testing cycle-freeness. Zbl 1417.68278 Arfaoui, Heger; Fraigniaud, Pierre; Ilcinkas, David; Mathieu, Fabien 14 2014 Randomized distributed decision. Zbl 1320.68223 Fraigniaud, Pierre; Göös, Mika; Korman, Amos; Parter, Merav; Peleg, David 7 2014 Greedy routing in small-world networks with power-law degrees. Zbl 1319.68028 Fraigniaud, Pierre; Giakkoupis, George 3 2014 Automata, languages, and programming. 41st international colloquium, ICALP 2014, Copenhagen, Denmark, July 8–11, 2014. Proceedings, Part II. Zbl 1291.68018 1 2014 Automata, languages, and programming. 41st international colloquium, ICALP 2014, Copenhagen, Denmark, July 8–11, 2014. Proceedings, Part I. Zbl 1291.68019 1 2014 The worst case behavior of randomized gossip protocols. Zbl 1303.68030 Baumann, Hervé; Fraigniaud, Pierre; Harutyunyan, Hovhannes A.; de Verclos, Rémi 1 2014 Towards a complexity theory for local distributed computing. Zbl 1281.68133 Fraigniaud, Pierre; Korman, Amos; Peleg, David 48 2013 Delays induce an exponential memory gap for rendezvous in trees. Zbl 1301.68203 Fraigniaud, Pierre; Pelc, Andrzej 26 2013 What can be decided locally without identifiers? Zbl 1323.68031 Fraigniaud, Pierre; Göös, Mika; Korman, Amos; Suomela, Jukka 16 2013 Locality and checkability in wait-free computing. Zbl 1311.68026 Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin 12 2013 Rumor spreading in random evolving graphs. Zbl 1394.68026 Clementi, Andrea; Crescenzi, Pierluigi; Doerr, Carola; Fraigniaud, Pierre; Isopi, Marco; Panconesi, Alessandro; Pasquale, Francesco; Silvestri, Riccardo 7 2013 Shrinking maxima, decreasing costs: new online packing and covering problems. Zbl 1335.68297 Fraigniaud, Pierre; Halldórsson, Magnús M.; Patt-Shamir, Boaz; Rawitz, Dror; Rosén, Adi 1 2013 Connected graph searching. Zbl 1252.91026 Barrière, Lali; Flocchini, Paola; Fomin, Fedor V.; Fraigniaud, Pierre; Nisse, Nicolas; Santoro, Nicola; Thilikos, Dimitrios M. 23 2012 On the impact of identifiers on local decision. Zbl 1323.68032 Fraigniaud, Pierre; Halldórsson, Magnús M.; Korman, Amos 18 2012 Decidability classes for mobile agents computing. Zbl 1353.68090 Fraigniaud, Pierre; Pelc, Andrzej 8 2012 Randomized distributed decision. Zbl 1377.68317 Fraigniaud, Pierre; Korman, Amos; Parter, Merav; Peleg, David 5 2012 Computing with large populations using interactions. Zbl 1365.68254 Bournez, Olivier; Fraigniaud, Pierre; Koegler, Xavier 4 2012 The worst case behavior of randomized gossip. Zbl 1354.68022 Baumann, H.; Fraigniaud, P.; Harutyunyan, H. A.; de Verclos, R. 2 2012 Special issue: Selected papers based on the presentations at the 4th workshop on GRAph searching, theory and applications, GRASTA 2011, February 13–18, 2012. Dedicated to Professor Lefteris M. Kirousis on the occasion of his 60th birthday. Zbl 1283.05005 1 2012 Brief announcement: What can be computed without communication? Zbl 1301.68052 Arfaoui, Heger; Fraigniaud, Pierre 1 2012 Online computation with advice. Zbl 1218.68200 Emek, Yuval; Fraigniaud, Pierre; Korman, Amos; Rosén, Adi 66 2011 Local distributed decision. Zbl 1292.68027 Fraigniaud, Pierre; Korman, Amos; Peleg, David 18 2011 Parsimonious flooding in dynamic graphs. Zbl 1231.68175 Baumann, Hervé; Crescenzi, Pierluigi; Fraigniaud, Pierre 12 2011 Locality and checkability in wait-free computing. Zbl 1311.68025 Fraigniaud, Pierre; Rajsbaum, Sergio; Travers, Corentin 6 2011 Local MST computation with short advice. Zbl 1213.68123 Fraigniaud, Pierre; Korman, Amos; Lebhar, Emmanuelle 25 2010 Communication algorithms with advice. Zbl 1201.68017 Fraigniaud, Pierre; Ilcinkas, David; Pelc, Andrzej 18 2010 On the searchability of small-world networks with arbitrary underlying structure. Zbl 1293.05359 Fraigniaud, Pierre; Giakkoupis, George 9 2010 Compact ancestry labeling schemes for XML trees. Zbl 1288.05270 Fraigniaud, Pierre; Korman, Amos 4 2010 An optimal ancestry scheme and small universal posets. Zbl 1293.68143 Fraigniaud, Pierre; Korman, Amos 4 2010 A lower bound for network navigability. Zbl 1207.05186 Fraigniaud, Pierre; Lebhar, Emmanuelle; Lotker, Zvi 3 2010 Recovering the long-range links in augmented graphs. Zbl 1195.68014 Fraigniaud, Pierre; Lebhar, Emmanuelle; Lotker, Zvi 2 2010 On the additive constant of the \(k\)-server work function algorithm. Zbl 1284.68679 Emek, Yuval; Fraigniaud, Pierre; Korman, Amos; Rosén, Adi 2 2010 On the additive constant of the \(k\)-server work function algorithm. Zbl 1379.68360 Emek, Yuval; Fraigniaud, Pierre; Korman, Amos; Rosén, Adi 1 2010 Parsimonious flooding in dynamic graphs. Zbl 1291.68292 Baumann, Hervé; Crescenzi, Pierluigi; Fraigniaud, Pierre 21 2009 Distributed computing with advice: information sensitivity of graph coloring. Zbl 1267.05118 Fraigniaud, Pierre; Gavoille, Cyril; Ilcinkas, David; Pelc, Andrzej 17 2009 Online computation with advice. Zbl 1248.68571 Emek, Yuval; Fraigniaud, Pierre; Korman, Amos; Rosén, Adi 15 2009 Nondeterministic graph searching: from pathwidth to treewidth. Zbl 1172.68046 Fomin, Fedor V.; Fraigniaud, Pierre; Nisse, Nicolas 10 2009 Universal augmentation schemes for network navigability. Zbl 1168.68006 Fraigniaud, Pierre; Gavoille, Cyril; Kosowski, Adrian; Lebhar, Emmanuelle; Lotker, Zvi 9 2009 The effect of power-law degrees on the navigability of small worlds (extended abstract). Zbl 1291.05190 Fraigniaud, Pierre; Giakkoupis, George 4 2009 Labeling schemes for tree representation. Zbl 1171.68599 Cohen, Reuven; Fraigniaud, Pierre; Ilcinkas, David; Korman, Amos; Peleg, David 3 2009 Deterministic rendezvous in trees with little memory. Zbl 1161.68336 Fraigniaud, Pierre; Pelc, Andrzej 22 2008 Tree exploration with advice. Zbl 1169.68047 Fraigniaud, Pierre; Ilcinkas, David; Pelc, Andrzej 22 2008 Label-guided graph exploration by a finite automaton. Zbl 1445.68157 Cohen, Reuven; Fraigniaud, Pierre; Ilcinkas, David; Korman, Amos; Peleg, David 22 2008 Distributed chasing of network intruders. Zbl 1146.68013 Blin, Lélia; Fraigniaud, Pierre; Nisse, Nicolas; Vial, Sandrine 13 2008 Monotony properties of connected visible graph searching. Zbl 1152.91383 Fraigniaud, Pierre; Nisse, Nicolas 12 2008 Networks become navigable as nodes move and forget. Zbl 1152.68326 Chaintreau, Augustin; Fraigniaud, Pierre; Lebhar, Emmanuelle 7 2008 Impact of memory size on graph exploration capability. Zbl 1155.68055 Fraigniaud, Pierre; Ilcinkas, David; Pelc, Andrzej 7 2008 Rendezvous and election of mobile agents: Impact of sense of direction. Zbl 1107.68022 Barriere, Lali; Flocchini, Paola; Fraigniaud, Pierre; Santoro, Nicola 18 2007 Distributed computing with advice: Information sensitivity of graph coloring. Zbl 1171.68859 Fraigniaud, Pierre; Gavoille, Cyril; Ilcinkas, David; Pelc, Andrzej 13 2007 Small worlds as navigable augmented networks: Model, analysis, and validation. Zbl 1151.68317 Fraigniaud, Pierre 6 2007 Deterministic rendezvous in graphs. Zbl 1100.68077 Dessmark, Anders; Fraigniaud, Pierre; Kowalski, Dariusz R.; Pelc, Andrzej 65 2006 Collective tree exploration. Zbl 1107.68065 Fraigniaud, Pierre; Ģasieniec, Leszek; Kowalski, Dariusz R.; Pelc, Andrzej 53 2006 ...and 54 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 1,173 Authors 77 Fraigniaud, Pierre 65 Pelc, Andrzej 30 Korman, Amos 26 Harutyunyan, Hovhannes A. 26 Ilcinkas, David 25 Dereniowski, Dariusz 24 Czyzowicz, Jurek 23 Böckenhauer, Hans-Joachim 22 Kosowski, Adrian 21 Flocchini, Paola 21 Santoro, Nicola 20 Klasing, Ralf 19 Das, Shantanu 19 Gavoille, Cyril 18 Dieudonné, Yoann 18 Dobrev, Stefan 18 Komm, Dennis 18 Nisse, Nicolas 18 Peleg, David 16 Rapaport, Ivan 15 Královič, Rastislav 14 Feuilloley, Laurent 14 Gąsieniec, Leszek Antoni 14 Královič, Richard 14 Rajsbaum, Sergio 13 Chalopin, Jérémie 13 Gargano, Luisa 13 Labourel, Arnaud 13 Todinca, Ioan 12 Clementi, Andrea E. F. 12 Masuzawa, Toshimitsu 12 Montealegre, Pedro 11 Oshman, Rotem 11 Pérennes, Stéphane 10 Hromkovič, Juraj 10 Kuhn, Fabian 10 Liestman, Arthur L. 10 Navarra, Alfredo 10 Paz, Ami 10 Thilikos, Dimitrios M. 10 Wattenhofer, Roger P. 9 Censor-Hillel, Keren 9 Kranakis, Evangelos Konstantinou 9 Kutten, Shay 9 Molla, Anisur Rahaman 9 Shams, Mudassir 9 Silvestri, Riccardo 9 Vaccaro, Ugo 8 Bampas, Evangelos 8 Bouchard, Sébastien 8 Castañeda, Armando 8 Disser, Yann 8 Dragan, Feodor F. 8 Kamali, Shahin 8 Markou, Euripides 8 Maus, Yannic 8 Mir, Nazir Ahmad 8 Ooshita, Fukuhito 8 Pajak, Dominik 8 Petković, Miodrag S. 8 Rafiq, Naila 8 Rosén, Adi 8 Unger, Walter 7 Boyar, Joan F. 7 Emek, Yuval 7 Fomin, Fedor V. 7 Gorain, Barun 7 Hirvonen, Juho 7 Kakugawa, Hirotsugu 7 Li, Zhiyuan 7 Lotker, Zvi 7 Mihalák, Matúš 7 Renault, Marc P. 7 Travers, Corentin 7 Uitto, Jara 6 Agarwal, Praveen 6 Di Stefano, Gabriele 6 Favrholdt, Lene Monrad 6 Fertin, Guillaume 6 Karousatou, Christina 6 Kausar, Nasreen 6 Krizanc, Danny 6 Krug, Sacha 6 Larsen, Kim Skak 6 Martynova, Olga 6 Okhotin, Alexander 6 Pandurangan, Gopal 6 Paul, Christophe 6 Peters, Joseph G. 6 Raynal, Michel 6 Rescigno, Adele Anna 6 Suomela, Jukka 6 Xiang, Yang 5 Barrière, Lali 5 Bermond, Jean-Claude 5 Brandt, Sebastian F. 5 De Marco, Gianluca 5 Ghaffari, Mohsen 5 Kowalski, Dariusz R. 5 Kuszner, Łukasz ...and 1,073 more Authors all top 5 Cited in 105 Serials 142 Theoretical Computer Science 75 Discrete Applied Mathematics 61 Distributed Computing 39 Algorithmica 23 Information and Computation 22 Information Processing Letters 20 Theory of Computing Systems 18 Journal of Computer and System Sciences 17 Networks 13 International Journal of Foundations of Computer Science 7 Discrete Mathematics 6 SIAM Journal on Computing 6 SIAM Journal on Discrete Mathematics 6 Random Structures & Algorithms 6 Journal of Combinatorial Optimization 6 Journal of Discrete Algorithms 5 Journal of Applied and Computational Topology 4 Applied Mathematics and Computation 4 Journal of Computational and Applied Mathematics 4 International Journal of Computer Mathematics 4 Parallel Processing Letters 3 BIT 3 Computing 3 Journal of Parallel and Distributed Computing 3 Japan Journal of Industrial and Applied Mathematics 3 Fractals 3 Discrete Mathematics and Theoretical Computer Science. DMTCS 3 Natural Computing 3 Advances in Difference Equations 3 International Journal of Parallel, Emergent and Distributed Systems 3 RAIRO. Theoretical Informatics and Applications 3 ACM Transactions on Algorithms 2 Artificial Intelligence 2 Computers & Mathematics with Applications 2 Physica A 2 Applied Mathematics Letters 2 The Annals of Applied Probability 2 Computational Geometry 2 Numerical Algorithms 2 Cybernetics and Systems Analysis 2 Formal Methods in System Design 2 The Electronic Journal of Combinatorics 2 Mathematical Problems in Engineering 2 Journal of Graph Algorithms and Applications 2 CEJOR. Central European Journal of Operations Research 2 Methodology and Computing in Applied Probability 2 RAIRO. Operations Research 2 Discrete Mathematics, Algorithms and Applications 2 Journal of Dynamics and Games 2 Journal of Logical and Algebraic Methods in Programming 1 Acta Mechanica 1 Mathematical Methods in the Applied Sciences 1 Annales de l’Institut Fourier 1 Information Sciences 1 Journal of Combinatorial Theory. Series A 1 Journal of Graph Theory 1 The Journal of Mathematical Sociology 1 Mathematics of Operations Research 1 Systems & Control Letters 1 Operations Research Letters 1 Chinese Annals of Mathematics. Series B 1 Physica D 1 Applied Numerical Mathematics 1 Acta Mathematicae Applicatae Sinica. English Series 1 Graphs and Combinatorics 1 Journal of Computer Science and Technology 1 Asia-Pacific Journal of Operational Research 1 Mathematical and Computer Modelling 1 Mathematical Structures in Computer Science 1 European Journal of Operational Research 1 Linear Algebra and its Applications 1 Stochastic Processes and their Applications 1 The Australasian Journal of Combinatorics 1 International Journal of Bifurcation and Chaos in Applied Sciences and Engineering 1 Annals of Mathematics and Artificial Intelligence 1 Boletín de la Sociedad Matemática Mexicana. Third Series 1 Electronic Journal of Probability 1 International Transactions in Operational Research 1 Constraints 1 INFORMS Journal on Computing 1 Acta Mathematica et Informatica Universitatis Ostraviensis 1 Journal of Scheduling 1 Journal of the ACM 1 Journal of Discrete Mathematical Sciences & Cryptography 1 New Journal of Physics 1 RAIRO. Theoretical Informatics and Applications 1 Fundamenta Informaticae 1 Miscelánea Matemática 1 Journal of Systems Science and Complexity 1 Journal of Applied Mathematics and Computing 1 Discrete Optimization 1 Science in China. Series F 1 Logical Methods in Computer Science 1 Asian-European Journal of Mathematics 1 Advances and Applications in Discrete Mathematics 1 Algorithms 1 Science China. Information Sciences 1 ISRN Applied Mathematics 1 Frontiers of Computer Science in China 1 Moscow Journal of Combinatorics and Number Theory ...and 5 more Serials all top 5 Cited in 28 Fields 754 Computer science (68-XX) 290 Combinatorics (05-XX) 103 Operations research, mathematical programming (90-XX) 48 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 36 Numerical analysis (65-XX) 35 Information and communication theory, circuits (94-XX) 18 Probability theory and stochastic processes (60-XX) 15 Functions of a complex variable (30-XX) 13 Field theory and polynomials (12-XX) 10 Biology and other natural sciences (92-XX) 8 Mathematical logic and foundations (03-XX) 8 Real functions (26-XX) 5 Quantum theory (81-XX) 4 Systems theory; control (93-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Convex and discrete geometry (52-XX) 2 Group theory and generalizations (20-XX) 2 Ordinary differential equations (34-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 Calculus of variations and optimal control; optimization (49-XX) 1 Category theory; homological algebra (18-XX) 1 Operator theory (47-XX) 1 Geometry (51-XX) 1 Algebraic topology (55-XX) 1 Manifolds and cell complexes (57-XX) 1 Mechanics of deformable solids (74-XX) 1 Fluid mechanics (76-XX) 1 Statistical mechanics, structure of matter (82-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.