2018 [ to top ]

• 
  Bilò, Davide; Lenzner, Pascal On the Tree Conjecture for the Network Creation Game. Symposium on the Theoretical Aspects of Computer Science (STACS) 2018: 14:1--14:15
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. [PODC'03] is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all \($\alpha$\) and that for \($\alpha \geq n$\) all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bounds for both conjectures. In particular we show that for \($\alpha > 4n-13$\) all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.
  @inproceedings{bil2018conjecture, abstract = {Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. [PODC'03] is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all $\alpha$ and that for $\alpha \geq n$ all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bounds for both conjectures. In particular we show that for $\alpha > 4n-13$ all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.}, author = {Bilò, Davide and Lenzner, Pascal}, booktitle = {Symposium on the Theoretical Aspects of Computer Science (STACS)}, pages = {14:1--14:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, title = {On the Tree Conjecture for the Network Creation Game}, year = 2018 }

2016 [ to top ]

• 
  Kötzing, Timo; Schirneck, Martin Towards an Atlas of Computational Learning Theory. Symposium on Theoretical Aspects of Computer Science (STACS) 2016: 47:1-47:13
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A major part of our knowledge about Computational Learning stems from comparisons of the learning power of different learning criteria. These comparisons inform about trade-offs between learning restrictions and, more generally, learning settings; furthermore, they inform about what restrictions can be observed without losing learning power. With this paper we propose that one main focus of future research in Computational Learning should be on a structured approach to determine the relations of different learning criteria. In particular, we propose that, for small sets of learning criteria, all pairwise relations should be determined; these relations can then be easily depicted as a map, a diagram detailing the relations. Once we have maps for many relevant sets of learning criteria, the collection of these maps is an Atlas of Computational Learning Theory, informing at a glance about the landscape of computational learning just as a geographical atlas informs about the earth. In this paper we work toward this goal by providing three example maps, one pertaining to partially set-driven learning, and two pertaining to strongly monotone learning. These maps can serve as blueprints for future maps of similar base structure.
  @inproceedings{DBLP:conf/stacs/KotzingS16, abstract = {A major part of our knowledge about Computational Learning stems from comparisons of the learning power of different learning criteria. These comparisons inform about trade-offs between learning restrictions and, more generally, learning settings; furthermore, they inform about what restrictions can be observed without losing learning power. With this paper we propose that one main focus of future research in Computational Learning should be on a structured approach to determine the relations of different learning criteria. In particular, we propose that, for small sets of learning criteria, all pairwise relations should be determined; these relations can then be easily depicted as a map, a diagram detailing the relations. Once we have maps for many relevant sets of learning criteria, the collection of these maps is an Atlas of Computational Learning Theory, informing at a glance about the landscape of computational learning just as a geographical atlas informs about the earth. In this paper we work toward this goal by providing three example maps, one pertaining to partially set-driven learning, and two pertaining to strongly monotone learning. These maps can serve as blueprints for future maps of similar base structure.}, address = {Dagstuhl, Germany}, annote = {Keywords: computational learning, language learning, partially set-driven learning, strongly monotone learning}, author = {Kötzing, Timo and Schirneck, Martin}, booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)}, pages = {47:1-47:13}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Towards an Atlas of Computational Learning Theory}, volume = 47, year = 2016 }

2014 [ to top ]

• 
  Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to Cactus Graphs Modulo 2. Symposium on Theoretical Aspects of Computer Science (STACS) 2014: 350-361
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A homomorphism from a graph \(G\) to a graph \(H\) is a function from \(V(G)\) to \(V(H)\) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this article, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph \(H\) has a big influence on the complexity of the problem. Thus, our approach is graph-theoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs \(H\), counting homomorphisms to \(H\) modulo 2 can be done in polynomial time. For every other fixed cactus graph \(H\), the problem is complete in the complexity class \(\oplus P\), which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which \(H\) lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which \(H\) is a tree.
  @inproceedings{DBLP:conf/stacs/0001GR14, abstract = {A homomorphism from a graph \(G\) to a graph \(H\) is a function from \(V(G)\) to \(V(H)\) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this article, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph \(H\) has a big influence on the complexity of the problem. Thus, our approach is graph-theoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs \(H\), counting homomorphisms to \(H\) modulo 2 can be done in polynomial time. For every other fixed cactus graph \(H\), the problem is complete in the complexity class \(\oplus P\), which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which \(H\) lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which \(H\) is a tree.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David}, booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)}, crossref = {DBLP:conf/stacs/2014}, pages = {350-361}, title = {Counting Homomorphisms to Cactus Graphs Modulo 2}, year = 2014 }
