Ivan Rapaport's Home Page

Distributed certification for classes of dense gaphs. Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport and Ioan Todinca. Proceedings of the 37th International Symposium on Distributed Computing (DISC 2023), LIPIcs, Volume 281, October 9-13, 2023, L'Aquila, Italy.

Energy-efficient distributed algorithms for synchronous networks. Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport and Ioan Todinca. Proceedings of the 30th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2023), Lecture Notes in Computer Science 13892 (2023), 116-134, June 6-9, 2023, Alcalá de Henares, Spain.

Local certification of graphs with bounded genus. Eric Remila, Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport and Ioan Todinca. Discrete Applied Mathematics 325, 9-36, 2023.

Computing power of hybrid models in synchronous networks. Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martin Rios-Wilson and Ioan Todinca. Proceedings of the 26th International Conference on Principles of Distributed Systems (OPODIS 2022), 20:1-20:18, December 13-15, 2022, Brussels, Belgium.

Distributed maximal independent set computation driven by finite-state dynamics. Eric Goles, Laura Leal, Pedro Montealegre, Axel Osses, Ivan Rapaport and Martin Rios-Wilson. International Journal of Parallel, Emergent and Distributed Systems, 1-13, 2022.

A large diffusion and small amplification dynamics for density classification on graphs. Laura Leal, Pedro Montealegre, Axel Osses and Ivan Rapaport. International Journal of Modern Physics C, 2022.

Brief Announcement: Computing power of hybrid models in synchronous networks. Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martin Rios-Wilson and Ioan Todinca. Proceedings of the 36th International Symposium on Distributed Computing (DISC 2022), 43:1-42:3, vol. 246, October 25-27, 2022, Augusta, Georgia, United States.

A meta-theorem for distributed certification. Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport and Ioan Todinca. Proceedings of the 29th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2022), Lecture Notes in Computer Science 13298 (2022), 116-134, June 27-29, 2022. Paderborn, Germany.

Distributed interactive proofs for the recognition of some geometric intersection graph classes. Benjamín Jaúregui, Pedro Montealegre and Ivan Rapaport. Proceedings of the 29th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2022), Lecture Notes in Computer Science 13298 (2022), 212-233, June 27-29, 2022, Paderborn, Germany.

Connectivity and connected components in the number-in-hand computation model. Antonio Lizama and Ivan Rapaport. Automata and Complexity: Emergence, Complexity and Computation, vol. 42, 71-74, 2022.

The load minimization problem on cycles. Mariana Escalante, Martín Matamala, Ivan Rapaport, Paola Tolomei, Luis Miguel Torres. Joint International Conference on Applied Combinatorial Optimization (ALIO/EURO 2022), April 11-23, 2022, Valparaíso, Chile.

Compact distributed interactive proofs for the recognition of cographs and distance-hereditary graphs. Pedro Montealege, Diego Ramírez and Ivan Rapaport. Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2021), Lecture Notes in Computer Science 13046 (2021), 395-409, November 17-20, 2021.

Communication complexity meets cellular automata: Necessary conditions for intrinsic universality. Raimundo Briceño and Ivan Rapaport. Natural Computing, 20(2), 307-320, 2021.

The role of randomness in the broadcast congested clique model. Florent Becker, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. Information and Computation, Vol. 281, 104669, 2021.

The multiple traveling salesman problem on spiders. Pedro Pérez-Escalona, Ivan Rapaport, José Soto and Ian Vidal. Proceedings of the 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2021), Lecture Notes in Computer Science 12607 (2021), 337-348, January 25-28, 2021, Bolzano-Bozen, Italy.

Shared vs private randomness in distributed interactive proofs. Pedro Montealege, Diego Ramírez and Ivan Rapaport. Proceedings of the 31th International Symposium on Algorithms and Complexity (ISAAC 2020), LIPIcs 181, 51:1-51:13, December 14-18, 2020, Hong Kong.

Compact distributed certification of planar graphs. Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Eric Rémila and Ioan Todinca. Algorithmica 83, 2215–2244 (2021). Proceedings of the 39th Annual ACM Symposium on Principles of Distributed Computing (PODC 2020), 319-328, August 3-7, 2020, Salerno, Italy. 5th Conference on Highlights of Algorithms (HALG 2020), August 31-September 2, 2020, Zurich, Switzerland.

