@article{60189, abstract = {{AbstractSeveral state‐of‐the‐art algorithms for semi‐structured hexahedral meshing involve a so called quantization step to decide on the integer DoFs of the meshing problem, corresponding to the number of hexahedral elements to embed into certain regions of the domain. Existing reliable methods for quantization are based on solving a sequence of integer quadratic programs (IQP). Solving these in a timely and predictable manner with general‐purpose solvers is a challenge, even more so in the open‐source field. We present here an alternative robust and efficient quantization scheme that is instead based on solving a series of continuous linear programs (LP), for which solver availability and efficiency are not an issue. In our formulation, such LPs are used to determine where inflation or deflation of virtual hexahedral sheets are favorable. We compare our method to two implementations of the former IQP formulation (using a commercial and an open‐source MIP solver, respectively), finding that (a) the solutions found by our method are near‐optimal or optimal in most cases, (b) these solutions are found within a much more predictable time frame, and (c) the state of the art run time is outperformed, in the case of using the open‐source solver by orders of magnitude.}}, author = {{Brückler, Hendrik and Bommes, David and Campen, Marcel}}, issn = {{0167-7055}}, journal = {{Comput. Graph. Forum}}, number = {{5}}, publisher = {{Wiley}}, title = {{{Integer‐Sheet‐Pump Quantization for Hexahedral Meshing}}}, doi = {{10.1111/cgf.15131}}, volume = {{43}}, year = {{2024}}, } @article{60240, author = {{Ludwig, Ingmar and Campen, Marcel}}, journal = {{Comput. Graph. Forum}}, number = {{7}}, pages = {{i–xxii}}, title = {{{Strictly Conservative Neural Implicits}}}, doi = {{10.1111/CGF.15241}}, volume = {{43}}, year = {{2024}}, } @article{60314, abstract = {{A method for the construction of bijective volumetric maps between 3D shapes is presented. Arbitrary shapes of ball-topology are supported, overcoming restrictions of previous methods to convex or star-shaped targets. In essence, the mapping problem is decomposed into a set of simpler mapping problems, each of which can be solved with previous methods for discrete star-shaped mapping problems. Addressing the key challenges in this endeavor, algorithms are described to reliably construct structurally compatible partitions of two shapes with constraints regarding star-shapedness and to compute a parsimonious common refinement of two triangulations.}}, author = {{Hinderink, Steffen and Brückler, Hendrik and Campen, Marcel}}, issn = {{0730-0301}}, journal = {{ACM Transactions on Graphics}}, number = {{6}}, pages = {{1--11}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{{Bijective Volumetric Mapping via Star Decomposition}}}, doi = {{10.1145/3687950}}, volume = {{43}}, year = {{2024}}, } @article{60331, abstract = {{ We present a novel algorithm to map ball-topology tetrahedral meshes onto star-shaped domains with guarantees regarding bijectivity. Our algorithm is based on the recently introduced idea of Shrink-and-Expand, where images of interior vertices are initially clustered at one point (Shrink-), before being sequentially moved to non-degenerate positions yielding a bijective map (-and-Expand). In this context, we introduce the concept of the cluster mesh , i.e. the unexpanded interior mesh consisting of geometrically degenerate simplices. Using local, per-vertex connectivity information solely from the cluster mesh, we show that a viable expansion sequence guaranteed to produce a bijective map can always be found as long as the mesh is shellable. In addition to robustness guarantees for this ubiquitous class of inputs, other practically relevant benefits include improved parsimony and reduced algorithmic complexity. While inheriting some of the worst-case high run time requirements of the state of the art, significant acceleration for the average case is experimentally demonstrated. }}, author = {{Nigolian, Valentin Zénon and Campen, Marcel and Bommes, David}}, issn = {{0730-0301}}, journal = {{ACM Transactions on Graphics}}, number = {{6}}, pages = {{1--14}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{{A Progressive Embedding Approach to Bijective Tetrahedral Maps driven by Cluster Mesh Topology}}}, doi = {{10.1145/3687992}}, volume = {{43}}, year = {{2024}}, } @inproceedings{55637, author = {{Kostan, Anastassija and Olschar, Sara and Simko, Lucy and Acar, Yasemin}}, booktitle = {{33rd USENIX Security Symposium, USENIX Security 2024, Philadelphia, PA, USA, August 14-16, 2024}}, editor = {{Balzarotti, Davide and Xu, Wenyuan}}, publisher = {{USENIX Association}}, title = {{{Exploring digital security and privacy in relative poverty in Germany through qualitative interviews}}}, year = {{2024}}, } @article{61172, author = {{Coy, Sam and Czumaj, Artur and Scheideler, Christian and Schneider, Philipp and Werthmann, Julian}}, issn = {{0304-3975}}, journal = {{Theoretical Computer Science}}, publisher = {{Elsevier BV}}, title = {{{Routing Schemes for Hybrid Communication Networks}}}, doi = {{10.1016/j.tcs.2023.114352}}, volume = {{985}}, year = {{2024}}, } @inproceedings{58377, abstract = {{The connection between inconsistent databases and Dung's abstract argumentation framework has recently drawn growing interest. Specifically, an inconsistent database, involving certain types of integrity constraints such as functional and inclusion dependencies, can be viewed as an argumentation framework in Dung's setting. Nevertheless, no prior work has explored the exact expressive power of Dung's theory of argumentation when compared to inconsistent databases and integrity constraints. In this paper, we close this gap by arguing that an argumentation framework can also be viewed as an inconsistent database. We first establish a connection between subset-repairs for databases and extensions for AFs, considering conflict-free, naive, admissible, and preferred semantics. Further, we define a new family of attribute-based repairs based on the principle of maximal content preservation. The effectiveness of these repairs is then highlighted by connecting them to stable, semi-stable, and stage semantics. Our main contributions include translating an argumentation framework into a database together with integrity constraints. Moreover, this translation can be achieved in polynomial time, which is essential in transferring complexity results between the two formalisms.}}, author = {{Mahmood, Yasir and Hecher, Markus and Ngonga Ngomo, Axel-Cyrille}}, title = {{{Dung's Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases}}}, doi = {{10.1609/AAAI.V39I14.33651}}, year = {{2024}}, } @inbook{57238, abstract = {{Abstract argumentation is a popular toolkit for modeling, evaluating, and comparing arguments. Relationships between arguments are specified in argumentation frameworks (AFs), and conditions are placed on sets (extensions) of arguments that allow AFs to be evaluated. For more expressiveness, AFs are augmented with acceptance conditions on directly interacting arguments or a constraint on the admissible sets of arguments, resulting in dialectic frameworks or constrained argumentation frameworks. In this paper, we consider flexible conditions for rejecting an argument from an extension, which we call rejection conditions (RCs). On the technical level, we associate each argument with a specific logic program. We analyze the resulting complexity, including the structural parameter treewidth. Rejection AFs are highly expressive, giving rise to natural problems on higher levels of the polynomial hierarchy.}}, author = {{Fichte, Johannes K. and Hecher, Markus and Mahmood, Yasir and Meier, Arne}}, booktitle = {{Frontiers in Artificial Intelligence and Applications}}, isbn = {{9781643685489}}, issn = {{0922-6389}}, location = {{Santiago de Compostela, Spain}}, publisher = {{IOS Press}}, title = {{{Rejection in Abstract Argumentation: Harder Than Acceptance?}}}, doi = {{10.3233/faia240867}}, year = {{2024}}, } @inproceedings{55655, abstract = {{Argumentation is a well-established formalism for nonmonotonic reasoning, with popular frameworks being Dung’s abstract argumentation (AFs) or logic-based argumentation (Besnard-Hunter’s framework). Structurally, a set of formulas forms support for a claim if it is consistent, subset-minimal, and implies the claim. Then, an argument comprises support and a claim. We observe that the computational task (ARG) of asking for support of a claim in a knowledge base is “brave”, since many claims with a single support are accepted. As a result, ARG falls short when it comes to the question of confidence in a claim, or claim strength. In this paper, we propose a concept for measuring the (acceptance) strength of claims, based on counting supports for a claim. Further, we settle classical and structural complexity of counting arguments favoring a given claim in propositional knowledge bases (KBs). We introduce quantitative reasoning to measure the strength of claims in a KB and to determine the relevance strength of a formula for a claim.}}, author = {{Hecher, Markus and Mahmood, Yasir and Meier, Arne and Schmidt, Johannes}}, booktitle = {{Proceedings of the Thirty-ThirdInternational Joint Conference on Artificial Intelligence}}, publisher = {{International Joint Conferences on Artificial Intelligence Organization}}, title = {{{Quantitative Claim-Centric Reasoning in Logic-Based Argumentation}}}, doi = {{10.24963/ijcai.2024/377}}, year = {{2024}}, } @unpublished{57814, abstract = {{We study consistent query answering via different graph representations. First, we introduce solution-conflict hypergraphs in which nodes represent facts and edges represent either conflicts or query solutions. Considering a monotonic query and a set of antimonotonic constraints, we present an explicit algorithm for counting the number of repairs satisfying the query based on a tree decomposition of the solution-conflict hypergraph. The algorithm not only provides fixed-parameter tractability results for data complexity over expressive query and constraint classes, but also introduces a novel and potentially implementable approach to repair counting. Second, we consider the Gaifman graphs arising from MSO descriptions of consistent query answering. Using a generalization of Courcelle's theorem, we then present fixed-parameter tractability results for combined complexity over expressive query and constraint classes.}}, author = {{Hankala, Teemu and Hannula, Miika and Mahmood, Yasir and Meier, Arne}}, booktitle = {{arXiv:2412.08324}}, title = {{{Parameterised Complexity of Consistent Query Answering via Graph Representations}}}, year = {{2024}}, } @inproceedings{56140, abstract = {{ Android apps collecting data from users must comply with legal frameworks to ensure data protection. This requirement has become even more important since the implementation of the General Data Protection Regulation (GDPR) by the European Union in 2018. Moreover, with the proposed Cyber Resilience Act on the horizon, stakeholders will soon need to assess software against even more stringent security and privacy standards. Effective privacy assessments require collaboration among groups with diverse expertise to function effectively as a cohesive unit. This paper motivates the need for an automated approach that enhances understanding of data protection in Android apps and improves communication between the various parties involved in privacy assessments. We propose the Assessor View, a tool designed to bridge the knowledge gap between these parties, facilitating more effective privacy assessments of Android applications. }}, author = {{Khedkar, Mugdha and Schlichtig, Michael and Bodden, Eric}}, booktitle = {{In Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering Workshops (ASEW ’24)}}, location = {{Sacramento, California}}, title = {{{Advancing Android Privacy Assessments with Automation}}}, doi = {{10.1145/3691621.3694953}}, year = {{2024}}, } @inproceedings{63658, author = {{Klüttermann, Simon and Rutinowski, Jérôme and Polachowski, Frederik and Nguyen, Anh and Grimme, Britta and Roidl, Moritz and Müller, Emmanuel}}, booktitle = {{2024 International Conference on Machine Learning and Applications (ICMLA)}}, pages = {{1705–1711}}, title = {{{On the Effectiveness of Heterogeneous Ensemble Methods for Re-identification}}}, year = {{2024}}, } @article{52587, author = {{Bodden, Eric and Pottebaum, Jens and Fockel, Markus and Gräßler, Iris}}, issn = {{1540-7993}}, journal = {{IEEE Security & Privacy}}, keywords = {{Law, Electrical and Electronic Engineering, Computer Networks and Communications}}, number = {{1}}, pages = {{69--72}}, publisher = {{Institute of Electrical and Electronics Engineers (IEEE)}}, title = {{{Evaluating Security Through Isolation and Defense in Depth}}}, doi = {{10.1109/msec.2023.3336028}}, volume = {{22}}, year = {{2024}}, } @inproceedings{56481, author = {{Berganski, Christoph and Jentzsch, Felix and Platzner, Marco and Kuhmichel, Max and Giefers, Heiner}}, location = {{Sydney}}, title = {{{FINN-T: Compiling Custom Dataflow Accelerators for Quantized Transformers}}}, year = {{2024}}, } @misc{54245, author = {{Henke, Luca-Sebastian}}, title = {{{Exploring Custom FPGA Accelerators for DNN-based RF Fingerprinting}}}, year = {{2024}}, } @inproceedings{50273, abstract = {{The Polynomial-Time Hierarchy ($\mathsf{PH}$) is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum advantage'' analyses for near-term quantum computers. Quantumly, however, despite the fact that at least \emph{four} definitions of quantum $\mathsf{PH}$ exist, it has been challenging to prove analogues for these of even basic facts from $\mathsf{PH}$. This work studies three quantum-verifier based generalizations of $\mathsf{PH}$, two of which are from [Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings ($\mathsf{QCPH}$) and quantum mixed states ($\mathsf{QPH}$) as proofs, and one of which is new to this work, utilizing quantum pure states ($\mathsf{pureQPH}$) as proofs. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for $\mathsf{QCPH}$. Then, for our new class $\mathsf{pureQPH}$, we show one-sided error reduction for $\mathsf{pureQPH}$, as well as the first bounds relating these quantum variants of $\mathsf{PH}$, namely $\mathsf{QCPH}\subseteq \mathsf{pureQPH} \subseteq \mathsf{EXP}^{\mathsf{PP}}$.}}, author = {{Agarwal, Avantika and Gharibian, Sevag and Koppula, Venkata and Rudolph, Dorian}}, booktitle = {{Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS)}}, number = {{7}}, pages = {{7--17}}, title = {{{Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds}}}, doi = {{10.4230/LIPIcs.MFCS.2024.7}}, volume = {{306}}, year = {{2024}}, } @inproceedings{50406, abstract = {{What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $\Theta(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $\Theta(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $\Omega(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $\Omega(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.}}, author = {{Gharibian, Sevag and Kamminga, Jonas}}, booktitle = {{Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP)}}, number = {{70}}, pages = {{1--19}}, title = {{{BQP, meet NP: Search-to-decision reductions and approximate counting}}}, volume = {{297}}, year = {{2024}}, } @unpublished{56944, abstract = {{Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic Heisenberg model, is a QMA-complete problem relevant to quantum many-body physics and computer science. Semidefinite programming relaxations have been fruitful in designing theoretical approximation algorithms for QMC, but are computationally expensive for systems beyond tens of qubits. We give a second order cone relaxation for QMC, which optimizes over the set of mutually consistent three-qubit reduced density matrices. In combination with Pauli level-$1$ of the quantum Lasserre hierarchy, the relaxation achieves an approximation ratio of $0.526$ to the ground state energy. Our relaxation is solvable on systems with hundreds of qubits and paves the way to computationally efficient lower and upper bounds on the ground state energy of large-scale quantum spin systems.}}, author = {{Huber, Felix and Thompson, Kevin and Parekh, Ojas and Gharibian, Sevag}}, booktitle = {{arXiv:2411.04120}}, title = {{{Second order cone relaxations for quantum Max Cut}}}, year = {{2024}}, } @article{48544, abstract = {{When it comes to NP, its natural definition, its wide applicability across scientific disciplines, and its timeless relevance, the writing is on the wall: There can be only one. Quantum NP, on the other hand, is clearly the apple that fell far from the tree of NP. Two decades since the first definitions of quantum NP started rolling in, quantum complexity theorists face a stark reality: There's QMA, QCMA, QMA1, QMA(2), StoqMA, and NQP. In this article aimed at a general theoretical computer science audience, I survey these various definitions of quantum NP, their strengths and weaknesses, and why most of them, for better or worse, actually appear to fit naturally into the complexity zoo.}}, author = {{Gharibian, Sevag}}, journal = {{ACM SIGACT News}}, number = {{4}}, pages = {{54--91}}, title = {{{Guest Column: The 7 faces of quantum NP}}}, volume = {{54}}, year = {{2024}}, } @inbook{62702, abstract = {{Clifford algebras are a natural extension of division algebras, including real numbers, complex numbers, quaternions, and octonions. Previous research in knowledge graph embeddings has focused exclusively on Clifford algebras of a specific type, which do not include nilpotent base vectors—elements that square to zero. In this work, we introduce a novel approach by incorporating nilpotent base vectors with a nilpotency index of two, leading to a more general form of Clifford algebras named degenerate Clifford algebras. This generalization to degenerate Clifford algebras does allow for covering dual numbers and as such include translations and rotations models under the same generalization paradigm for the first time. We develop two models to determine the parameters that define the algebra: one using a greedy search and another predicting the parameters based on neural network embeddings of the input knowledge graph. Our evaluation on seven benchmark datasets demonstrates that this incorporation of nilpotent vectors enhances the quality of embeddings. Additionally, our method outperforms state-of-the-art approaches in terms of generalization, particularly regarding the mean reciprocal rank achieved on validation data. Finally, we show that even a simple greedy search can effectively discover optimal or near-optimal parameters for the algebra.}}, author = {{Kamdem Teyou, Louis Mozart and Demir, Caglar and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{Frontiers in Artificial Intelligence and Applications}}, isbn = {{9781643685489}}, issn = {{0922-6389}}, location = {{Santiago de Compostela}}, publisher = {{IOS Press}}, title = {{{Embedding Knowledge Graphs in Degenerate Clifford Algebras}}}, doi = {{10.3233/faia240627}}, year = {{2024}}, }