View: session overviewtalk overview

14:00 | Sample compression schemes for balls in graphs ABSTRACT. One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For balls of arbitrary radius $r$, we design proper sample compression schemes of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of $\delta$-hyperbolic graphs. |

14:25 | Not all Strangers are the Same: The Impact of Tolerance in Schelling Games PRESENTER: Maria Kyropoulou ABSTRACT. Schelling’s famous model of segregation assumes agents of different types, who would like to be located in neighborhoods having at least a certain fraction of agents of the same type. We consider natural generalizations that allow for the possibility of agents being tolerant towards other agents, even if they are not of the same type. In particular, we consider an ordering of the types, and make the realistic assumption that the agents are in principle more tolerant towards agents of types that are closer to their own according to the ordering. Based on this, we study the strategic games induced when the agents aim to maximize their utility, for a variety of tolerance levels. We provide a collection of results about the existence of equilibria, and their quality in terms of social welfare. |

14:50 | Membership problems in finite groups ABSTRACT. We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed n > 2, where n is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks, stating NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant Horton-Strahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar. |

15:15 | On Algorithms Based on Finitely Many Homomorphism Counts ABSTRACT. It is well known [Lovasz, 1967] that up to isomorphism a graph $G$ is determined by the homomorphism counts $\textup{hom}(F, G)$, i.e., by the number of homomorphisms from $F$ to $G$ where $F$ ranges over all graphs. Moreover, it suffices that $F$ ranges over the graphs with at most as many vertices as $G$. Thus, in principle, we can answer any query concerning $G$ with only accessing the $\textup{hom}(\cdot, G)$'s instead of $G$ itself. In this paper, we deal with queries for which there is a \emph{hom algorithm}, i.e., there are \emph{finitely many} graphs $F_1, \ldots, F_k$ such that for any graph $ G$ whether it is a \textsc{Yes}-instance of the query is already determined by the vector $\vec{hom}_{F_1, \ldots, F_k}(G):= (\textup{hom}(F_1, G), \ldots, \hom(F_k, G))$. We observe that planarity of graphs and 3-colorability of graphs, properties expressible in monadic second-order logic, have no hom algorithm. On the other hand, queries expressible as a Boolean combination of universal sentences in first-order logic FO have a hom algorithm. Even though it is not easy to find FO definable queries without a hom algorithm, we succeed to show this for the existence of an isolated vertex, a property expressible by the FO sentence $\exists x\forall y \neg Exy$, somehow the ``simplest'' graph property not definable by a Boolean combination of universal sentences. These results provide a characterization of the prefix classes of first-order logic with the property that each query definable by a sentence of the prefix class has a hom algorithm. For \emph{adaptive} hom algorithms, i.e., algorithms that might access a $\hom(F_{i+1}, G)$ with $F_{i+1}$ depending on $\hom(F_j, G)$ for $1\le j \le i$ we show that \emph{three} homomorphism counts $\hom(\cdot, G)$ are sufficient and in general necessary to determine the (isomorphism type of) $G$. In particular, by three adaptive queries we can answer any question on $G$. Moreover, adaptively accessing two $\hom(\cdot, G)$'s is already enough to detect an isolated vertex. In 1993 Chaudhuri and Vardi showed the analogue of the Lovasz Isomorphism Theorem for the right homomorphism vector of a graph $G$, i.e., the vector of values $\textup{hom}(G,F)$ where $F$ ranges over all graphs characterizes the isomorphism type of $G$. We study to what extent our results carry over to the right homomorphism vector. |