LATIN 2020 Theoretical Informatics 14th Latin American Symposium São Paulo Brazil January 5 8 2021 Proceedings Yoshiharu Kohayakawa

Approximation Algorithms

PTAS for Steiner Tree on Map Graphs

Near-Linear Time Algorithm for Approximate Minimum Degree Spanning Trees

Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations

Scheduling on Hybrid Platforms: Improved Approximability Window

Leafy Spanning Arborescences in DAGs

Approximating Routing and Connectivity Problems with Multiple Distances

A 2-Approximation for the k-Prize-Collecting Steiner Tree Problem

Parameterized Algorithms

Maximizing Happiness in Graphs of Bounded Clique-Width

Graph Hamiltonicity Parameterized by Proper Interval Deletion Set

Graph Square Roots of Small Distance from Degree One Graphs

Structural Parameterizations for Equitable Coloring

Algorithms and Data Structures

Dynamically Optimal Self-adjusting Single-Source Tree Networks

Batched Predecessor and Sorting with Size-Priced Information in External Memory

Probabilistically Faulty Searching on a Half-Line

Query Minimization Under Stochastic Uncertainty

Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries

Towards a Definitive Measure of Repetitiveness

Computational Geometry

Flips in Higher Order Delaunay Triangulations

An Lower Bound on the Number of Cell Crossings for Weighted Shortest Paths in 3-Dimensional Polyhedral Structures

Computing Balanced Convex Partitions of Lines

Ordered Strip Packing

Shortest Rectilinear Path Queries to Rectangles in a Rectangular Domain

Farthest Color Voronoi Diagrams: Complexity and Algorithms

Rectilinear Convex Hull of Points in 3D

Complexity Theory

Monotone Circuit Lower Bounds from Robust Sunflowers

Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions

Sherali-Adams and the Binary Encoding of Combinatorial Principles

Hardness of Variants of the Graph Coloring Game

Tractable Unordered 3-CNF Games

Quantum Computing

Lower Bounds for Testing Complete Positivity and Quantum Separability

Exponential-Time Quantum Algorithms for Graph Coloring Problems

Neural Networks and Biologically Inspired Computing

On Symmetry and Initialization for Neural Networks

How to Color a French Flag

Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model

Randomization

Transmitting once to Elect a Leader on Wireless Networks

Asymptotics for Push on the Complete Graph

The Hardness of Sampling Connected Subgraphs

Combinatorics

Lower Bounds for Max-Cut via Semidefinite Programming

Quasi-Random Words and Limits of Word Sequences

Thresholds in the Lattice of Subspaces of

Analytic and Enumerative Combinatorics

On Minimal-Perimeter Lattice Animals

Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes

On the Collection of Fringe Subtrees in Random Binary Trees

A Method to Prove the Nonrationality of Some Combinatorial Generating Functions

Binary Decision Diagrams: From Tree Compaction to Sampling

Graph Theory

Graph Sandwich Problem for the Property of Being Well-Covered and Partitionable into k Independent Sets and Cliques

On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number

Steiner Trees for Hereditary Graph Classes

On Some Subclasses of Split -EPG Graphs

On the Helly Subclasses of Interval Bigraphs and Circular Arc Bigraphs