@inproceedings{27160, abstract = {{We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$ and $P^{QMA}$, respectively. The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate Simulation (APX-SIM) [Ambainis, CCC 2014]. In this area, a central role has been played by the classes $P^{NP[\log]}$ and $P^{QMA[\log]}$, defined identically to $P^{NP}$ and $P^{QMA}$, except that only logarithmically many oracle queries are allowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by a $P^{NP}$ machine have a "query graph" which is a tree, then this computation can be simulated in $P^{NP[\log]}$. In this work, we first show that for any verification class $C\in\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\exp}\}$, any $P^C$ machine with a query graph of "separator number" $s$ can be simulated using deterministic time $\exp(s\log n)$ and $s\log n$ queries to a $C$-oracle. When $s\in O(1)$ (which includes the case of $O(1)$-treewidth, and thus also of trees), this gives an upper bound of $P^{C[\log]}$, and when $s\in O(\log^k(n))$, this yields bound $QP^{C[\log^{k+1}]}$ (QP meaning quasi-polynomial time). We next show how to combine Gottlob's "admissible-weighting function" framework with the "flag-qubit" framework of [Watson, Bausch, Gharibian, 2020], obtaining a unified approach for embedding $P^C$ computations directly into APX-SIM instances in a black-box fashion. Finally, we formalize a simple no-go statement about polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear polynomial $p$ specified via an arithmetic circuit, if one can "weakly compress" $p$ so that its optimal value requires $m$ bits to represent, then $P^{NP}$ can be decided with only $m$ queries to an NP-oracle.}}, author = {{Gharibian, Sevag and Rudolph, Dorian}}, booktitle = {{13th Innovations in Theoretical Computer Science (ITCS 2022)}}, number = {{75}}, pages = {{1--27}}, title = {{{On polynomially many queries to NP or QMA oracles}}}, doi = {{10.4230/LIPIcs.ITCS.2022.75}}, volume = {{215}}, year = {{2022}}, } @unpublished{44537, author = {{Burban, Igor and Alfes-Neumann, C. and Raum, M.}}, title = {{{A classification of polyharmonic Maaß forms via quiver representations}}}, year = {{2022}}, } @article{24721, author = {{Fathi Ahmed, Abdullah and Ahmed Sherif, Mohamed and Moussallem, Diego and Ngonga Ngomo, Axel-Cyrille}}, journal = {{Data Knowl. Eng.}}, pages = {{101874}}, title = {{{Multilingual Verbalization and Summarization for Explainable Link Discovery}}}, doi = {{10.1016/j.datak.2021.101874}}, volume = {{133}}, year = {{2021}}, } @inproceedings{24722, author = {{Röder, Michael and Frerk, Philip and Conrads, Felix and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{The Semantic Web - 18th International Conference, {ESWC} 2021, Virtual Event, June 6-10, 2021, Proceedings}}, editor = {{Verborgh, Ruben and Hose, Katja and Paulheim, Heiko and Champin, Pierre-Antoine and Maleshkova, Maria and Corcho, Oscar and Ristoski, Petar and Alam, Mehwish}}, pages = {{93--108}}, publisher = {{Springer}}, title = {{{Applying Grammar-Based Compression to RDF}}}, doi = {{10.1007/978-3-030-77385-4\_6}}, volume = {{12731}}, year = {{2021}}, } @inproceedings{24723, author = {{Ali, Manzoor and Saleem, Muhammad and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{The Semantic Web: {ESWC} 2021 Satellite Events - Virtual Event, June 6-10, 2021, Revised Selected Papers}}, editor = {{Verborgh, Ruben and Dimou, Anastasia and Hogan, Aidan and d'Amato, Claudia and Tiddi, Ilaria and Br{\"{o}}ring, Arne and Maier, Simon and Ongenae, Femke and Tommasini, Riccardo and Alam, Mehwish}}, pages = {{136--140}}, publisher = {{Springer}}, title = {{{Unsupervised Relation Extraction Using Sentence Encoding}}}, doi = {{10.1007/978-3-030-80418-3\_25}}, volume = {{12739}}, year = {{2021}}, } @inproceedings{24724, author = {{Ali, Manzoor and Saleem, Muhammad and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{The Semantic Web: {ESWC} 2021 Satellite Events - Virtual Event, June 6-10, 2021, Revised Selected Papers}}, editor = {{Verborgh, Ruben and Dimou, Anastasia and Hogan, Aidan and d'Amato, Claudia and Tiddi, Ilaria and Br{\"{o}}ring, Arne and Maier, Simon and Ongenae, Femke and Tommasini, Riccardo and Alam, Mehwish}}, pages = {{136--140}}, publisher = {{Springer}}, title = {{{Unsupervised Relation Extraction Using Sentence Encoding}}}, doi = {{10.1007/978-3-030-80418-3\_25}}, volume = {{12739}}, year = {{2021}}, } @inproceedings{24725, author = {{Shahzad, Moemmur and Amin, Ayesha and Esteves, Diego and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{Proceedings of the Thirty-Fourth International Florida Artificial Intelligence Research Society Conference, North Miami Beach, Florida, USA, May 17-19, 2021}}, editor = {{Bell, Eric and Keshtkar, Fazel}}, title = {{{InferNER: an attentive model leveraging the sentence-level information for Named Entity Recognition in Microblogs}}}, doi = {{10.32473/flairs.v34i1.128538}}, year = {{2021}}, } @inproceedings{24726, author = {{Röder, Michael and Thuy Sy Nguyen, Pham and Conrads, Felix and Alexandra Morim da Silva, Ana and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{15th {IEEE} International Conference on Semantic Computing, {ICSC} 2021, Laguna Hills, CA, USA, January 27-29, 2021}}, pages = {{62--69}}, publisher = {{{IEEE}}}, title = {{{Lemming - Example-based Mimicking of Knowledge Graphs}}}, doi = {{10.1109/ICSC50631.2021.00015}}, year = {{2021}}, } @inproceedings{24727, author = {{Amer Desouki, Abdelmoneim and Conrads, Felix and Röder, Michael and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{15th {IEEE} International Conference on Semantic Computing, {ICSC} 2021, Laguna Hills, CA, USA, January 27-29, 2021}}, pages = {{76--79}}, publisher = {{{IEEE}}}, title = {{{SYNTHG: Mimicking RDF Graphs Using Tensor Factorization}}}, doi = {{10.1109/ICSC50631.2021.00017}}, year = {{2021}}, } @inproceedings{24728, author = {{Demir, Caglar and Moussallem, Diego and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{15th {IEEE} International Conference on Semantic Computing, {ICSC} 2021, Laguna Hills, CA, USA, January 27-29, 2021}}, pages = {{179--182}}, publisher = {{{IEEE}}}, title = {{{A shallow neural model for relation prediction}}}, doi = {{10.1109/ICSC50631.2021.00038}}, year = {{2021}}, } @inproceedings{24729, author = {{G. Athreya, Ram and Kona Bansal, Srividya and Ngonga Ngomo, Axel-Cyrille and Usbeck, Ricardo}}, booktitle = {{15th {IEEE} International Conference on Semantic Computing, {ICSC} 2021, Laguna Hills, CA, USA, January 27-29, 2021}}, pages = {{195--198}}, publisher = {{{IEEE}}}, title = {{{Template-based Question Answering using Recursive Neural Networks}}}, doi = {{10.1109/ICSC50631.2021.00041}}, year = {{2021}}, } @inproceedings{24730, author = {{Jalota, Rricha and Vollmers, Daniel and Moussallem, Diego and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{15th {IEEE} International Conference on Semantic Computing, {ICSC} 2021, Laguna Hills, CA, USA, January 27-29, 2021}}, pages = {{221--226}}, publisher = {{{IEEE}}}, title = {{{LAUREN - Knowledge Graph Summarization for Question Answering}}}, doi = {{10.1109/ICSC50631.2021.00047}}, year = {{2021}}, } @inproceedings{24731, author = {{Wilke, Adrian and Bannoura, Arwa and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{15th {IEEE} International Conference on Semantic Computing, {ICSC} 2021, Laguna Hills, CA, USA, January 27-29, 2021}}, pages = {{241--247}}, publisher = {{{IEEE}}}, title = {{{Relicensing Combined Datasets}}}, doi = {{10.1109/ICSC50631.2021.00050}}, year = {{2021}}, } @inproceedings{24732, author = {{Röder, Michael and de Souza, Geraldo and Kuchelev, Denis and Amer Desouki, Abdelmoneim and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{15th {IEEE} International Conference on Semantic Computing, {ICSC} 2021, Laguna Hills, CA, USA, January 27-29, 2021}}, pages = {{272--279}}, publisher = {{{IEEE}}}, title = {{{ORCA - a Benchmark for Data Web Crawlers}}}, doi = {{10.1109/ICSC50631.2021.00054}}, year = {{2021}}, } @phdthesis{24887, author = {{Hinnenthal, Kristian}}, title = {{{Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter}}}, doi = {{10.17619/UNIPB/1-1169 }}, year = {{2021}}, } @misc{25126, abstract = {{Motivated by the prospect of computing agents that explore unknown environments and construct convex hulls on the nanoscale, we investigate the capabilities and limitations of a single deterministic finite automaton robot in the three-dimensional hybrid model for programmable matter. In this model, active robots move on a set of passive tiles, called configuration, with the geometric shape of rhombic dodecahedra on the adjacency graph of the face-centered cubic sphere-packing. We show that the exploration problem is equally hard in the hybrid model and in three-dimensional mazes, in which tiles have the shape of cubes and are positioned at the vertices of $\mathbb{Z}^3$. Thereby, a single robot with a constant number of pebbles cannot solve this problem in the hybrid model on arbitrary configurations. We provide algorithms for a robot with two pebbles that solve the exploration problem in the subclass of compact configurations of size $n$ in $\O(n^3)$ rounds. Further, we investigate the robot's capabilities of detection and hull construction in terms of restricted orientation convexity. We show that a robot without any pebble can detect strong $\O$-convexity in $\O(n)$ rounds, but cannot detect weak $\O$-convexity, not even if provided with a single pebble. Assuming that a robot can construct tiles from scratch and deconstruct previously constructed tiles, we show that the strong $\O$-hull of any given configuration of size $n$ can be constructed in $\O(n^4)$ rounds, even if the robot cannot distinguish constructed from native tiles.}}, author = {{Liedtke, David Jan}}, keywords = {{Robot Exploration, Finite Automaton, Hybrid Model for Programmable Matter, Convex Hull}}, title = {{{Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model}}}, year = {{2021}}, } @inproceedings{25203, author = {{Alexandra Morim da Silva, Ana and Röder, Michael and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{The Semantic Web - {ISWC} 2021 - 20th International Semantic Web Conference, {ISWC} 2021, Virtual Event, October 24-28, 2021, Proceedings}}, editor = {{Hotho, Andreas and Blomqvist, Eva and Dietze, Stefan and Fokoue, Achille and Ding, Ying and M. Barnaghi, Payam and Haller, Armin and Dragoni, Mauro and Alani, Harith}}, pages = {{270--286}}, publisher = {{Springer}}, title = {{{Using Compositional Embeddings for Fact Checking}}}, doi = {{10.1007/978-3-030-88361-4\_16}}, volume = {{12922}}, year = {{2021}}, } @inproceedings{25206, author = {{Demir, Caglar and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{The Semantic Web - 18th International Conference, {ESWC} 2021, Virtual Event, June 6-10, 2021, Proceedings}}, editor = {{Verborgh, Ruben and Hose, Katja and Paulheim, Heiko and Champin, Pierre{-}Antoine and Maleshkova, Maria and Corcho, Oscar and Ristoski, Petar and Alam, Mehwish}}, pages = {{409--424}}, publisher = {{Springer}}, title = {{{Convolutional Complex Knowledge Graph Embeddings}}}, doi = {{10.1007/978-3-030-77385-4\_24}}, volume = {{12731}}, year = {{2021}}, } @inproceedings{25208, author = {{Speck, Ren{\'{e}} and Moussallem, Diego and Ngonga Ngomo, Axel-Cyrille}}, booktitle = {{15th {IEEE} International Conference on Semantic Computing, {ICSC} 2021, Laguna Hills, CA, USA, January 27-29, 2021}}, pages = {{298--305}}, publisher = {{{IEEE}}}, title = {{{Twitter Network Mimicking for Data Storage Benchmarking}}}, doi = {{10.1109/ICSC50631.2021.00057}}, year = {{2021}}, } @article{25209, author = {{Demir, Caglar and Moussallem, Diego and Ngonga Ngomo, Axel-Cyrille}}, journal = {{CoRR}}, title = {{{A shallow neural model for relation prediction}}}, volume = {{abs/2101.09090}}, year = {{2021}}, }