The creative use of abstractions is central to computer science. But not all abstractions address the same kinds of problems. We identify four different reasons abstractions appear in computer-science theory, and focus on the "declarative abstractions," whose purpose is to raise the level at which we program. Important declarative abstractions appear in the theory of compiling and the theory of databases. We shall touch on the most important elements in those two fields.

Reversible computation has been studied for over 60 years as a way to evade fundamental physical limits on the power needed for irreversible computational steps, and because quantum computing circuits are necessarily reversible. We study a class of problems based on computing the iterated values of a reversible function. The story leads through Thomason's lollipop algorithm in graph theory, circuit complexity, and reversible cellular automata, to card shuffling, the reflections of light in jewels, and curves on topological surfaces, and involves both PSPACE-hard problems and problems with unexpected polynomial-time algorithms.

Following the immense recent advances in distributed networks, the explosive growth of the Internet, and our increased dependency on these infrastructures, guaranteeing the uninterrupted operation of communication networks has become a major objective in network algorithms. The modern instantiations of distributed networks, such as the Bitcoin network and cloud computing, introduce new security challenges that deserve urgent attention in both theory and practice. In this talk, I will present a unified framework for obtaining fast, resilient and secure distributed algorithms for fundamental graph problems. Our approach is based on a graph-theoretic perspective in which common notions of resilient requirements are translated into suitably tailored combinatorial graph structures. We will discuss recent developments along the following two lines of research: - Designing distributed algorithms that can handle various adversarial settings, such as, node crashes and Byzantine attacks. We will mainly provide general compilation schemes that are based on exploiting the high-connectivity of the graph. Our key focus will be on the efficiency of the resilient algorithms in terms of the number of communication rounds. - Initiating and establishing the theoretical exploration of security in distributed graph algorithms. Such a notion has been addressed before mainly in the context of secure multi-party computation (MPC). The heart of our approach is to develop new graph theoretical infrastructures to provide graphical secure channels between nodes in a communication network of an arbitrary topology. Finally, I will highlight future directions that call for strengthening the connections between the areas of fault tolerant network design, distributed graph algorithms and information theoretic security.

Abstract: Following the immense recent advances in distributed networks, the explosive growth of the Internet, and our increased dependency on these infrastructures, guaranteeing the uninterrupted operation of communication networks has become a major objective in network algorithms. The modern instantiations of distributed networks, such as the Bitcoin network and cloud computing, introduce new security challenges that deserve urgent attention in both theory and practice. In this talk, I will present a unified framework for obtaining fast, resilient and secure distributed algorithms for fundamental graph pproblems. Our approach is based on a graph-theoretic perspective in which common notions of resilient requirements are translated into suitably tailored combinatorial graph structures. We will discuss recent developments along the following two lines of research:

• Designing distributed algorithms that can handle various adversarial settings, such as, node crashes and Byzantine attacks. We will mainly provide general compilation schemes that are based on exploiting the high-connectivity of the graph. Our key focus will be on the efficiency of the resilient algorithms in terms of the number of communication rounds.
• Initiating and establishing the theoretical exploration of security in distributed graph algorithms. Such a notion has been addressed before mainly in the context of secure multi-party computation (MPC). The heart of our approach is to develop new graph theoretical infrastructures to provide graphical secure channels between nodes in a communication network of an arbitrary topology.

Finally, I will highlight future directions that call for strengthening the connections between the areas of fault tolerant network design, distributed graph algorithms and information theoretic security.

The 15th Latin American Theoretical Informatics Symposium will be held in Guanajuato, Mexico.

More information about meeting can be found at https://pakal.cs.cinvestav.mx/latin2022/.

Call for Papers for LATIN 2022

Dates

All deadlines are at 23:59 anywhere on earth.

Abstract Submission (extended)

May 27, 2022

Full Paper Submission (extended)

May 30, 2022

Notification

July 29, 2022

Camera Ready

August 19, 2022

Symposium

November 7–11, 2022

Scope and Topics

LATIN is devoted to different areas in theoretical computer science including, but not limited to: algorithms (approximation, online, randomized, algorithmic game theory, etc.), analytic combinatorics and analysis of algorithms, automata theory and formal languages, coding theory and data compression, combinatorial algorithms, combinatorial optimization, combinatorics and graph theory, complexity theory, computational algebra, computational biology, computational geometry, computational number theory, cryptology, databases and information retrieval, data structures, formal methods and security, foundations of data science and theoretical machine learning, Internet and the web, parallel and distributed computing, pattern matching, programming language theory, quantum computing, and random structures.

Submission

