@inproceedings{3110, author = {{Günther, Felix and Hale, Britta and Jager, Tibor and Lauer, Sebastian}}, booktitle = {{Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part III}}, pages = {{519----548}}, title = {{{0-RTT Key Exchange with Full Forward Secrecy}}}, doi = {{10.1007/978-3-319-56617-7_18}}, year = {{2017}}, } @inproceedings{3111, author = {{Jager, Tibor and Stam, Martijn and Stanley-Oakes, Ryan and Warinschi, Bogdan}}, booktitle = {{Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12-15, 2017, Proceedings, Part I}}, pages = {{409----441}}, title = {{{Multi-key Authenticated Encryption with Corruptions: Reductions Are Lossy}}}, doi = {{10.1007/978-3-319-70500-2_14}}, year = {{2017}}, } @inproceedings{3155, author = {{Töws, Manuel and Wehrheim, Heike}}, booktitle = {{Formal Methods and Software Engineering - 19th International Conference on Formal Engineering Methods, {ICFEM} 2017, Xi'an, China, November 13-17, 2017, Proceedings}}, editor = {{Duan, Zhenhua and Ong, Luke}}, pages = {{362----378}}, title = {{{Policy Dependent and Independent Information Flow Analyses}}}, doi = {{10.1007/978-3-319-68690-5_22}}, year = {{2017}}, } @inproceedings{3156, author = {{König, Jürgen and Wehrheim, Heike}}, booktitle = {{Theoretical Aspects of Computing - {ICTAC} 2017 - 14th International Colloquium, Hanoi, Vietnam, October 23-27, 2017, Proceedings}}, editor = {{Van Hung, Dang and Kapur, Deepak}}, pages = {{118----135}}, title = {{{Value-Based or Conflict-Based? Opacity Definitions for STMs}}}, doi = {{10.1007/978-3-319-67729-3_8}}, year = {{2017}}, } @inproceedings{2741, author = {{Ali Ashraf, Shehzad and Wang, Y.-P. Eric and Eldessoki, Sameh and Holfeld, Bernd and Parruca, Donald and Serror, Martin and Gross, James}}, publisher = {{Proceedings of 23th European Wireless Conference 2017, 17- 19.05.2017}}, title = {{{From Radio Design to System Evaluations for Ultra-Reliable and Low-Latency Communication }}}, year = {{2017}}, } @inproceedings{112, abstract = {{We study a model of selfish resource allocation that seeks to incorporate dependencies among resources as they exist in in modern networked environments. Our model is inspired by utility functions with constant elasticity of substitution (CES) which is a well-studied model in economics. We consider congestion games with different aggregation functions. In particular, we study $L_p$ norms and analyze the existence and complexity of (approximate) pure Nash equilibria. Additionally, we give an almost tight characterization based on monotonicity properties to describe the set of aggregation functions that guarantee the existence of pure Nash equilibria.}}, author = {{Feldotto, Matthias and Leder, Lennart and Skopalik, Alexander}}, booktitle = {{Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC)}}, pages = {{222----233}}, title = {{{Congestion Games with Complementarities}}}, doi = {{10.1007/978-3-319-57586-5_19}}, year = {{2017}}, } @inproceedings{113, abstract = {{We study the computation of approximate pure Nash equilibria in Shapley value (SV) weighted congestion games, introduced in [19]. This class of games considers weighted congestion games in which Shapley values are used as an alternative (to proportional shares) for distributing the total cost of each resource among its users. We focus on the interesting subclass of such games with polynomial resource cost functions and present an algorithm that computes approximate pure Nash equilibria with a polynomial number of strategy updates. Since computing a single strategy update is hard, we apply sampling techniques which allow us to achieve polynomial running time. The algorithm builds on the algorithmic ideas of [7], however, to the best of our knowledge, this is the first algorithmic result on computation of approximate equilibria using other than proportional shares as player costs in this setting. We present a novel relation that approximates the Shapley value of a player by her proportional share and vice versa. As side results, we upper bound the approximate price of anarchy of such games and significantly improve the best known factor for computing approximate pure Nash equilibria in weighted congestion games of [7].}}, author = {{Feldotto, Matthias and Gairing, Martin and Kotsialou, Grammateia and Skopalik, Alexander}}, booktitle = {{Proceedings of the 13th International Conference on Web and Internet Economics (WINE)}}, title = {{{Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games}}}, doi = {{10.1007/978-3-319-71924-5_14}}, year = {{2017}}, } @inproceedings{114, abstract = {{Proof witnesses are proof artifacts showing correctness of programs wrt. safety properties. The recent past has seen a rising interest in witnesses as (a) proofs in a proof-carrying-code context, (b) certificates for the correct functioning of verification tools, or simply (c) exchange formats for (partial) verification results. As witnesses in all theses scenarios need to be stored and processed, witnesses are required to be as small as possible. However, software verification tools – the prime suppliers of witnesses – do not necessarily construct small witnesses. In this paper, we present a formal account of proof witnesses. We introduce the concept of weakenings, reducing the complexity of proof witnesses while preserving the ability of witnessing safety. We develop aweakening technique for a specific class of program analyses, and prove it to be sound. Finally, we experimentally demonstrate our weakening technique to indeed achieve a size reduction of proof witnesses.}}, author = {{Jakobs, Marie-Christine and Wehrheim, Heike}}, booktitle = {{NASA Formal Methods: 9th International Symposium}}, editor = {{Barrett, Clark and Davies, Misty and Kahsai, Temesghen}}, pages = {{389--403}}, title = {{{Compact Proof Witnesses}}}, doi = {{10.1007/978-3-319-57288-8_28}}, year = {{2017}}, } @inproceedings{115, abstract = {{Whenever customers have to decide between different instances of the same product, they are interested in buying the best product. In contrast, companies are interested in reducing the construction effort (and usually as a consequence thereof, the quality) to gain profit. The described setting is widely known as opposed preferences in quality of the product and also applies to the context of service-oriented computing. In general, service-oriented computing emphasizes the construction of large software systems out of existing services, where services are small and self-contained pieces of software that adhere to a specified interface. Several implementations of the same interface are considered as several instances of the same service. Thereby, customers are interested in buying the best service implementation for their service composition wrt. to metrics, such as costs, energy, memory consumption, or execution time. One way to ensure the service quality is to employ certificates, which can come in different kinds: Technical certificates proving correctness can be automatically constructed by the service provider and again be automatically checked by the user. Digital certificates allow proof of the integrity of a product. Other certificates might be rolled out if service providers follow a good software construction principle, which is checked in annual audits. Whereas all of these certificates are handled differently in service markets, what they have in common is that they influence the buying decisions of customers. In this paper, we review state-of-the-art developments in certification with respect to service-oriented computing. We not only discuss how certificates are constructed and handled in service-oriented computing but also review the effects of certificates on the market from an economic perspective.}}, author = {{Jakobs, Marie-Christine and Krämer, Julia and van Straaten, Dirk and Lettmann, Theodor}}, booktitle = {{The Ninth International Conferences on Advanced Service Computing (SERVICE COMPUTATION)}}, editor = {{Marcelo De Barros, Janusz Klink,Tadeus Uhl, Thomas Prinz}}, pages = {{7--12}}, title = {{{Certification Matters for Service Markets}}}, year = {{2017}}, } @misc{1157, author = {{Witschen, Linus Matthias}}, publisher = {{Universität Paderborn}}, title = {{{A Framework for the Synthesis of Approximate Circuits}}}, year = {{2017}}, } @inproceedings{1158, abstract = {{In this paper, we present the annotation challenges we have encountered when working on a historical language that was undergoing elaboration processes. We especially focus on syntactic ambiguity and gradience in Middle Low German, which causes uncertainty to some extent. Since current annotation tools consider construction contexts and the dynamics of the grammaticalization only partially, we plan to extend CorA – a web-based annotation tool for historical and other non-standard language data – to capture elaboration phenomena and annotator unsureness. Moreover, we seek to interactively learn morphological as well as syntactic annotations.}}, author = {{Seemann, Nina and Merten, Marie-Luis and Geierhos, Michaela and Tophinke, Doris and Hüllermeier, Eyke}}, booktitle = {{Proceedings of the Joint SIGHUM Workshop on Computational Linguistics for Cultural Heritage, Social Sciences, Humanities and Literature}}, location = {{Vancouver, BC, Canada}}, pages = {{40--45}}, publisher = {{Association for Computational Linguistics (ACL)}}, title = {{{Annotation Challenges for Reconstructing the Structural Elaboration of Middle Low German}}}, doi = {{10.18653/v1/W17-2206}}, year = {{2017}}, } @phdthesis{116, author = {{Liske, Gennadij}}, publisher = {{Universität Paderborn}}, title = {{{CCA-Security for Predicate Encryption Schemes}}}, doi = {{10.17619/UNIPB/1-220}}, year = {{2017}}, } @inproceedings{17652, author = {{Polevoy, Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees}}, booktitle = {{Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I}}, isbn = {{978-3-319-71150-8}}, keywords = {{flow, filter, MMSA, set cover, approximation, local ratio algorithm}}, pages = {{3--17}}, publisher = {{Springer International Publishing}}, title = {{{Filtering Undesirable Flows in Networks}}}, doi = {{10.1007/978-3-319-71150-8_1}}, year = {{2017}}, } @inproceedings{17653, author = {{Polevoy, Gleb and de Weerdt, M.M.}}, booktitle = {{Proceedings of the 29th Benelux Conference on Artificial Intelligence}}, keywords = {{interaction, reciprocation, contribute, shared effort, curbing, convergence, threshold, Nash equilibrium, social welfare, efficiency, price of anarchy, price of stability}}, publisher = {{Springer}}, title = {{{Reciprocation Effort Games}}}, year = {{2017}}, } @inproceedings{17654, author = {{Polevoy, Gleb and de Weerdt, M.M.}}, booktitle = {{Proceedings of the 29th Benelux Conference on Artificial Intelligence}}, keywords = {{agents, projects, contribute, shared effort game, competition, quota, threshold, Nash equilibrium, social welfare, efficiency, price of anarchy, price of stability}}, publisher = {{Springer}}, title = {{{Competition between Cooperative Projects}}}, year = {{2017}}, } @inproceedings{1767, abstract = {{Conditional Value-at-Risk, denoted as CVaRα, is becoming the prevailing measure of risk over two paramount economic domains: the insurance domain and the financial domain; α∈(0,1) is the confidence level. In this work, we study the strategic equilibria for an economic system modeled as a game, where risk-averse players seek to minimize the Conditional Value-at-Risk of their costs. Concretely, in a CVaRα -equilibrium, the mixed strategy of each player is a best-response. We establish two significant properties of CVaRα at equilibrium: (1) The Optimal-Value property: For any best-response of a player, each mixed strategy in the support gives the same cost to the player. This follows directly from the concavity of CVaRα in the involved probabilities, which we establish. (2) The Crawford property: For every α, there is a 2-player game with no CVaRα-equilibrium. The property is established using the Optimal-Value property and a new functional property of CVaRα, called Weak-Equilibrium-for- VaRα, we establish. On top of these properties, we show, as one of our two main results, that deciding the existence of a CVaRα-equilibrium is strongly NP-hard even for 2-player games. As our other main result, we show the strong NP-hardness of deciding the existence of a V-equilibrium, over 2-player games, for any valuation V with the Optimal-Value and the Crawford properties. This result has a rich potential since we prove that the very significant and broad class of strictly quasiconcave valuations has the Optimal-Value property.}}, author = {{Mavronicolas, Marios and Monien, Burkhard}}, booktitle = {{Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT 2017)}}, location = {{L'Aquila, Italy}}, pages = {{131----143}}, title = {{{Conditional Value-at-Risk: Structure and Complexity of Equilibria}}}, doi = {{10.1007/978-3-319-66700-3_11}}, volume = {{10504}}, year = {{2017}}, } @unpublished{17811, abstract = {{We consider a swarm of $n$ autonomous mobile robots, distributed on a 2-dimensional grid. A basic task for such a swarm is the gathering process: All robots have to gather at one (not predefined) place. A common local model for extremely simple robots is the following: The robots do not have a common compass, only have a constant viewing radius, are autonomous and indistinguishable, can move at most a constant distance in each step, cannot communicate, are oblivious and do not have flags or states. The only gathering algorithm under this robot model, with known runtime bounds, needs $\mathcal{O}(n^2)$ rounds and works in the Euclidean plane. The underlying time model for the algorithm is the fully synchronous $\mathcal{FSYNC}$ model. On the other side, in the case of the 2-dimensional grid, the only known gathering algorithms for the same time and a similar local model additionally require a constant memory, states and "flags" to communicate these states to neighbors in viewing range. They gather in time $\mathcal{O}(n)$. In this paper we contribute the (to the best of our knowledge) first gathering algorithm on the grid that works under the same simple local model as the above mentioned Euclidean plane strategy, i.e., without memory (oblivious), "flags" and states. We prove its correctness and an $\mathcal{O}(n^2)$ time bound in the fully synchronous $\mathcal{FSYNC}$ time model. This time bound matches the time bound of the best known algorithm for the Euclidean plane mentioned above. We say gathering is done if all robots are located within a $2\times 2$ square, because in $\mathcal{FSYNC}$ such configurations cannot be solved.}}, author = {{Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm}}, booktitle = {{arXiv:1702.03400}}, title = {{{Gathering Anonymous, Oblivious Robots on a Grid}}}, year = {{2017}}, } @inproceedings{2343, author = {{Löken, Nils}}, booktitle = {{Proceedings of the 12th International Conference on Availability, Reliability and Security - ARES '17}}, isbn = {{9781450352574}}, publisher = {{ACM Press}}, title = {{{Searchable Encryption with Access Control}}}, doi = {{10.1145/3098954.3098987}}, year = {{2017}}, } @inproceedings{2344, author = {{Blömer, Johannes and Günther, Peter and Krummel, Volker and Löken, Nils}}, booktitle = {{Foundations and Practice of Security}}, isbn = {{9783319756493}}, issn = {{0302-9743}}, pages = {{3--17}}, publisher = {{Springer International Publishing}}, title = {{{Attribute-Based Encryption as a Service for Access Control in Large-Scale Organizations}}}, doi = {{10.1007/978-3-319-75650-9_1}}, year = {{2017}}, } @inbook{2381, abstract = {{Metric facility location and K-means are well-known problems of combinatorial optimization. Both admit a fairly simple heuristic called single-swap, which adds, drops or swaps open facilities until it reaches a local optimum. For both problems, it is known that this algorithm produces a solution that is at most a constant factor worse than the respective global optimum. In this paper, we show that single-swap applied to the weighted metric uncapacitated facility location and weighted discrete K-means problem is tightly PLS-complete and hence has exponential worst-case running time.}}, author = {{Brauer, Sascha}}, booktitle = {{Lecture Notes in Computer Science}}, editor = {{Fotakis, Dimitris and Pagourtzis, Aris and Paschos, Vangelis Th.}}, isbn = {{9783319575858}}, issn = {{0302-9743}}, location = {{Athens, Greece}}, pages = {{116--127}}, publisher = {{Springer International Publishing}}, title = {{{Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems}}}, doi = {{10.1007/978-3-319-57586-5_11}}, volume = {{10236}}, year = {{2017}}, }