Marcos A. Kiwi

According to our database, Marcos A. Kiwi authored at least 44 papers between 1992 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Naively Sorting Evolving Data is Optimal and Robust.

George Giakkoupis, Marcos Kiwi, Dimitrios Los

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Label propagation on binomial random graphs.

Marcos Kiwi, Lyuben Lichev, Dieter Mitsche, Pawel Pralat

CoRR, 2023

2022

Cover and Hitting Times of Hyperbolic Random Graphs.

Marcos Kiwi, Markus Schepers, John Sylvester

Proceedings of the Approximation, 2022

2020

A perspective on theoretical computer science in Latin America.

Marcos Kiwi, Yoshiharu Kohayakawa, Sergio Rajsbaum, Francisco Rodríguez-Henríquez, Jayme Luiz Szwarcfiter, Alfredo Viola

Commun. ACM, 2020

Quasi-Random Words and Limits of Word Sequences.

Hiêp Hàn, Marcos Kiwi, Matías Pavez-Signé

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

2019

On the Second Largest Component of Random Hyperbolic Graphs.

Marcos A. Kiwi, Dieter Mitsche

SIAM J. Discret. Math., 2019

2017

FIFO Queues Are Bad for Rumor Spreading.

Marcos A. Kiwi, Christopher Thraves Caro

IEEE Trans. Inf. Theory, 2017

2016

Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations.

Andrea Jiménez, Marcos A. Kiwi

Discret. Appl. Math., 2016

Repetition-free longest common subsequence of random sequences.

Cristina G. Fernandes, Marcos A. Kiwi

Discret. Appl. Math., 2016

2015

Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays.

Marcos A. Kiwi, José A. Soto

Comb. Probab. Comput., 2015

Adaptive Rumor Spreading.

José Correa, Marcos A. Kiwi, Neil Olver, Alberto Vera

Proceedings of the Web and Internet Economics - 11th International Conference, 2015

A Bound for the Diameter of Random Hyperbolic Graphs.

Marcos A. Kiwi, Dieter Mitsche

Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, 2015

2014

Strict Majority Bootstrap Percolation in the r-wheel.

Marcos A. Kiwi, Pablo Moisset de Espanés, Ivan Rapaport, Sergio Rica, Guillaume Theyssier

Inf. Process. Lett., 2014

Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings.

Andrea Jiménez, Marcos A. Kiwi

Discret. Appl. Math., 2014

2011

Counting perfect matchings in the geometric dual.

Andrea Jiménez, Marcos A. Kiwi

Electron. Notes Discret. Math., 2011

Computational Hardness of Enumerating Satisfying Spin-Assignments in Triangulations

Andrea Jiménez, Marcos A. Kiwi

CoRR, 2011

Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs

Marcos A. Kiwi, José A. Soto

CoRR, 2011

2010

Satisfying States of Triangulations of a Convex n-gon.

Andrea Jiménez, Marcos A. Kiwi, Martin Loebl

Electron. J. Comb., 2010

2009

Adversarial queuing theory with setups.

Marcos A. Kiwi, Mauricio Soto, Christopher Thraves

Theor. Comput. Sci., 2009

On a Speculated Relation Between Chvátal-Sankoff Constants of Several Sequences.

Marcos A. Kiwi, José A. Soto

Comb. Probab. Comput., 2009

2008

Towards the Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs.

Marcos A. Kiwi, Martin Loebl

Electron. J. Comb., 2008

Foreword.

José R. Correa, Marcos A. Kiwi

Algorithmica, 2008

Strong Accumulators from Collision-Resistant Hashing.

Philippe Camacho, Alejandro Hevia, Marcos A. Kiwi, Roberto Opazo

Proceedings of the Information Security, 11th International Conference, 2008

On-Line Approximate String Matching with Bounded Errors.

Marcos A. Kiwi, Gonzalo Navarro, Claudio Telha

Proceedings of the Combinatorial Pattern Matching, 19th Annual Symposium, 2008

2006

A concentration bound for the longest increasing subsequence of a randomly chosen involution.

Marcos A. Kiwi

Discret. Appl. Math., 2006

Adversarial Queueing Theory Revisited.

Marcos A. Kiwi

Proceedings of the Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), 2006

2004

The chilean highway problem.

Marcos A. Kiwi, Alexander Russell

Theor. Comput. Sci., 2004

Expected Length of the Longest Common Subsequence for Large Alphabets.

Marcos A. Kiwi, Martin Loebl, Jirí Matousek

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

2003

Algebraic testing and weight distributions of codes.

Marcos A. Kiwi

Theor. Comput. Sci., 2003

Approximate testing with error relative to input size.

Marcos A. Kiwi, Frédéric Magniez, Miklos Santha

J. Comput. Syst. Sci., 2003

2002

Largest planar matching in random bipartite graphs.

Marcos A. Kiwi, Martin Loebl

Random Struct. Algorithms, 2002

Electronic Jury Voting Protocols.

Alejandro Hevia, Marcos A. Kiwi

Proceedings of the LATIN 2002: Theoretical Informatics, 2002

2000

Threshold data structures and coding theory.

Eric Bach, Marcos A. Kiwi

Theor. Comput. Sci., 2000

Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey.

Marcos A. Kiwi, Frédéric Magniez, Miklos Santha

Proceedings of the Theoretical Aspects of Computer Science, 2000

1999

Approximate Testing with Relative Error.

Marcos A. Kiwi, Frédéric Magniez, Miklos Santha

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

Strength of Two Data Encryption Standard Implementations under Timing Attacks.

Alejandro Hevia, Marcos A. Kiwi

Proceedings of the LATIN '98: Theoretical Informatics, 1998

Min-Max-Boundary Domain Decomposition.

Marcos A. Kiwi, Daniel A. Spielman, Shang-Hua Teng

Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

1997

Testing and Weight Distributions of Dual Codes

Marcos A. Kiwi

Electron. Colloquium Comput. Complex., 1997

1995

Linearity Testing in Characteristic Two.

Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

No Polynomial Bound for the Period of the Parallel Chip Firing Game on Graphs.

Marcos A. Kiwi, René Ndoundam, Maurice Tchuenté, Eric Goles Ch.

Theor. Comput. Sci., 1994

Alternation in Interaction.

Marcos A. Kiwi, Carsten Lund, Alexander Russell, Daniel A. Spielman, Ravi Sundaram

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

Games on Line Graphs and Sand Piles.

Eric Goles Ch., Marcos A. Kiwi

Theor. Comput. Sci., 1993

1992

A lower bound on the computational complexity of the QR decomposition on a shared memory SIMD computer.

Eric Goles Ch., Marcos A. Kiwi

Parallel Comput., 1992

Dynamics of Sand-Piles Games on Graphs.

Eric Goles Ch., Marcos A. Kiwi

Proceedings of the LATIN '92, 1992