# 1st Annual Scientific Meeting of Computer Science Institute of Charles University and Institute for Theoretical Computer Science (CE-ITI)

All lectures are at Academy of Performing Arts in Prague, Malostranské nám. 13, hall Galerie## Program

### Thursday, December 13

10:00 | Cliff Stein | Resource Cost Aware Scheduling |
---|---|---|

10:45 | Michal Koucky | Computing error-correcting codes by bounded-depth circuits |

11:30 | Martin Loebl | On Rota's bases conjecture |

12:15 | Lunch at the faculty building | |

14:00 | Alberto Marchetti Spaccamela | Sporadic Real-Time Multiprocessor Task Systems |

14:45 | Jan Obdržálek | From trees to shrubs and m-partite cographs |

15:15 | Petr Hliněný | When MSO and FO logics express the same |

### Friday, December 14

9:30 | Kirk Pruhs | Optimal Energy Trade-off Schedules |
---|---|---|

10:15 | Ondřej Pangrác | Coloring Eulerian triangulations of the Klein Bottle |

10:40 | Petr Kučera | Propagation Complete Formulas |

11:05 | Pavel Surynek | Cooperative path finding for multiple robots |

11:30 | Roman Čada | On the equivalence of Jackson's and Thomassen's conjectures |

12:15 | lunch at the faculty building | |

14:00 | Nikhil Bansal | Semidefinite Optimization in Discrepancy Theory |

14:40 | Michel Habib | On some graph problems in biology |

15:20 | Rostislav Horčík | Algebraic methods from substructural logics and formal languages |

15:50 | Gabor Kun | Constraint Satisfaction Problems and expander relational structures |

16:30 | Patrice Ossona de Mendez | A Model Theory Approach to Structural Limits |

## Abstracts

### Cliff Stein: Resource Cost Aware Scheduling

(joint work with Rodrigo Carrasco and Garud Iyengar)

There has been much recent work on energy aware scheduling, in which the energy used to process each job is also accounted for in the total cost. Extending this idea outside of the CPU setting, we consider the case where there are several different resources that determine the speed at which a jobs runs, and we have to pay depending on the amount/level of each resource that we use. This work is also an extension of the resource dependent job processing time problem.

In this talk, we will discuss some of the applications in this more general model, and then give new constant-factor approximation algorithms for resource cost aware scheduling problems, where the objective is to minimize the sum of the total cost of resources consumed and the total weighted completion time in the one machine non-preemptive setting, allowing for arbitrary precedence constraints and also release dates. We introduce a generalization of an interval-index linear program, and then show how to use the lp solution to obtain both an ordering of the jobs, and a speed at which to run.

We will also discuss some preliminary experimental work.

### Michal Koucky: Computing error-correcting codes by bounded-depth circuits

(joint work with A. Gal, K.A. Hansen, P. Pudlak and E. Viola)

In this talk I will present our recent results on computing error- correcting codes by bounded-depth circuits with arbitrary gates. We study the minimum number w of wires needed to compute any (asymptotically good) error-correcting code C:{0,1}^Omega(n) -> {0,1}^n with minimum distance Omega(n), using unbounded fan-in circuits of depth d with arbitrary gates. We show nearly linear upper bounds as well as matching lower bounds.

To prove our lower bounds we exhibit a connection between circuits computing the error-correcting codes and a new class of superconcentrator-like graphs with connectivity properties distinct from previously studied ones.

Our upper bounds imply that a (necessarily dense) generator matrix for the code can be written as the product of two sparse matrices. The upper bounds are non-explicit: we show the existence of circuits (consisting of only XOR gates) computing good codes within the stated bounds.

Using a result by Ishai, Kushilevitz, Ostrovsky, and Sahai (2008) we also obtain similar bounds for computing pairwise-independent hash functions.

### Martin Loebl: On Rota's bases conjecture

(joint work with Ron Aharoni)

Longstanding Rota's bases conjecture reads as follows: given n non-singular real matrices M_1,..., M_n, one can always find decomposition of their column-sets into n transversals so that each of them also forms a non-singular matrix. About 20 years ago, it was proved that for n even, Alon-Tarsi latin squares conjecture implies the Rota's bases conjecture. We (with Ron Aharoni) prove that another conjecture on latin squares implies Rota's conjecture for n odd. The starting point is a non-commutative version of a formula of Shmuel Onn.

### Alberto Marchetti Spaccamela: Sporadic Real-Time Multiprocessor Task Systems

