13 Search Results for "Str�der, Thomas"

Document
DOI: 10.4230/LIPIcs.CCC.2021.25
Arithmetic Circuit Complexity of Division and Truncation

Authors: Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
Given polynomials f,g,h ∈ 𝔽[x₁,…,x_n] such that f = g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s,deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen'87 & WACT'16). The result is an exponential improvement over Strassen’s classic result (Strassen'73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)). Further, we show that any univariate polynomial family (f_d)_d, defined by the initial segment of the power series expansion of rational function g_d(x)/h_d(x) up to degree d (i.e. f_d = g_d/h_d od x^{d+1}), where circuit size of g is s_d and degree of g_d is at most d, can be computed by a circuit of size poly(s_d,deg(h_d),log d). We also show a hardness result when the degrees of the rational functions are high (i.e. Ω (d)), assuming hardness of the integer factorization problem. Finally, we extend this conditional hardness to simple algebraic functions as well, and show that for every prime p, there is an integral algebraic power series with its minimal polynomial satisfying a degree p polynomial equation, such that its initial segment is hard to compute unless integer factoring is easy, or a multiple of n! is easy to compute. Both, integer factoring and computation of multiple of n!, are believed to be notoriously hard. In contrast, we show examples of transcendental power series whose initial segments are easy to compute.
Cite as

Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu. Arithmetic Circuit Complexity of Division and Truncation. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 25:1-25:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.CCC.2021.25,
  author =	{Dutta, Pranjal and Jindal, Gorav and Pandey, Anurag and Sinhababu, Amit},
  title =	{{Arithmetic Circuit Complexity of Division and Truncation}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{25:1--25:36},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.25},
  URN =		{urn:nbn:de:0030-drops-142990},
  doi =		{10.4230/LIPIcs.CCC.2021.25},
  annote =	{Keywords: Arithmetic Circuits, Division, Truncation, Division elimination, Rational function, Algebraic power series, Transcendental power series, Integer factorization}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.15
Multi-Robot Motion Planning of k-Colored Discs Is PSPACE-Hard

Authors: Thomas Brocken, G. Wessel van der Heijden, Irina Kostitsyna, Lloyd E. Lo-Wong, and Remco J. A. Surtel

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
In the problem of multi-robot motion planning, a group of robots, placed in a polygonal domain with obstacles, must be moved from their starting positions to a set of target positions. We consider the specific case of unlabeled disc robots of two different sizes. That is, within one class of robots, where a class is given by the robots' size, any robot can be moved to any of the corresponding target positions. We prove that the decision problem of whether there exists a schedule moving the robots to the target positions is PSPACE-hard.
Cite as

Thomas Brocken, G. Wessel van der Heijden, Irina Kostitsyna, Lloyd E. Lo-Wong, and Remco J. A. Surtel. Multi-Robot Motion Planning of k-Colored Discs Is PSPACE-Hard. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brocken_et_al:LIPIcs.FUN.2021.15,
  author =	{Brocken, Thomas and van der Heijden, G. Wessel and Kostitsyna, Irina and Lo-Wong, Lloyd E. and Surtel, Remco J. A.},
  title =	{{Multi-Robot Motion Planning of k-Colored Discs Is PSPACE-Hard}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.15},
  URN =		{urn:nbn:de:0030-drops-127769},
  doi =		{10.4230/LIPIcs.FUN.2021.15},
  annote =	{Keywords: Disc-robot motion planning, algorithmic complexity, PSPACE-hard}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2020.10
Cybersecurity Games for Secure Programming Education in the Industry: Gameplay Analysis

Authors: Tiago Gasiba, Ulrike Lechner, Filip Rezabek, and Maria Pinto-Albuquerque

Published in: OASIcs, Volume 81, First International Computer Programming Education Conference (ICPEC 2020)

Abstract
To minimize the possibility of introducing vulnerabilities in source code, software developers may attend security awareness and secure coding training. From the various approaches of how to raise awareness and adherence to coding standards, one promising novel approach is Cybersecurity Challenges. However, in an industrial setting, time is a precious resource, and, therefore, one needs to understand how to optimize the gaming experience of Cybersecurity Challenges and the effect of this game on secure coding skills. This work identifies the time spent solving challenges of different categories, analyzes gaming strategies in terms of a slow and fast team profile, and relates these profiles to the game success. First results indicate that the slow strategy is more successful than the fast approach. The authors also analyze the possible implications in the design and the training of secure coding in an industrial setting by means of Cybersecurity Challenges. This work concludes with a brief overview of its limitations and next steps in the study.
Cite as

Tiago Gasiba, Ulrike Lechner, Filip Rezabek, and Maria Pinto-Albuquerque. Cybersecurity Games for Secure Programming Education in the Industry: Gameplay Analysis. In First International Computer Programming Education Conference (ICPEC 2020). Open Access Series in Informatics (OASIcs), Volume 81, pp. 10:1-10:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gasiba_et_al:OASIcs.ICPEC.2020.10,
  author =	{Gasiba, Tiago and Lechner, Ulrike and Rezabek, Filip and Pinto-Albuquerque, Maria},
  title =	{{Cybersecurity Games for Secure Programming Education in the Industry: Gameplay Analysis}},
  booktitle =	{First International Computer Programming Education Conference (ICPEC 2020)},
  pages =	{10:1--10:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-153-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{81},
  editor =	{Queir\'{o}s, Ricardo and Portela, Filipe and Pinto, M\'{a}rio and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2020.10},
  URN =		{urn:nbn:de:0030-drops-122977},
  doi =		{10.4230/OASIcs.ICPEC.2020.10},
  annote =	{Keywords: education, training, secure coding, industry, cybersecurity, capture-the-flag, game analysis, cybersecurity challenge}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2020.11
Ranking Secure Coding Guidelines for Software Developer Awareness Training in the Industry

Authors: Tiago Gasiba, Ulrike Lechner, Jorge Cuellar, and Alae Zouitni

Published in: OASIcs, Volume 81, First International Computer Programming Education Conference (ICPEC 2020)

Abstract
Secure coding guidelines are essential material used to train and raise awareness of software developers on the topic of secure software development. In industrial environments, since developer time is costly, and training and education is part of non-productive hours, it is important to address and stress the most important topics first. In this work, we devise a method, based on publicly available real-world vulnerability databases and secure coding guideline databases, to rank important secure coding guidelines based on defined industry-relevant metrics. The goal is to define priorities for a teaching curriculum on raising cybersecurity awareness of software developers on secure coding guidelines. Furthermore, we do a small comparison study by asking computer science students from university on how they rank the importance of secure coding guidelines and compare the outcome to our results.
Cite as

Tiago Gasiba, Ulrike Lechner, Jorge Cuellar, and Alae Zouitni. Ranking Secure Coding Guidelines for Software Developer Awareness Training in the Industry. In First International Computer Programming Education Conference (ICPEC 2020). Open Access Series in Informatics (OASIcs), Volume 81, pp. 11:1-11:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gasiba_et_al:OASIcs.ICPEC.2020.11,
  author =	{Gasiba, Tiago and Lechner, Ulrike and Cuellar, Jorge and Zouitni, Alae},
  title =	{{Ranking Secure Coding Guidelines for Software Developer Awareness Training in the Industry}},
  booktitle =	{First International Computer Programming Education Conference (ICPEC 2020)},
  pages =	{11:1--11:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-153-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{81},
  editor =	{Queir\'{o}s, Ricardo and Portela, Filipe and Pinto, M\'{a}rio and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2020.11},
  URN =		{urn:nbn:de:0030-drops-122988},
  doi =		{10.4230/OASIcs.ICPEC.2020.11},
  annote =	{Keywords: education, teaching, training, secure coding, industry, cybersecurity, capture-the-flag, game analysis, game design, cybersecurity challenge}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.9
Complexity of Unordered CNF Games

Authors: Md Lutfar Rahman and Thomas Watson

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study variants of this game in which the variables may be played in any order, and each turn consists of picking a remaining variable and a truth value for it. - For the version where the set of variables is partitioned into two halves and each player may only pick variables from his/her half, we prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for unbounded-width CNFs (Schaefer, STOC 1976). - For the general unordered version (where each variable can be picked by either player), we also prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for 6-CNFs (Ahlroth and Orponen, MFCS 2012) and PSPACE-complete for positive 11-CNFs (Schaefer, STOC 1976).
Cite as

Md Lutfar Rahman and Thomas Watson. Complexity of Unordered CNF Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{rahman_et_al:LIPIcs.ISAAC.2018.9,
  author =	{Rahman, Md Lutfar and Watson, Thomas},
  title =	{{Complexity of Unordered CNF Games}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.9},
  URN =		{urn:nbn:de:0030-drops-99574},
  doi =		{10.4230/LIPIcs.ISAAC.2018.9},
  annote =	{Keywords: CNF, Games, PSPACE-complete, SAT, Linear Time}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.45
Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm

Authors: Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Consider a problem where 4k given vectors need to be partitioned into k clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum of the component-wise maxima of the four vectors in the quad. The problem is to partition the given 4k vectors into k quads with minimum total cost. We analyze a straightforward matching-based algorithm and prove that this algorithm is a 3/2-approximation algorithm for this problem. We further analyze the performance of this algorithm on a hierarchy of special cases of the problem and prove that, in one particular case, the algorithm is a 5/4-approximation algorithm. Our analysis is tight in all cases except one.
Cite as

Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma. Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 45:1-45:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ficker_et_al:LIPIcs.ISAAC.2018.45,
  author =	{Ficker, Annette M. C. and Erlebach, Thomas and Mihal\'{a}k, Mat\'{u}s and Spieksma, Frits C. R.},
  title =	{{Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{45:1--45:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.45},
  URN =		{urn:nbn:de:0030-drops-99933},
  doi =		{10.4230/LIPIcs.ISAAC.2018.45},
  annote =	{Keywords: approximation algorithm, matching, clustering problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.61
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity

Authors: Timothy M. Chan, Thomas C. van Dijk, Krzysztof Fleszar, Joachim Spoerhase, and Alexander Wolff

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizontal line segments of minimum total length so that every rectangle is stabbed by some line segment. A line segment stabs a rectangle if it intersects its left and its right boundary. The problem, which we call Stabbing, can be motivated by a resource allocation problem and has applications in geometric network design. To the best of our knowledge, only special cases of this problem have been considered so far. Stabbing is a weighted geometric set cover problem, which we show to be NP-hard. While for general set cover the best possible approximation ratio is Theta(log n), it is an important field in geometric approximation algorithms to obtain better ratios for geometric set cover problems. Chan et al. [SODA'12] generalize earlier results by Varadarajan [STOC'10] to obtain sub-logarithmic performances for a broad class of weighted geometric set cover instances that are characterized by having low shallow-cell complexity. The shallow-cell complexity of Stabbing instances, however, can be high so that a direct application of the framework of Chan et al. gives only logarithmic bounds. We still achieve a constant-factor approximation by decomposing general instances into what we call laminar instances that have low enough complexity. Our decomposition technique yields constant-factor approximations also for the variant where rectangles can be stabbed by horizontal and vertical segments and for two further geometric set cover problems.
Cite as

Timothy M. Chan, Thomas C. van Dijk, Krzysztof Fleszar, Joachim Spoerhase, and Alexander Wolff. Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ISAAC.2018.61,
  author =	{Chan, Timothy M. and van Dijk, Thomas C. and Fleszar, Krzysztof and Spoerhase, Joachim and Wolff, Alexander},
  title =	{{Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{61:1--61:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.61},
  URN =		{urn:nbn:de:0030-drops-100094},
  doi =		{10.4230/LIPIcs.ISAAC.2018.61},
  annote =	{Keywords: Geometric optimization, NP-hard, approximation, shallow-cell complexity, line stabbing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.64
Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings

Authors: Kelin Luo, Thomas Erlebach, and Yinfeng Xu

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We study an on-line scheduling problem that is motivated by applications such as car-sharing, in which users submit ride requests, and the scheduler aims to accept requests of maximum total profit using k servers (cars). Each ride request specifies the pick-up time and the pick-up location (among two locations, with the other location being the destination). The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time). We consider two variants of the problem with respect to constraints on the booking time: In the fixed booking time variant, a request must be submitted a fixed amount of time before the pick-up time. In the variable booking time variant, a request can be submitted at any time during a certain time interval (called the booking horizon) that precedes the pick-up time. We present lower bounds on the competitive ratio for both variants and propose a balanced greedy algorithm (BGA) that achieves the best possible competitive ratio. We prove that, for the fixed booking time variant, BGA is 1.5-competitive if k=3i ( i in N) and the fixed booking length is not less than the travel time between the two locations; for the variable booking time variant, BGA is 1.5-competitive if k=3i ( i in N) and the length of the booking horizon is less than the travel time between the two locations, and BGA is 5/3-competitive if k=5i ( i in N) and the length of the booking horizon is not less than the travel time between the two locations.
Cite as

Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 64:1-64:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{luo_et_al:LIPIcs.ISAAC.2018.64,
  author =	{Luo, Kelin and Erlebach, Thomas and Xu, Yinfeng},
  title =	{{Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{64:1--64:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.64},
  URN =		{urn:nbn:de:0030-drops-100122},
  doi =		{10.4230/LIPIcs.ISAAC.2018.64},
  annote =	{Keywords: Car-sharing system, Competitive analysis, On-line scheduling}
}
Document
DOI: 10.4230/LIPIcs.RTA.2015.334
Inferring Lower Bounds for Runtime Complexity

Authors: Florian Frohn, Jürgen Giesl, Jera Hensel, Cornelius Aschermann, and Thomas Ströder

Published in: LIPIcs, Volume 36, 26th International Conference on Rewriting Techniques and Applications (RTA 2015)

Abstract
We present the first approach to deduce lower bounds for innermost runtime complexity of term rewrite systems (TRSs) automatically. Inferring lower runtime bounds is useful to detect bugs and to complement existing techniques that compute upper complexity bounds. The key idea of our approach is to generate suitable families of rewrite sequences of a TRS and to find a relation between the length of such a rewrite sequence and the size of the first term in the sequence. We implemented our approach in the tool AProVE and evaluated it by extensive experiments.
Cite as

Florian Frohn, Jürgen Giesl, Jera Hensel, Cornelius Aschermann, and Thomas Ströder. Inferring Lower Bounds for Runtime Complexity. In 26th International Conference on Rewriting Techniques and Applications (RTA 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 36, pp. 334-349, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{frohn_et_al:LIPIcs.RTA.2015.334,
  author =	{Frohn, Florian and Giesl, J\"{u}rgen and Hensel, Jera and Aschermann, Cornelius and Str\"{o}der, Thomas},
  title =	{{Inferring Lower Bounds for Runtime Complexity}},
  booktitle =	{26th International Conference on Rewriting Techniques and Applications (RTA 2015)},
  pages =	{334--349},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-85-9},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{36},
  editor =	{Fern\'{a}ndez, Maribel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2015.334},
  URN =		{urn:nbn:de:0030-drops-52068},
  doi =		{10.4230/LIPIcs.RTA.2015.334},
  annote =	{Keywords: Term Rewriting, Runtime Complexity, Lower Bounds, Induction}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.465
Preemptive and Non-Preemptive Generalized Min Sum Set Cover

Authors: Sungjin Im, Maxim Sviridenko, and Ruben van der Zwaan

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets S = {S_1, S_2, ..., S_m} where each set S_i in 2^{[n]} has a positive requirement k(S_i) that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set S_i is defined as the first index j in the ordering such that the first j elements in the ordering contain k(S_i) elements in S_i. This problem was introduced by [Azar, Gamzu and Yin, 2009] with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known [Bansal, Gupta and Krishnaswamy, 2010][Skutella and Williamson, 2011]. We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set S is covered in the moment when k(S) amount of elements in S are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming and analysis are completely different from [Bansal, Gupta and Krishnaswamy, 2010][Skutella and Williamson, 2011]. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved 12.4-approximation for the non-preemptive problem.
Cite as

Sungjin Im, Maxim Sviridenko, and Ruben van der Zwaan. Preemptive and Non-Preemptive Generalized Min Sum Set Cover. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 465-476, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{im_et_al:LIPIcs.STACS.2012.465,
  author =	{Im, Sungjin and Sviridenko, Maxim and van der Zwaan, Ruben},
  title =	{{Preemptive and Non-Preemptive Generalized Min Sum Set Cover}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{465--476},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.465},
  URN =		{urn:nbn:de:0030-drops-33991},
  doi =		{10.4230/LIPIcs.STACS.2012.465},
  annote =	{Keywords: Set Cover, Approximation, Preemption, Latency, Average cover time}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2492
Named Models in Coalgebraic Hybrid Logic

Authors: Lutz Schröder and Dirk Pattinson

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Hybrid logic extends modal logic with support for reasoning about individual states, designated by so-called nominals. We study hybrid logic in the broad context of coalgebraic semantics, where Kripke frames are replaced with coalgebras for a given functor, thus covering a wide range of reasoning principles including, e.g., probabilistic, graded, default, or coalitional operators. Specifically, we establish generic criteria for a given coalgebraic hybrid logic to admit named canonical models, with ensuing completeness proofs for pure extensions on the one hand, and for an extended hybrid language with local binding on the other. We instantiate our framework with a number of examples. Notably, we prove completeness of graded hybrid logic with local binding.
Cite as

Lutz Schröder and Dirk Pattinson. Named Models in Coalgebraic Hybrid Logic. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 645-656, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{schroder_et_al:LIPIcs.STACS.2010.2492,
  author =	{Schr\"{o}der, Lutz and Pattinson, Dirk},
  title =	{{Named Models in Coalgebraic Hybrid Logic}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{645--656},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2492},
  URN =		{urn:nbn:de:0030-drops-24920},
  doi =		{10.4230/LIPIcs.STACS.2010.2492},
  annote =	{Keywords: Logic in computer science, semantics, deduction, modal logic, coalgebra}
}
Document
DOI: 10.4230/DagSemProc.09121.27
Robust Normative Systems

Authors: Thomas Agotnes, Wiebe van der Hoek, and Michael Wooldridge

Published in: Dagstuhl Seminar Proceedings, Volume 9121, Normative Multi-Agent Systems (2009)

Abstract
Although normative systems, or social laws, have proved to be a highly influential approach to coordination in multi-agent systems, the issue of emph{compliance} to such normative systems remains problematic. In all real systems, it is possible that some members of an agent population will not comply with the rules of a normative system, even if it is in their interests to do so. It is therefore important to consider the extent to which a normative system is emph{robust}, i.e., the extent to which it remains effective even if some agents do not comply with it. We formalise and investigate three different notions of robustness and related decision problems. We begin by considering sets of agents whose compliance is necessary and/or sufficient to guarantee the effectiveness of a normative system; we then consider quantitative approaches to robustness, where we try to identify the proportion of an agent population that must comply in order to ensure success, and finally, we consider a more general approach, where we characterise the compliance conditions required for success as a logical formula.
Cite as

Thomas Agotnes, Wiebe van der Hoek, and Michael Wooldridge. Robust Normative Systems. In Normative Multi-Agent Systems. Dagstuhl Seminar Proceedings, Volume 9121, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{agotnes_et_al:DagSemProc.09121.27,
  author =	{Agotnes, Thomas and van der Hoek, Wiebe and Wooldridge, Michael},
  title =	{{Robust Normative Systems}},
  booktitle =	{Normative Multi-Agent Systems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9121},
  editor =	{Guido Boella and Pablo Noriega and Gabriella Pigozzi and Harko Verhagen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09121.27},
  URN =		{urn:nbn:de:0030-drops-18971},
  doi =		{10.4230/DagSemProc.09121.27},
  annote =	{Keywords: Normative systems, robustness, fault tolerance, complexity}
}
Document
DOI: 10.4230/DagSemProc.07122.24
On the Logic of Normative Systems

Authors: Thomas Ågotnes, Wiebe van der Hoek, Juan A. Rodriguez-Aguilar, Carles Sierra, and Michael Wooldridge

Published in: Dagstuhl Seminar Proceedings, Volume 7122, Normative Multi-agent Systems (2007)

Abstract
We introduce emph{Normative Temporal Logic} (acro{ntl}), a logic for reasoning about normative systems. acro{ntl} is a generalisation of the well-known branching-time temporal logic acro{ctl}, in which the path quantifiers $Apath$ (``on all pathsldots'') and $Epath$ (``on some pathldots'') are replaced by the indexed deontic operators $O{ s}$ and $P{ s}$, where for example $O{ s}phi$ means ``$phi$ is obligatory in the context of normative system $ s$''. After defining the logic, we give a sound and complete axiomatisation, and discuss the logic's relationship to standard deontic logics. We present a symbolic representation language for models and normative systems, and identify four different model checking problems, corresponding to whether or not a model is represented symbolically or explicitly, and whether or not we are given an interpretation for the normative systems named in formulae to be checked. We show that the complexity of model checking varies from acro{p}-complete up to acro{exptime}-hard for these variations.
Cite as

Thomas Ågotnes, Wiebe van der Hoek, Juan A. Rodriguez-Aguilar, Carles Sierra, and Michael Wooldridge. On the Logic of Normative Systems. In Normative Multi-agent Systems. Dagstuhl Seminar Proceedings, Volume 7122, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{agotnes_et_al:DagSemProc.07122.24,
  author =	{\r{A}gotnes, Thomas and van der Hoek, Wiebe and Rodriguez-Aguilar, Juan A. and Sierra, Carles and Wooldridge, Michael},
  title =	{{On the Logic of Normative Systems}},
  booktitle =	{Normative Multi-agent Systems},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7122},
  editor =	{Guido Boella and Leon van der Torre and Harko Verhagen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07122.24},
  URN =		{urn:nbn:de:0030-drops-9210},
  doi =		{10.4230/DagSemProc.07122.24},
  annote =	{Keywords: Normative systems, normative temporal logic, deontic logic}
}
  • Refine by Author
  • 2 Erlebach, Thomas
  • 2 Gasiba, Tiago
  • 2 Lechner, Ulrike
  • 2 Wooldridge, Michael
  • 2 van der Hoek, Wiebe
  • Show More...

  • Refine by Classification
  • 2 Applied computing → E-learning
  • 2 Applied computing → Interactive learning environments
  • 2 Security and privacy → Software security engineering
  • 2 Security and privacy → Web application security
  • 2 Theory of computation → Computational complexity and cryptography
  • Show More...

  • Refine by Keyword
  • 2 Normative systems
  • 2 capture-the-flag
  • 2 cybersecurity
  • 2 cybersecurity challenge
  • 2 education
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 4 2018
  • 3 2020
  • 1 2007
  • 1 2009
  • 1 2010
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact