Lunes	Martes	Miércoles	Jueves	Viernes
	Chair: Pedro Montealegre	Chair: Martín Ríos-Wilson	Chair: Dana Pizarro	Chair: Víctor Verdugo	Chair: Pedro Montealegre
8:30 – 9:00	Inscripción	Tareas	Tareas	Tareas	Tareas
9:00 – 10:15	Bonamy	Cohen-Addad	Vegh	Vegh	Bonamy
10:15 – 10:30	Coffee break	Coffee break	Coffee break	Coffee break	Coffee break
10:30 – 11:45	Trabajo	Trabajo	Trabajo	Trabajo	Trabajo
11:45 – 13:00	Cohen-Addad	Vegh	Bonamy		Actividad
13:00 – 15:00	Almuerzo	Almuerzo	Almuerzo	Almuerzo
15:00 – 16:15	Vegh	Bonamy	Cohen-Addad	Cohen-Addad
16:15 – 16:30	Coffee break	Coffee break	Coffee break	Coffee break
16:30 – 17:45	Trabajo	Trabajo	Trabajo	Trabajo
17:45 – 19:30	Actividad	Charla	Charla	Charla

Student talks

Speaker	Title
Gabriel Gorostiaga	Solving Techniques for Sudoku	Tuesday #1	17:45 – 18:10
Pablo Concha	On the Complexity of Stable and Biased Majority	Tuesday #2	18:15 – 18:40
Federica Cecchetto	Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	Wednesday #1	17:45 – 18:10
Javier Maass	A Hotelling-Downs game for strategic candidacy with binary issues.	Wednesday #2	18:15 – 18:40
Arturo Merino	From Combinatorial Optimization to Combinatorial Generation	Wednesday #3	18:45 – 19:10
Aleyah Dawkins	Edge condition for Hamiltonicity and chorded pancyclity in $K_{r+1}$-free graphs	Thursday #1	17:45 – 18:10
Bruno Bandeira	Recognizing Set Graphs by Computing Set Deficiencies	Thursday #2	18:15 – 18:40

Abstracts

Gabriel Gorostiaga (Universidad Nacional de Asunción)

Title: Solving Techniques for Sudoku

Abstract: Sudoku (Japanese: 数独, sūdoku) is a mathematical game invented in the late 1970s. It gained popularity in Japan in the 1980s and became widely known in 2005 when numerous newspapers started posting it in their hobby section.
The classic game consists of a grid of 9×9 cells divided into 9 blocks of 3×3 cells. Given a pattern of numbers, we aim to complete the grid with numbers from 1 to 9, keeping in mind that each group (row, column, or block) must contain those numbers without repetition. The game ends when the grid is completed with all the correct numbers.
The game’s solution is mainly related to Graph Theory, but we will be focusing on the logic behind solving this game manually. We will run through basic to advanced techniques for solving Sudoku.

Pablo Concha (Universidad Adolfo Ibañez)

Title: On the Complexity of Stable and Biased Majority

Abstract: A majority automata is a two-state cellular automata, where each cell updates its state according to the most represented state in its neighborhood. A question that naturally arises in the study of these dynamical systems asks whether there exists an efficient algorithm that can be implemented in order to compute the state configuration reached by the system at a given time-step. This problem is called the prediction problem. In this work, we study the prediction problem for a more general setting in which the local functions can be different according to their behavior in tie cases. We define two types of local rules: the stable majority and biased majority. The first one remains invariant in tie cases, and the second one takes the value 1. We call this class the heterogeneous majority cellular automata (HMCA). For this latter class, we prove that in two or more dimensions, the problem is P-Complete as a consequence of the capability of the system of simulating Boolean circuits.

Federica Cecchetto (ETH Zurich)

Title: Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches

Abstract: We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area of Survivable Network Design. It is about increasing the edge-connectivity of a graph by one unit in the cheapest possible way. More precisely, given a k-edge-connected graph G=(V,E) and a set of extra edges, the task is to find a minimum cardinality subset of extra edges whose addition to G makes the graph (k+1)-edge-connected. If k is odd, the problem is known to reduce to the Tree Augmentation Problem (TAP)—i.e., G is a spanning tree—for which significant progress has been achieved recently, leading to approximation factors below 1.5 (the currently best factor is 1.458). However, advances on TAP did not carry over to CAP so far. Indeed, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain the first approximation factor below 2 for CAP by presenting a 1.91-approximation algorithm based on a method that is disjoint from recent advances for TAP.
We first bridge the gap between TAP and CAP, by presenting techniques that allow for leveraging insights and methods from TAP to approach CAP. We then introduce a new way to get approximation factors below 1.5, based on a new analysis technique. Through these ingredients, we obtain a 1.393-approximation algorithm for CAP, and therefore also for TAP. This leads to the currently best approximation result for both problems in a unified way, by significantly improving on the above-mentioned 1.91-approximation for CAP and also the previously best approximation factor of 1.458 for TAP by Grandoni, Kalaitzis, and Zenklusen (STOC 2018). Additionally, a feature we inherit from recent TAP advances is that our approach can deal with the weighted setting when the ratio between the largest to smallest cost on extra links is bounded, in which case we obtain approximation factors below 1.5.

 