Graph reconstruction in the congested clique. Pedro Montealegre, Sebastian Perez-Salazar, Ivan Rapaport and Ioan Todinca. Journal of Computer and System Sciences 113 (2020), 1-17.

The impact of locality in the broadcast congested clique model. Florent Becker, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. SIAM Journal on Discrete Mathematics 34-1 (2020), 682-700.

On distributed Merlin-Arthur decision protocols. Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport and Ioan Todinca. Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019), Lecture Notes in Computer Science 11639 (2019), 230-245, July 1-4, 2019, L'Aquila, Gran Sasso, Italy.

Two rounds are enough for reconstructing any graph (class) in the congested clique model. Pedro Montealegre, Sebastian Perez-Salazar, Ivan Rapaport and Ioan Todinca. Proceedings of the 25th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2018), Lecture Notes in Computer Science 11085 (2018), 134-148, June 18-21, 2018, Kibbutz Ma'ale HaHamisha, Israel.

The impact of locality on the detection of cycles in the broadcast congested clique model. Florent Becker, Pedro Montealegre, Ivan Rapaport and Ioan Todinca. Proceedings of the 13th Latin American Theoretical Informatics Symposium (LATIN 2018), Lecture Notes in Computer Science 10807 (2018), 134-145, April 16-19, 2018, Buenos Aires, Argentina.

Three notes on distributed property testing. Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Denis Olivetti, Rotem Oshman, Ivan Rapaport and Ioan Todinca. Proceedings of the 31st International Symposium on Distributed Computing (DISC 2017), LIPIcs 91, 15:1-15:30, October 16-20, 2017, Vienna, Austria.

Fixed-points in Random Boolean Networks: The impact of parallelism in the Barabási-Albert scale-free topology case. Pablo Moisset, Axel Osses and Ivan Rapaport. BioSystems 150 (2016), 167-176.

Distributed testing of excluded subgraphs. Pierre Fraigniaud, Ivan Rapaport, Ville Salo and Ioan Todinca. Proceedings of the 30th International Symposium on Distributed Computing (DISC 2016), Lecture Notes in Computer Science 9888 (2016), 342-356, September 26-30, 2016, Paris, France.

The effect of range and bandwidth on the round complexity in the congested clique model. Florent Becker, Antonio Fernández Anta, Ivan Rapaport and Eric Rémila. Proceedings of the 22nd International Computing and Combinatorics Conference (COCOON 2016), Lecture Notes in Computer Science 9797 (2016), 182-193, August 2-4, 2016, Ho Chi Minh, Vietnam.

Robust reconstruction of Barabási-Albert networks in the broadcast congested clique model. P. Moisset, I. Rapaport, D. Remenik and J. Urrutia. Networks, Vol. 67(1), 82-91, 2016.
Solving the Induced Subgraph problem in the randomized multiparty simultaneous messages model. J. Kari, M. Matamala, I. Rapaport and V. Salo. Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2015), Lecture Notes in Computer Science 9439 (2015), 370-384, July 15-17, 2015, Montserrat, Spain.

Brief Announcement: A hierarchy of congested clique models, from broadcast to unicast. Florent Becker, Antonio Fernández Anta, Ivan Rapaport and Eric Rémila. Proceedings of the 34th Annual ACM Symposium on Principles of Distributed Computing (PODC 2015), 167-169, July 21-23, 2015, Donostia-San Sebastián, Spain.

Allowing each node to communicate only once in a distributed system: shared whiteboard models. F. Becker, A. Kosowski, M. Matamala, N. Nisse, I. Rapaport, K. Suchan and I. Todinca. Distributed Computing (2015) 28:189-200.
Séparation des modèles de communication simultanée pour les réseaux: protocoles déterministes, avec bits aléatoires publics et privés. F. Becker, P. Montealegre, I. Rapaport and I. Todinca. ALGOTEL 2015, June 2-5, 2015, Beaune, France.
The simultaneous number-in-hand communication model for networks: private coins, public coins and determinism. F. Becker, I. Rapaport, P. Montealegre and I. Todinca. Proceedings of the 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO 2014), Lecture Notes in Computer Science 8576 (2014), 83-95, July 23-25, 2014, Hida Takayama, Japan.