• 
  Kötzing, Timo A Solution to Wiehagen's Thesis. Symposium on Theoretical Aspects of Computer Science (STACS) 2014: 494-505
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Wiehagen's Thesis in Inductive Inference (1991) essentially states that, for each learning criterion, learning can be done in a normalized, enumerative way. The thesis was not a formal statement and thus did not allow for a formal proof, but support was given by examples of a number of different learning criteria that can be learned by enumeration. Building on recent formalizations of learning criteria, we are now able to formalize Wiehagen's Thesis. We prove the thesis for a wide range of learning criteria, including many popular criteria from the literature. We also show the limitations of the thesis by giving four learning criteria for which the thesis does not hold (and, in two cases, was probably not meant to hold). Beyond the original formulation of the thesis, we also prove stronger versions which allow for many corollaries relating to strongly decisive and conservative learning.
  @inproceedings{DBLP:conf/stacs/Kotzing14, abstract = {Wiehagen's Thesis in Inductive Inference (1991) essentially states that, for each learning criterion, learning can be done in a normalized, enumerative way. The thesis was not a formal statement and thus did not allow for a formal proof, but support was given by examples of a number of different learning criteria that can be learned by enumeration. Building on recent formalizations of learning criteria, we are now able to formalize Wiehagen's Thesis. We prove the thesis for a wide range of learning criteria, including many popular criteria from the literature. We also show the limitations of the thesis by giving four learning criteria for which the thesis does not hold (and, in two cases, was probably not meant to hold). Beyond the original formulation of the thesis, we also prove stronger versions which allow for many corollaries relating to strongly decisive and conservative learning.}, author = {Kötzing, Timo}, booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)}, pages = {494-505}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {A Solution to Wiehagen's Thesis}, volume = 25, year = 2014 }

2011 [ to top ]

• 
  Antoniadis, Antonios; Hüffner, Falk; Lenzner, Pascal; Moldenhauer, Carsten; Souza, Alexander Balanced Interval Coloring. Symposium on Theoretical Aspects of Computer Science (STACS) 2011: 531-542
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We consider the discrepancy problem of coloring n intervals with \(k\) colors such that at each point on the line, the maximal difference between the number of intervals of any two colors is minimal. Somewhat surprisingly, a coloring with maximal difference at most one always exists. Furthermore, we give an algorithm with running time \(O(n \log n + k n \log k)\) for its construction. This is in particular interesting because many known results for discrepancy problems are non-constructive. This problem naturally models a load balancing scenario, where \(n\) tasks with given start- and endtimes have to be distributed among \(k\) servers. Our results imply that this can be done ideally balanced. When generalizing to \(d\)-dimensional boxes (instead of intervals), a solution with difference at most one is not always possible. We show that for any \(d \ge 2\) and any \(k \ge 2\) it is NP-complete to decide if such a solution exists, which implies also NP-hardness of the respective minimization problem. In an online scenario, where intervals arrive over time and the color has to be decided upon arrival, the maximal difference in the size of color classes can become arbitrarily high for any online algorithm.
  @inproceedings{DBLP:conf/stacs/AntoniadisHLMS11, abstract = {We consider the discrepancy problem of coloring n intervals with \(k\) colors such that at each point on the line, the maximal difference between the number of intervals of any two colors is minimal. Somewhat surprisingly, a coloring with maximal difference at most one always exists. Furthermore, we give an algorithm with running time \(O(n \log n + k n \log k)\) for its construction. This is in particular interesting because many known results for discrepancy problems are non-constructive. This problem naturally models a load balancing scenario, where \(n\) tasks with given start- and endtimes have to be distributed among \(k\) servers. Our results imply that this can be done ideally balanced. When generalizing to \(d\)-dimensional boxes (instead of intervals), a solution with difference at most one is not always possible. We show that for any \(d \ge 2\) and any \(k \ge 2\) it is NP-complete to decide if such a solution exists, which implies also NP-hardness of the respective minimization problem. In an online scenario, where intervals arrive over time and the color has to be decided upon arrival, the maximal difference in the size of color classes can become arbitrarily high for any online algorithm.}, author = {Antoniadis, Antonios and Hüffner, Falk and Lenzner, Pascal and Moldenhauer, Carsten and Souza, Alexander}, booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)}, pages = {531-542}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Balanced Interval Coloring}, volume = 9, year = 2011 }
• 
  Case, John; Kötzing, Timo Measuring Learning Complexity with Criteria Epitomizers. Symposium on Theoretical Aspects of Computer Science (STACS) 2011: 320-331
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In prior papers, beginning with the seminal work by Freivalds et al. 1995, the notion of intrinsic complexity is used to analyze the learning complexity of sets of functions in a Gold-style learning setting. Herein are pointed out some weaknesses of this notion. Offered is an alternative based on epitomizing sets of functions - sets, which are learnable under a given learning criterion, but not under other criteria which are not at least as powerful. To capture the idea of epitomizing sets, new reducibility notions are given based on robust learning (closure of learning under certain classes of operators). Various degrees of epitomizing sets are characterized as the sets complete with respect to corresponding reducibility notions! These characterizations also provide an easy method for showing sets to be epitomizers, and they are, then, employed to prove several sets to be epitomizing. Furthermore, a scheme is provided to generate easily very strong epitomizers for a multitude of learning criteria. These strong epitomizers are so-called self-learning sets, previously applied by Case & Koetzing, 2010. These strong epitomizers can be generated and employed in a myriad of settings to witness the strict separation in learning power between the criteria so epitomized and other not as powerful criteria!
  @inproceedings{DBLP:conf/stacs/CaseK11, abstract = {In prior papers, beginning with the seminal work by Freivalds et al. 1995, the notion of intrinsic complexity is used to analyze the learning complexity of sets of functions in a Gold-style learning setting. Herein are pointed out some weaknesses of this notion. Offered is an alternative based on epitomizing sets of functions - sets, which are learnable under a given learning criterion, but not under other criteria which are not at least as powerful. To capture the idea of epitomizing sets, new reducibility notions are given based on robust learning (closure of learning under certain classes of operators). Various degrees of epitomizing sets are characterized as the sets complete with respect to corresponding reducibility notions! These characterizations also provide an easy method for showing sets to be epitomizers, and they are, then, employed to prove several sets to be epitomizing. Furthermore, a scheme is provided to generate easily very strong epitomizers for a multitude of learning criteria. These strong epitomizers are so-called self-learning sets, previously applied by Case \& Koetzing, 2010. These strong epitomizers can be generated and employed in a myriad of settings to witness the strict separation in learning power between the criteria so epitomized and other not as powerful criteria!}, author = {Case, John and Kötzing, Timo}, booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)}, pages = {320-331}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Measuring Learning Complexity with Criteria Epitomizers}, volume = 9, year = 2011 }