Javier Maass (Universidad de Chile)

Title: A Hotelling-Downs game for strategic candidacy with binary issues.

Abstract: In a pre-election period, candidates may, in the course of the public political campaign, adopt a populist behavior by modifying their advertised political views, to obtain a better outcome in the election. This situation can be modeled by a type of strategic candidacy game, close to the Hotelling-Downs framework, which has been investigated in previous works via political views that are positions in a common one-dimensional axis. However, the left right axis cannot always capture the actual political stances of candidates. Therefore, we propose to model the political views of candidates as opinions over binary issues (e.g., for or against higher taxes, abortion, etc.), implying that the space of possible political views can be represented by a hypercube whose dimension is the number of issues. In this populism game, we introduce the notion of local equilibrium, broader than the Nash equilibrium, which is a stable state with respect to candidates that can change their view on at most a given number of issues. We study the existence of local equilibria in the populism game and identify natural conditions under which the existence of an equilibrium is guaranteed. To complement our theoretical results, we provide experiments to empirically evaluate the existence of local equilibria and their quality.

Arturo Merino (TU Berlin)

Title: From Combinatorial Optimization to Combinatorial Generation. 

Abstract:  Combinatorial generation is the task of computing all solutions to a combinatorial problem instead of only one of them. For example, we may be interested in all spanning trees of a given graph or all optimal weight perfect matchings of a given weighted graph. In recent years, there has been much interest in unifying techniques or general approaches that simultaneously apply to various combinatorial generation problems.

We propose a new simple general approach for combinatorial generation. Given some binary strings X⊆{0,1}ⁿ, our approach consists of computing a Hamilton path in a polytope with X as vertices, namely conv(X). Our main result shows that this approach works for all X⊆{0,1}ⁿ and is efficient whenever optimization over X can be efficiently solved, showing an unexplored relation between combinatorial optimization and generation. More specifically, if we can solve certain linear optimization problems for X in time O(T), we can compute a Hamilton path in conv(X) in roughly O(T⋅log(n)) time per vertex.

As a consequence, we obtain new efficient algorithms for combinatorial generation problems that can be binary encoded, like spanning tree generation, 0/1 vertex enumeration, and perfect matching generation. Furthermore, consecutive objects visited by our generation algorithms differ only in a local operation, like an edge exchange in the case of spanning trees or an alternating cycle exchange in the case of perfect matchings.

Aleyah Dawkins (George Mason University)

Title: Edge condition for Hamiltonicity and chorded pancyclity in $K_{r+1}$-free graphs

Abstract: In this talk, we discuss a new result on an edge density condition sufficient to imply Hamiltonicity and chorded pancyclicity in $K_{r+1}$-free graphs. The problem of determining the extremal number $\ex(n,F)$, the maximum number of edges in an $n$-vertex, $F$-free graph, has been studied extensively since T\'{u}ran’s theorem. The first edge density condition implying Hamiltonicity is due to Ore, and variations on this problem have been studied since. In 2018, Ferrero and Lesniak determined the edge density condition implying Hamiltonicity in $r$-partite graphs with given part sizes. Our main theorem brings these two themes together, and can be viewed as determining $\ex(n,\{K_{r+1},C_n\})$ and the edge density condition implying Hamiltonicity for $K_{r+1}$-free graphs. This talk is based on preliminary joint work with Rachel Kirsch.

Bruno Bandeira (Universidade Federal do Rio de Janeiro)

Title: Recognizing Set Graphs by Computing Set Deficiencies

Abstract: A set graph is a graph admitting an extensional acyclic orientation, where an orientation is extensional if different vertices have different out-neighborhoods. The set graph recognition problem was first considered and proved to be NP-complete by A. Tomescu in 2012. In this work, we introduce two concepts that can be used for the efficient recognition of set graphs in some classes of graphs. We define layered extensional acyclic orientations and a graph parameter, called set-deficiency, that measures how far a graph is from being a set graph. Then, we describe how these concepts can be applied to recognize set graphs in the class of cographs in polynomial time.

Official group photo.