Papers are to be submitted in PDF format using the EasyChair server (https://easychair.org/conferences/?conf=latin2022).

Submissions are limited to fifteen (15) single-column letter-size pages in Springer LNCS format (see LNCS author guidelines at http://www.springer.com/la/computer-science/lncs/conference-proceedings-guidelines). This limit does not include references. An optional appendix (to be read at the program committee's discretion) may be included if desired. Simultaneous submission of papers to any other conference with published proceedings, as well as the submission of previously published papers, is not allowed. Papers must be written in English. If there is a physical meeting, as hoped for, for each accepted paper at least one author must register and attend the symposium to present it. Moreover, an author cannot register for multiple papers. That is, each accepted paper must have its own registrant. An exception will be made if a group of one or more authors has more papers accepted than group members.

Proceedings

Accepted papers will appear in the proceedings of LATIN, which will be published in Springer Lecture Notes in Computer Science (http://www.springer.com/la/computer-science/lncs).

Algorithmica Special Issue

A Special Issue of ALGORITHMICA will be dedicated to selected paper of LATIN 2022.

Imre Simon Test of Time Award

As of 2012, the Imre Simon Test-of-Time Award is given to the LATIN paper deemed most influential among all those published at least ten years prior to the current edition of the conference. Papers published in the LATIN proceedings up to and including 2010 are eligible for the 2022 award.

Best Paper Award

Papers presented at the conference will be considered for the LATIN 2022 Alejandro Lopez-Ortiz Best Paper Award.

COVID-19 Pandemic

The state of the COVID-19 pandemic in October 2022 cannot be predicted now. We will do our best to have a meeting in person, but it may happen that some or all attendees participate online. Questions can be sent to: Latinconferenciachair2022@delta.cs.cinvestav.mx.

Conference Chair

Francisco Rodríguez Henríquez, Centro de investigación y de Estudios Avanzados, México. Cryptography Research Centre, TII, Abu Dhabi, United Arab Emirates.

Program Committee

• Martin Aumüller, University of Copenhagen, Denmark
• Jérémy Barbay, Universidad de Chile, Chile
• Leonid Barenboim, The Open University of Israel, Israel
• Frédérique Bassino, Université Sorbonne Paris Nord, France
• Luciana Buriol, Amazon, USA
• Armando Castañeda, Universidad Nacional Autónoma de México, Mexico (Chair)
• Witold Charatonik, University of Wrocław, Poland
• Min Chih Lin, Universidad de Buenos Aires, Argentina
• Amalia Duch Brown, Universitat Politècnica de Catalunya, Spain
• Leah Epstein, University of Haifa, Israel
• Martín Farach-Colton, Rutgers University, USA
• Esteban Feuerstein, Universidad de Buenos Aires, Argentina
• David Flores-Peñaloza, Universidad Nacional Autónoma de México, Mexico
• Fedor Fomin, University of Bergen, Norway
• Jesper Jansson, Kyoto University, Japan
• Gabriela Jeronimo, Universidad de Buenos Aires, Argentina
• Christos Kaklamanis, University of Patras & CTI "Diophantus", Greece
• Shuji Kijima, Kyushu University, Japan
• Gregory Kucherov, CNRS/LIGM, France
• François Le Gall, Nagoya University, Japan
• Jérémy Ledent, University of Strathclyde, UK
• Reut Levi, IDC Herzliya, Israel
• Giovanni Manzini, Università di Pisa, Italy
• Andrea Marino, Università degli Studi di Firenze, Italy
• Elvira Mayordomo, Universidad de Zaragoza, Spain
• Marco Molinaro, Pontifical Catholic University of Rio de Janeiro, Brazil
• Guilherme Oliveira Mota, Universidade de São Paulo, Brazil
• Lucia Moura, University of Ottawa, Canada
• Gonzalo Navarro, Universidad de Chile, Chile
• Rafael Oliveira, University of Waterloo, Canada
• Daniel Panario, Carleton University, Canada
• Gopal Pandurangan, University of Houston, USA
• Seth Pettie, University of Michigan, USA
• Miguel A. Pizaña, Universidad Autónoma Metropolitana, Mexico
• Igor Potapov, University of Liverpool, UK
• Svetlana Puzynina, Sobolev Institute of Mathematics, Russia
• Pablo Rotondo, Université Gustave Eiffel, France
• Jared Saia, University of New Mexico, USA
• Rodrigo I. Silveira, Universitat Politècnica de Catalunya, Spain
• Mohit Singh, Georgia Tech, USA
• José A. Soto, Universidad de Chile, Chile
• Frank Stephan, National University of Singapore, Singapore
• Martin Strauss, University of Michigan, USA
• Subhash Suri, University of California, USA
• Dimitrios M. Thilikos, LIRMM, Université de Montpellier, CNRS, Montpellier, France
• Christopher Thraves, Universidad de Concepción, Chile
• Denis Trystram, Université de Grenoble Alpes, France
• Seeun William Umboh, The University of Sydney, Australia
• Jorge Urrutia, Universidad Nacional Autónoma de México, Mexico
• Alfredo Viola, Universidad de la República, Uruguay
• Mikhail V. Volkov, Ural Federal University, Russia
• Sebastian Wild, University of Liverpool, UK
• Georg Zetzsche, Max Planck Institute, Germany

Organizing Committee

• Mariano Rivera Meraz, CIMAT, Guanajuato, México (Organizing Committee chair)
• Édgar Leonel Chávez González, CICESE, Ensenada, México (Tutorial chair)
• Tássio Naia, Universidade de São Paulo, Brazil (Publicity Chair)

Steering Committee

• Michael A. Bender, Stony Brook University, USA
• Cristina G. Fernandes, Universidade de São Paulo, Brazil
• Joachim von zur Gathen, Bonn-Aachen International Center for Information Technology, Germany
• Evangelos Kranakis, Carleton University, Canada
• Conrado Martínez, Universitat Politècnica de Catalunya, Spain
• Flávio Keidi Miyazawa, Universidade Estadual de Campinas, Brazil

^*  Authors with n affiliations contributes 1/n to each affiliation.
^** Papers with n authors contribute 1/n to each affiliation.

^*  Authors with n affiliations contributes 1/n to each affiliation.
^** Papers with n authors contribute 1/n to each affiliation.

Africa

Australia & Asia

Europe

Latin-America

Middle East

USA & Canada