@phdthesis{1209, abstract = {{My dissertation deals with the Gathering problem for swarms of n point-shaped robots on a grid, in which all robots of the swarm are supposed to gather at a previously undefined point. Special attention is paid to the strong limitation of robot capabilities. These include in particular the lack of global control, a global compass, global visibility and (global) communication skills. Furthermore, all robots are identical. The robots are given only local abilities. This includes a constant range of vision. The robots all work completely synchronously. In this work we present and analyze three different Gathering strategies in different robot models. We formally prove correctness and total running time: Chapter 4 focuses on minimizing the available robot capabilities. The underlying strategy completes the gathering in O(n^2) time. For the following Chapters 5 and 6, the aim is to optimize the total running time under using only local robot capabilities: We additionally allow a constant-sized memory and a constant number of locally visible statuses (lights, flags). For the strategies of both chapters we show an asymptotically optimal running time of O(n). Unlike in Chapters 4 and 5, we additionally restrict connectivity and vision to an initially given chain connectivity in Chapter 6, where two chain neighbors must have a distance of 1 from each other. A robot can only see and interact with a constant number of its direct chain neighbors.}}, author = {{Jung, Daniel}}, isbn = {{978-3-942647-99-1}}, publisher = {{Universität Paderborn}}, title = {{{Local Strategies for Swarm Formations on a Grid}}}, doi = {{10.17619/UNIPB/1-271}}, year = {{2018}}, } @inproceedings{8162, abstract = {{The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry; we hope these prove useful elsewhere.}}, author = {{Aldi, Marco and de Beaudrap, Niel and Gharibian, Sevag and Saeedi, Seyran}}, booktitle = {{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}}, editor = {{Potapov, Igor and Spirakis, Paul and Worrell, James}}, keywords = {{search complexity, local Hamiltonian, Quantum SAT, algebraic geometry}}, location = {{Liverpool, UK}}, pages = {{38:1--38:16}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}}, title = {{{On Efficiently Solvable Cases of Quantum k-SAT}}}, doi = {{10.4230/LIPIcs.MFCS.2018.38}}, volume = {{117}}, year = {{2018}}, } @inproceedings{8161, abstract = {{The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH does not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, QCPH, uses classical proofs, and the second, QPH, uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, Q Sigma_3, into NEXP using the Ellipsoid Method for efficiently solving semidefinite programs. These results yield two implications for QMA(2), the variant of Quantum Merlin-Arthur (QMA) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs "equivalent"), then QMA(2) is in the Counting Hierarchy (specifically, in P^{PP^{PP}}). Second, unless QMA(2)= Q Sigma_3 (i.e., alternating quantifiers do not help in the presence of "unentanglement"), QMA(2) is strictly contained in NEXP.}}, author = {{Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi and Yirka, Justin}}, booktitle = {{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}}, editor = {{Potapov, Igor and Spirakis, Paul and Worrell, James}}, keywords = {{Complexity Theory, Quantum Computing, Polynomial Hierarchy, Semidefinite Programming, QMA(2), Quantum Complexity}}, location = {{Liverpool, UK}}, pages = {{58:1--58:16}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}}, title = {{{Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)}}}, doi = {{10.4230/LIPIcs.MFCS.2018.58}}, volume = {{117}}, year = {{2018}}, } @inproceedings{8160, abstract = {{An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, Ambainis defined the complexity class P^QMA[log], and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is P^QMA[log]-complete. In this paper, we continue the study of P^QMA[log], obtaining the following results. The P^QMA[log]-completeness result of Ambainis requires O(log n)-local observ- ables and Hamiltonians. We show that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete, resolving an open question of Ambainis. We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is similarly P^QMA[log]-complete. P^QMA[log] is thought of as "slightly harder" than QMA. We justify this formally by exploiting the hierarchical voting technique of Beigel, Hemachandra, and Wechsung to show P^QMA[log] \subseteq PP. This improves the containment QMA \subseteq PP from Kitaev and Watrous. A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, we identify a flaw in Ambainis' prior work regarding a P^UQMA[log]-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a "query validation" technique, we build on his prior work to obtain P^UQMA[log]-hardness for estimating spectral gaps under polynomial-time Turing reductions.}}, author = {{Gharibian, Sevag and Yirka, Justin}}, booktitle = {{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)}}, editor = {{Wilde, Mark}}, keywords = {{Complexity theory, Quantum Merlin Arthur (QMA), local Hamiltonian, local measurement, spectral gap}}, location = {{Paris, France}}, pages = {{2:1--2:17}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}}, title = {{{The Complexity of Simulating Local Measurements on Quantum Systems}}}, doi = {{10.4230/LIPIcs.TQC.2017.2}}, volume = {{73}}, year = {{2018}}, } @article{8167, author = {{Gharibian, Sevag and Sikora, Jamie}}, issn = {{1942-3454}}, journal = {{ACM Transactions on Computation Theory (TOCT)}}, keywords = {{Local Hamiltonian, ground state connectivity, quantum Hamiltonian complexity, reconfiguration problem}}, number = {{2}}, pages = {{8:1--8:28}}, publisher = {{ACM}}, title = {{{Ground State Connectivity of Local Hamiltonians}}}, doi = {{10.1145/3186587}}, volume = {{10}}, year = {{2018}}, } @inproceedings{1588, abstract = {{The exploration of FPGAs as accelerators for scientific simulations has so far mostly been focused on small kernels of methods working on regular data structures, for example in the form of stencil computations for finite difference methods. In computational sciences, often more advanced methods are employed that promise better stability, convergence, locality and scaling. Unstructured meshes are shown to be more effective and more accurate, compared to regular grids, in representing computation domains of various shapes. Using unstructured meshes, the discontinuous Galerkin method preserves the ability to perform explicit local update operations for simulations in the time domain. In this work, we investigate FPGAs as target platform for an implementation of the nodal discontinuous Galerkin method to find time-domain solutions of Maxwell's equations in an unstructured mesh. When maximizing data reuse and fitting constant coefficients into suitably partitioned on-chip memory, high computational intensity allows us to implement and feed wide data paths with hundreds of floating point operators. By decoupling off-chip memory accesses from the computations, high memory bandwidth can be sustained, even for the irregular access pattern required by parts of the application. Using the Intel/Altera OpenCL SDK for FPGAs, we present different implementation variants for different polynomial orders of the method. In different phases of the algorithm, either computational or bandwidth limits of the Arria 10 platform are almost reached, thus outperforming a highly multithreaded CPU implementation by around 2x.}}, author = {{Kenter, Tobias and Mahale, Gopinath and Alhaddad, Samer and Grynko, Yevgen and Schmitt, Christian and Afzal, Ayesha and Hannig, Frank and Förstner, Jens and Plessl, Christian}}, booktitle = {{Proc. Int. Symp. on Field-Programmable Custom Computing Machines (FCCM)}}, keywords = {{tet_topic_hpc}}, publisher = {{IEEE}}, title = {{{OpenCL-based FPGA Design to Accelerate the Nodal Discontinuous Galerkin Method for Unstructured Meshes}}}, doi = {{10.1109/FCCM.2018.00037}}, year = {{2018}}, } @inproceedings{1590, abstract = {{We present the submatrix method, a highly parallelizable method for the approximate calculation of inverse p-th roots of large sparse symmetric matrices which are required in different scientific applications. Following the idea of Approximate Computing, we allow imprecision in the final result in order to utilize the sparsity of the input matrix and to allow massively parallel execution. For an n x n matrix, the proposed algorithm allows to distribute the calculations over n nodes with only little communication overhead. The result matrix exhibits the same sparsity pattern as the input matrix, allowing for efficient reuse of allocated data structures. We evaluate the algorithm with respect to the error that it introduces into calculated results, as well as its performance and scalability. We demonstrate that the error is relatively limited for well-conditioned matrices and that results are still valuable for error-resilient applications like preconditioning even for ill-conditioned matrices. We discuss the execution time and scaling of the algorithm on a theoretical level and present a distributed implementation of the algorithm using MPI and OpenMP. We demonstrate the scalability of this implementation by running it on a high-performance compute cluster comprised of 1024 CPU cores, showing a speedup of 665x compared to single-threaded execution.}}, author = {{Lass, Michael and Mohr, Stephan and Wiebeler, Hendrik and Kühne, Thomas and Plessl, Christian}}, booktitle = {{Proc. Platform for Advanced Scientific Computing (PASC) Conference}}, isbn = {{978-1-4503-5891-0/18/07}}, keywords = {{approximate computing, linear algebra, matrix inversion, matrix p-th roots, numeric algorithm, parallel computing}}, location = {{Basel, Switzerland}}, publisher = {{ACM}}, title = {{{A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices}}}, doi = {{10.1145/3218176.3218231}}, year = {{2018}}, } @inproceedings{1204, author = {{Riebler, Heinrich and Vaz, Gavin Francis and Kenter, Tobias and Plessl, Christian}}, booktitle = {{Proc. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)}}, isbn = {{9781450349826}}, keywords = {{htrop}}, publisher = {{ACM}}, title = {{{Automated Code Acceleration Targeting Heterogeneous OpenCL Devices}}}, doi = {{10.1145/3178487.3178534}}, year = {{2018}}, } @inproceedings{56157, author = {{Schulte, Carsten and Krüger, Jessica and Gödecke, Andreas and Schmidt, Ann-Katrin}}, booktitle = {{Proceedings of the 13th Workshop in Primary and Secondary Computing Education}}, publisher = {{ACM}}, title = {{{The computing repair cafe}}}, doi = {{10.1145/3265757.3265781}}, year = {{2018}}, } @inproceedings{15646, author = {{Heinemann, Birte and Opel, Simone Anna and Budde, Lea and Schulte, Carsten and Frischemeier, Daniel and Biehler, Rolf and Podworny, Susanne and Wassong, Thomas}}, booktitle = {{Koli Calling}}, pages = {{17:1--17:5}}, publisher = {{ACM}}, title = {{{Drafting a Data Science Curriculum for Secondary Schools}}}, year = {{2018}}, } @inproceedings{46539, abstract = {{This paper describes the Ontology Alignment Evaluation Initiative 2017.5 pre-campaign. Like in 2012, when we transitioned the evaluation to the SEALS platform, we have also conducted a pre-campaign to assess the feasibility of moving to the HOBBIT platform. We report the experiences of this precampaign and discuss the future steps for the OAEI.}}, author = {{Jiménez-Ruiz, Ernesto and Saveta, Tzanina and Zamazal, Ondrej and Hertling, Sven and Röder, Michael and Fundulaki, Irini and Ngonga Ngomo, Axel-Cyrille and Sherif, Mohamed and Annane, Amina and Bellahsene, Zohra and Yahia, Sadok Ben and Diallo, Gayo and Faria, Daniel and Kachroudi, Marouen and Khiat, Abderrahmane and Lambrix, Patrick and Li, Huanyu and Mackeprang, Maximilian and Mohammadi, Majid and Rybinski, Maciej and Balasubramani, Booma Sowkarthiga and Trojahn, Cassia}}, booktitle = {{Proceedings of the Ontology Matching Workshop 2018}}, keywords = {{2018 DICE SIMBA group_aksw ngonga projecthobbit roeder sherif}}, title = {{{Introducing the HOBBIT platform into the Ontology Alignment Evaluation Campaign}}}, year = {{2018}}, } @inproceedings{60448, author = {{Lim, Isaak and Dielen, Alexander and Campen, Marcel and Kobbelt, Leif}}, booktitle = {{Computer Vision - ECCV 2018 Workshops - Munich, Germany, September 8-14, 2018, Proceedings, Part III}}, editor = {{Leal-Taixé, Laura and Roth, Stefan}}, pages = {{349–362}}, publisher = {{Springer}}, title = {{{A Simple Approach to Intrinsic Correspondence Learning on Unstructured 3D Meshes}}}, doi = {{10.1007/978-3-030-11015-4_26}}, volume = {{11131}}, year = {{2018}}, } @article{60391, author = {{Zhou, Jiaran and Campen, Marcel and Zorin, Denis and Tu, Changhe and Silva, Claudio T.}}, issn = {{0167-8396}}, journal = {{Computer Aided Geometric Design}}, pages = {{3--15}}, publisher = {{Elsevier BV}}, title = {{{Quadrangulation of non-rigid objects using deformation metrics}}}, doi = {{10.1016/j.cagd.2018.03.003}}, volume = {{62}}, year = {{2018}}, } @misc{15596, abstract = {{Data science is increasingly relevant in more and more areas of everyday life - but the general education at school so far has hardly responded to these specific changes in digitalization. Completely new challenges for the teaching of mathematics and computer science have emerged, as well as for the subjects of the social and cultural sciences field and for cross-curricular media education. All these subjects have to be reinterpreted in regard to the raising attention to data science, to big data and in regard to a fundamentally changing world of labor and economy. As a reaction, schools have to realize a broad general education that is to be newly defined on the one hand. On the other hand, school education has to stimulate and promote interest in the current, exciting and dynamic new scientific area of data science with its numerous applications. This book presents the extended abstracts of the presentations at a symposium held in November 2017, discussing economic, social and cultural impacts of big data and data science with experts in curriculum development and educational research in statistics and computer science as well as experts from different facets of data science and its applications. Moreover, analyses from a socio-cultural perspective were included. The main goal was to inspire ideas for teaching data science in secondary schools.}}, author = {{Biehler, Rolf and Budde, Lea and Frischemeier, Daniel and Heinemann, Birte and Podworny, Susanne and Schulte, Carsten and Wassong, Thomas}}, pages = {{109}}, publisher = {{Paderborn University}}, title = {{{Paderborn Symposium on Data Science Education at School Level 2017: The Collected Extended Abstracts}}}, doi = {{10.17619/UNIPB/1-374}}, year = {{2018}}, } @phdthesis{19604, author = {{Li, Shouwei}}, title = {{{Parallel fixed parameter tractable problems}}}, doi = {{10.17619/UNIPB/1-252}}, year = {{2017}}, } @inproceedings{2851, author = {{Markarian, Christine}}, booktitle = {{International Conference on Operations Research (OR)}}, location = {{Berlin}}, title = {{{Leasing with Uncertainty}}}, doi = {{10.1007/978-3-319-89920-6_57}}, year = {{2017}}, } @article{24152, author = {{Ramaswamy, Arunselvan and Bhatnagar, Shalabh}}, journal = {{IEEE Transactions on Automatic Control}}, number = {{5}}, pages = {{1465--1471}}, publisher = {{IEEE}}, title = {{{Analysis of gradient descent methods with nondiminishing bounded errors}}}, volume = {{63}}, year = {{2017}}, } @article{24153, author = {{Ramaswamy, Arunselvan and Bhatnagar, Shalabh}}, journal = {{Mathematics of Operations Research}}, number = {{3}}, pages = {{648--661}}, publisher = {{INFORMS}}, title = {{{A generalization of the Borkar-Meyn theorem for stochastic recursive inclusions}}}, volume = {{42}}, year = {{2017}}, } @inproceedings{24398, abstract = {{Through this study, we introduce the idea of applying scheduling techniques to allocate spatial resources that are shared among multiple robots moving in a static environment and having temporal constraints on the arrival time to destinations. To illustrate this idea, we present an exemplified algorithm that plans and assigns a motion path to each robot. The considered problem is particularly challenging because: (i) the robots share the same environment and thus the planner must take into account overlapping paths which cannot happen at the same time; (ii) there are time deadlines thus the planner must deal with temporal constraints; (iii) new requests arrive without a priori knowledge thus the planner must be able to add new paths online and adjust old plans; (iv) the robot motion is subject to noise thus the planner must be reactive to adapt to online changes. We showcase the functioning of the proposed algorithm through a set of agent-based simulations.}}, author = {{Khaluf, Yara and Markarian, Christine and Simoens, Pieter and Reina, Andreagiovanni}}, booktitle = {{International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS 2017)}}, issn = {{0302-9743}}, title = {{{Scheduling Access to Shared Space in Multi-robot Systems}}}, doi = {{10.1007/978-3-319-59930-4_12}}, year = {{2017}}, } @article{26426, author = {{Hadjakos, Aristotelis and Iffland, Joachim and Keil, Reinhard and Oberhoff, Andreas and Veit, Joachim}}, journal = {{International Journal of Humanities and Arts Computing}}, pages = {{255--275}}, title = {{{Challenges for Annotation Concepts in Music}}}, volume = {{11:2}}, year = {{2017}}, }