Strict majority bootstrap percolation on augmented tori and random regular graphs: experimental results. P. Moisset and I. Rapaport. Proceedings of the 20th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2014), Lecture Notes in Computer Science 8996 (2014), 1-9, July 7-9, 2014, Himeji, Japan.

Strict majority bootstrap percolation in the r-wheel M. Kiwi , P. Moisset, I. Rapaport, S. Rica and G. Theyssier. Information Processing Letters 114/6 (2014), 277-281.

Solving the density classification problem with a large diffusion and small amplification cellular automaton. R. Briceño, P. Moisset, A. Osses and I. Rapaport. Physica D 261 (2013) 70-80.

Letting Alice and Bob choose which problem to solve: Implications to the study of cellular automata R. Briceño and I. Rapaport. Theoretical Computer Science 468 (2013) 1-11.

Allowing each node to communicate only once in a distributed system: shared whiteboard models. F. Becker, A. Kosowski, N. Nisse, I. Rapaport and K. Suchan. Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architecture (SPAA 2012), 11-17, June 25-27, 2012, Pittsburgh, Pennsylvania, USA.
Adding a referee to an interconnection network: What can(not) be computed in one round? F. Becker, M. Matamala, N. Nisse, I. Rapaport, K. Suchan and I. Todinca. Proceedings of the 25th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2011), IEEE Computer Society (2011), 508-514, May 16-20, 2011, Anchorage, Alaska, USA.

Reconstruire un graphe en une ronde. F. Becker, M. Matamala, N. Nisse, I. Rapaport, K. Suchan and I. Todinca. Proceedings of the 13es Rencontres Francophones sur les Aspects Algorithmiques de Telecommunications (ALGOTEL 2011), May 23-26, 2011, Cap Esterel, France.

Communication complexity in number-preserving and monotone cellular automata. E. Goles, A. Moreira and I. Rapaport. Theoretical Computer Science 412/29 (2011), 3616-3628.

Communication complexity and intrinsic universality in cellular automata. E. Goles, P.-E. Meunier, I. Rapaport and G. Theyssier. Theoretical Computer Science 412/1-2 (2011), 2-21.

Average long-lived memoryless consensus: the three-value case. I. Rapaport and E. Remila. Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2010), Lecture Notes in Computer Science 6058 (2010), 114-126, June 7-11, 2010, Sirence, Turkey.

Traced communication complexity of cellular automata. E. Goles, P. Guillon and I. Rapaport. Theoretical Computer Science 412/30 (2011), 3906-3916. 15th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2009), October 10-12, 2009, Sao Jose dos Campos, Sao Paulo, Brazil.

Distributed computing of efficient routing schemes in generalized chordal graphs. N. Nisse, I. Rapaport and K. Suchan. Theoretical Computer Science 444 (2012), 17-27. Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2009), Lecture Notes in Computer Science 5869 (2010), 252-265, May 25-27, 2009, Piran, Slovenia.

Understanding a non-trivial cellular automaton by finding its simplest underlying communication protocol E. Goles, C. Little and I. Rapaport. Proceedings of the 19th International Symposium on Algorithms and Complexity (ISAAC 2008), Lecture Notes in Computer Science 5369 (2008), 593-605, December 15-17, 2008, Gold Coast, Australia.

Modeling heterocyst pattern formation in cyanobacteria. Z.P. Gerdtzen, J.C. Salgado, A. Osses, J.A. Asenjo, I. Rapaport and B.A. Andrews. BMC Bionformatics 2009 10(6). European Molecular Biology Network (EMBNet) Conference 2008: 20th Anniversary Celebration, September 18-20, 2008, Martina Franca, Italy.
Communications in cellular automata E. Goles, P.-E. Meunier, I. Rapaport and G. Theyssier. Electronic Proceedings of Theoretical Computer Science. International Workshop on the Complexity of Simple Programs (CSP 2008), 103-116, December 6-7, 2008, Cork, Ireland.

Average binary long-lived Consensus: quantifying the stabilizing role played by memory F. Becker, S. Rajsbaum, I. Rapaport and E. Remila. Theoretical Computer Science 411 (2010), 1558 - 1566. Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008), Lecture Notes in Computer Science 5058 (2008), 48-60, June 17-20, 2008, Villars-sur-Ollon, Switzerland.