The sporadic task model is a model of recurrent processes in hard real-time systems that has received great attention in the last years. A sporadic task \tau(i) = (C(i),D(i),P(i)) is characterized by a worst-case execution time C(i) , a relative deadline D(i) , and a minimum interarrival separation P(i) . Such a sporadic task generates a potentially infinite sequence of jobs: each job arrives at an unpredictable time, after the minimum separation P(i) from the last job of the same task has elapsed; it has an execution requirement less than or equal to C(i) and a deadline that occurs D(i) time units after its arrival time. A sporadic task system T is a collection of such sporadic tasks. Since the actual interarrival times can vary, there are infinitely many job sequences that can be generated by T.

We will present two results for sporadic task systems on a multiprocessor platform. We give the first algorithm for testing the feasibility of a system of sporadic real-time tasks on a set of identical processors by casting the problem as 2 people game. We also investigate the related notion of schedulability and a notion of online feasibility. Then we consider the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of approximately 12.9; in the proof we introduce a rounding technique that might be of independent interest.

### Jan Obdržálek: From trees to shrubs and m-partite cographs

(joint work with Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Patrice Ossona de Mendez, and Reshma Ramadurai)

Our goal is to extend the notion of tree-depth towards more rich classes of graphs, like those of bounded clique-width, while preserving at least some of the nice algorithmic properties of tree-depth. We introduce the notion of shrub-depth of a graph class and show that MSO1 model checking is fast for classes of bounded shrub-depth. Moreover, we also show that shrub-depth exactly characterizes the graph classes having an interpretation in coloured trees of bounded height. Additionally we introduce a common extension of cographs and of graphs with bounded shrub-depth - m-partite cographs (still of bounded clique-width), which are well quasi-ordered by the relation "is an induced subgraph of" and therefore allow polynomial time testing of hereditary properties.

### Petr Hliněný: When MSO and FO logics express the same

(joint work with Jakub Gajarsky)

We show that FO logic has the same expressive power as MSO1 (quantifying over vertex sets in a graph) on every graph class of bounded shrub-depth. This extends some recent work of Elberfeld, Grohe, and Tantau.

### Kirk Pruhs: Optimal Energy Trade-off Schedules

(joint work with Neal Barcelo, Daniel Cole, Dimitrios Letsios, Michael Nugent)

We consider scheduling tasks that arrive over time on a speed scalable processor. At each time a schedule specifies a job to be run and the speed at which the processor is run. Processors are generally less energy efficient at higher speeds. We seek to understand the structure of schedules that optimally trade-off the energy used by the processor with a common scheduling quality of service measure, fractional weighted delay. We assume that there is some user defined parameter \beta specifying the user?s desired additive trade-off between energy efficiency and quality of service. We prove that the optimal energy trade-off schedule is essentially unique, and has a simple structure. Thus it is easy to check the optimality of a schedule. We further prove that the optimal energy trade-off schedule changes continuously as a function of the parameter \beta. Thus it is possible to compute the optimal energy trade-off schedule using a natural homotopic optimization algorithm. We further show that multiplicative trade-off schedules have fewer desirable properties. I will try to highlight several intriguing open problems exposed by this research.

### Ondřej Pangrác: Coloring Eulerian triangulations of the Klein Bottle

(joint work with D. Kral, B. Mohar, A. Nakamoto, Y. Suzuki)

We prove that an Eulerian triangulation of the Klein bottle has chromatic number at most five unless it contains a complete graph of order six as a subgraph. As a consequence of our proof, we derive that every Eulerian triangulation of the Klein bottle with face-width at least four is 5-colorable.

### Petr Kučera: Propagation Complete Formulas

(joint work with Martin Babka, Tomáš Balyo, Ondřej Čepek, Štefan Gurský and Václav Vlček)

The notion of propagation complete formulas was introduced in Knowledge compilation with empowerment. L. Bordeaux and J. Marques-Silva, SOFSEM 2012. A CNF formula F is propagation complete if after any partial substitution of truth values all logically entailed literals can be inferred from the resulting formula by unit propagation. The process which turns a CNF formula F into an equivalent propagation CNF formula F' is one of many ways of knowledge compilation. The key to this process is detecting the so called empowering implicates. Propagation complete formulas have connections to modern day SAT solvers based on CDCL (where the empowering implicates are used to enhance the original formula to make further search easier) and to CSP (where the CNF propagator for a constraint has to be propagation complete). In this talk we shall study several properties of propagation complete formulas with focus on complexity of the problems connected to this class of formulas. The main problems we study is how hard is to recognize whether given formula is propagation complete and how many implicates has to added to a formula to make it propagation complete. We also study the properties of empowering implicates some of which follow from the properties of modern day SAT solvers based on CDCL.

### Pavel Surynek: Cooperative path finding for multiple robots

Consider a group of robots that are moving in a certain environment. Each robot is given its initial and goal location. The task of finding a sequence of moves for each robot such that it eventually reaches the given goal location by following this path is known as cooperative path finding (CPF). The interaction among robots is given by the requirement that they must not collide with each other. The CPF problem can be abstracted as a problem of motion on a graph where the graph represents the environment and robots are placed in vertices of the graph with at most one robot in a vertex. Complete and incomplete algorithms for solving the CPF problem and their properties will be discussed.

### Roman Čada: On the equivalence of Jackson's and Thomassen's conjectures

### Nikhil Bansal: Semidefinite Optimization in Discrepancy Theory

The concept of discrepancy is intimately related to several fundamental topics in mathematics and theoretical computer science, and deals with the following type of question: Given a collection of sets on some elements, color each element red or blue such that each set in the collection is colored as evenly as possible.

Recently, there have been several new developments in discrepancy theory based on connections to semidefinite programming. In this talk, I will give a brief survey of discrepancy theory and these developments, focusing on the main ideas and the techniques involved.

### Michel Habib: On some graph problems in biology

I will present several graph problems coming from Biology, I was involved in the last years. All these problems are related with phylogeny and genes comparisons, but they were a lot of combinatorial differences.

In bioinformatics there is a need to develop efficient algorithms to analyze huge data sets coming containing errors from genome of many organisms. I will first present the notion of common interval between genes sequences and how it leads to very nice algorithmic questions on graphs.

Then I will describe variations on computations of phylogenetic tress and their relationships with chordal graphs. These leads to leaf power graphs, unique minimal sandwich problems and phylogenetic networks. In fact some Biologists now consider phylogenetics networks rather than phylogenetic trees. Unfortunately moving from trees to networks (even if we ask for constraints on their cycles, for example that they do not overlap) makes things much more difficult from a graph theory point of view. Finally we end by some clustering problems on bipartite graphs.

### Rostislav Horčík: Algebraic methods from substructural logics and formal languages

A canonical way to assign to a given logic a correct and complete algebraic semantics, involves the construction of Lindenbaum-Tarski algebra. An analogous construction appears also in the theory of formal languages. Namely, given a language, the construction of its syntactic monoid corresponds to the construction of Lindenbaum-Tarski algebra using Leibniz congruence.

However, Lindenbaum-Tarski algebra is not the only algebra making a bridge between syntax and semantics. In the framework of substructural logics it is often convenient to work with a more complex algebra. Imitating the construction for a language, one can obtain its syntactic residuated lattice which is richer than its syntactic monoid. In the talk we will present basic properties of syntactic residuated lattices. These can be sometimes used to transfer results from the theory of substructural logics to the theory of formal languages. As an application we obtain a new sufficient condition for a language to be regular.

### Gabor Kun: Constraint Satisfaction Problems and expander relational structures

In their seminal paper Feder and Vardi proved that every problem in the class Monotone Monadic Strict NP (MMSNP) is random polynomial-time equivalent to a finite union of Constraint Satisfaction Problems (CSP). The class MMSNP is the "largest natural" subclass defined by syntactical restrictions on existential, second order formulas that might have the dichotomy property. This (and the Hell-Nesetril dichotomy theorem) was the main reason for the famous dichotomy conjecture of Feder and Vardi for CSP problems.

We derandomize their reduction showing that every MMSNP problem is polynomial-time equivalent to a finite union of CSP problems. The technical novelty of the paper is a notion of expander relational structures. We give a polynomial-time construction of such structures with large girth. We show another interesting application of these structures: we give an effective construction of hypergraphs with large girth and chromatic number.

### Patrice Ossona de Mendez: A Model Theory Approach to Structural Limits

(joint work with J. Nesetril)

Recently, graph sequences and graph limits are intensively studied, from diverse point of views: probability theory and statistics, property testing in computer science, flag algebras, logic, graphs homomorphisms, etc. Three standard notions of graph limits have inspired this work: the notion of dense graph limit, the notion of bounded degree graph limit, and the notion of elementary limit. In this talk we provide a unifying approach to these limits. Our approach is a combination of a functional analytic and model theoretic approach and thus applies to applies to more general structures (rather than graphs). Thus we use term structural limits.