On dissemination thresholds in regular and irregular graph classes I. Rapaport, K. Suchan, I. Todinca and J. Verstraete. Algorithmica (2011) 59: 16-34. Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN 2008), Lecture Notes in Computer Science 4957 (2008), 24-35, April 7-11, 2008, Buzios, Brazil.

Small alliances in graphs R. Carvajal, M. Matamala, I. Rapaport and N. Schabanel. Proceedings of the 32nd Symposium on Mathematical Foundations of Computer Science (MFCS 2007), Lecture Notes in Computer Science 4708 (2007), 218-227, August 26-31, 2007, Cesky Krumlov, Czech Republic. 10th Combinatorial and Computational Aspects of Optimization, Topology and Algebra (ACCOTA 2006), December 3-6, 2006, Puerto Vallarta, Mexico.

Self-Assemblying classes of shapes with a minimum number of tiles, and in optimal time. F. Becker, E. Remila and I. Rapaport. Proceedings of the 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2006), Lecture Notes in Computer Science 4337 (2006), 45-56, December 13-15, 2006, Kolkata, India.

Minimal proper interval completions I. Rapaport, K. Suchan and I. Todinca. Information Processing Letters 106 (2008), 195-202. Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Computer Science 4271 (2006), 217-228, June 22-24, 2006, Bergen, Norway.

The complexity of approximating the oriented diameter of chordal graphs F. Fomin, M. Matamala and I. Rapaport. Journal of Graph Theory 45(4), 2004, 255-269. Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2002), Lecture Notes in Computer Science 2573 (2002), 211-222, June 13-15, 2002, Cesky Krumlov, Czech Republic.

AT-free graphs: linear bounds for the oriented diameter F. Fomin, M. Matamala, E. Prisner and I. Rapaport. Discrete Applied Mathematics 141 (2004), 135-148. Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2001), March 17-19, 2001, Fortaleza, Brazil.

Cellular automata and communication complexity C. Durr, I. Rapaport and G. Theyssier. Theoretical Computer Science 322/2 (2004), 355-368.

Domino tilings and other physical models: space of configurations of domains with holes S. Desreux, M. Matamala, I. Rapaport and E. Remila. Theoretical Computer Science 319 (2004), 83-101. IV Simposio Chileno de Matematicas, November 12-15, 2002, Punta Arenas, Chile.

Tiling with bars under tomographic constraints C. Durr, E. Goles, I. Rapaport and E. Remila. Theoretical Computer Science 290 (2003), 1317-1329.

Who wins Domineering on rectangular boards? M. Lachmann, C. Moore and I. Rapaport. In More Games of No Chance. MSRI Publications 42 (2002), 307-315, Cambridge University Press. 2nd MSRI Combinatorial Games Theory Workshop, July 24-28, 2000, Berkeley, California, USA.

k-Pseudosnakes in large grids M. Matamala, E. Prisner and I. Rapaport. Proceedings of the 5th Latin American Theoretical Informatics Symposium (LATIN 2002), Lecture Notes in Computer Science 2286 (2002), 224-235, April 2-6, 2002, Cancun, Mexico.

Tiling groups for Wang tiles C. Moore, I. Rapaport and E. Remila. Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), 402-411, January 6-8, 2002, San Francisco, California, USA.

Global fixed point attractors of circular cellular automata and periodic tilings of the plane: undecidability results J. Mazoyer and I. Rapaport. Discrete Mathematics 199 (1999), 103-122. Editor's Choice Edition 1999. Cellular Automata Workshop 1997, September 25-27, 1997, Gargnano, Lago di Garda, Italy. Automata '98, December 10-12, 1998, Santiago, Chile.

Tiling allowing rotations only E. Goles and I. Rapaport. Theoretical Computer Science 218 (1999), 285-295. Polyominoes, Tilings and Cellular Automata: Journes d'Hiver a Caen, January 28-31, 1997, Caen, France.

Inducing an order on cellular automata by a grouping operation J. Mazoyer and I. Rapaport. Discrete Applied Mathematics 91 (1999), 177-196. Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science (STACS 1998), Lecture Notes in Computer Science 1373 (1998), 116-127, February 25-27, 1998, Paris, France.

Additive cellular automata over Zp and the bottom of (CA,<) J. Mazoyer and I. Rapaport. Proceedings of the 23rd Symposium on Mathematical Foundations of Computer Science (MFCS 1998), Lecture Notes in Computer Science 1450 (1998), 834-843, August 24-28, 1998, Brno, Czech Republic.

Complexity of tile rotation problems E. Goles and I. Rapaport. Theoretical Computer Science 188 (1997), 129-159.

Continuous modeling of metabolic networks with gene regulation in yeast and in vivo determination of rate parameters. P. Moisset, D. Vaisman, A. Cintolesi, J. Urrutia, I. Rapaport, B.A. Andrews and J. A. Asenjo. Biotechnology and Bioengineering 2012 Sep;109(9):2325-39.

A discrete mathematical model applied to genetic regulation and metabolic networks. J.A. Asenjo, P. Ramirez, I. Rapaport, J. Aracena, E. Goles and B.A. Andrews. J. Microbiology and Biotechnology Vol. 17, 2007, 3:496-510.

New approaches for predicting protein retention time in hydrophobic interaction chromatography. M.E. Lienqueo, A. Mahn, G. Navarro, T. Perez-Acle, C. Salgado, I. Rapaport and J. Asenjo. Journal of Molecular Recognition 2006 Jul-Aug; 19(4): 260-269.

Predicting the behaviour of proteins in hydrophobic interacton chromatography 2: Using a statistical description of their surface amino acid distribution. C. Salgado, I. Rapaport and J. Asenjo. Journal of Chromatography A, 1107, (2006), 120-129.

Predicting the behaviour of proteins in hydrophobic interacton chromatography 1: Using the hydrophobic imbalance (HI) to describe their surface amino acid distribution. C. Salgado, I. Rapaport and J. Asenjo. Journal of Chromatography A, 1107, (2006), 110-119.

Prediction of retention times of proteins in hydrophobic interaction chromatography using only their amino acid composition C. Salgado, I. Rapaport and J. Asenjo. Journal of Chromatography A, 1098 (2005), 44-154.

Is it possible to predict the average surface hydrophobicity of a protein using only its amino acid composition? C. Salgado, I. Rapaport and J. Asenjo. Journal of Chromatography A, 1075 (2005), 133-143.

students

benjamín jáuregui
current, PhD, mathematical modeling

antonia labarca
current, master, mathematical modeling

carlos antil
current, master, mathematical modeling

gary vidal
current, master, mathematical modeling

david cifuentes
current, master, mathematical modeling

francisco aliaga
2023, master, mathematical modeling

laura leal
2023, PhD, mathematical modeling

pablo paredes
2022, master, mathematical modeling

benjamín jáuregui
2022, master, mathematical modeling

iván zúñiga
2022, master, mathematical modeling

diego ramírez
2020, master, mathematical modeling

ian vidal
2019, master, mathematical modeling

sebastián pérez
2017, mathematical engineering

antonio lizama
2013, mathematical engineering

javiera urrutia
2013, mathematical engineering

pierre-etienne meunier
2012, PhD, mathematical modeling

raimundo briceño
2011, mathematical engineering

rodolfo carvajal
2006, mathematical engineering

cristian salgado
2005, PhD, chemical engineering

cristobal rojas
2004, mathematical engineering

teaching

mixed linear programming
2021

combinatorial algorithms
2023, 2022, 2019, 2017, 2016

graph theory
2015

optimization
2014

distributed computing
2022, 2020, 2018, 2016, 2014, 2012

combinatorial optimization
2010, 2008, 2004

probability
2023, 2019, 2013, 2012, 2010, 2009, 2008, 2007, 2005, 2003, 2002

introduction to algebra
2022, 2018, 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2007, 2005, 2003, 2002, 2001, 2000, 1999

linear algebra
2011, 2010, 2009, 2008, 2006, 2004, 2001, 2000, 1999

calculability and computational complexity
2020, 2006, 2003, 2001

communication complexity
2005, 2000

multivariable calculus
1999

grants

fondecyt PI
2022-2025

stic-amsud PI
2022-2024

fondecyt PI
2017-2021

fondef (deputy director)
2019-2021

núcleo PI
2014-2017

fondecyt PI
2013-2017

fondeccyt PI
2009-2013

anillo PI
2005-2008

fondecyt PI
2002-2005

fondecyt PI
1999-2002