12 Search Results for "Schultz, Thomas"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.34
Testing Classical Properties from Quantum Data

Authors: Matthias C. Caro, Preksha Naik, and Joseph Slote

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of f instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |f⟩∝ ∑_x|x,f(x)⟩ or the phase state |(-1)^f⟩∝ ∑_x (-1)^{f(x)}|x⟩. Quantum advantage in testing from data. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query-based testers in each case. Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2^{Ω(n)} for any tester relying exclusively on Fourier and classical samples. Classical queries vs. quantum data. Our passive quantum testers are competitive with classical query-based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2^{n/2}) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.
Cite as

Matthias C. Caro, Preksha Naik, and Joseph Slote. Testing Classical Properties from Quantum Data. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 34:1-34:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{caro_et_al:LIPIcs.ITCS.2026.34,
  author =	{Caro, Matthias C. and Naik, Preksha and Slote, Joseph},
  title =	{{Testing Classical Properties from Quantum Data}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{34:1--34:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.34},
  URN =		{urn:nbn:de:0030-drops-253213},
  doi =		{10.4230/LIPIcs.ITCS.2026.34},
  annote =	{Keywords: Quantum Property Testing, Quantum Data, Boolean Functions}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.IPEC.2025.1
A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk)

Authors: Martin Koutecký

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Integer Programming (IP) is a fundamental but computationally hard problem. Still, certain efficiently solvable subclasses have been identified over time, most notably totally unimodular IPs in the 1950s, and fixed-dimension IPs in the 1980s. Starting around the year 2000, a stream of research has identified block-structured IPs as yet another tractable subclass. In this paper, we give a brief and incomplete review of this history, with a focus on several of the author’s contributions.
Cite as

Martin Koutecký. A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk). In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koutecky:LIPIcs.IPEC.2025.1,
  author =	{Kouteck\'{y}, Martin},
  title =	{{A Brief History of Parameterized Algorithms for Block-Structured Integer Programs}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.1},
  URN =		{urn:nbn:de:0030-drops-251338},
  doi =		{10.4230/LIPIcs.IPEC.2025.1},
  annote =	{Keywords: Integer Programming, Parameterized Algorithm, Graver Basis, Treedepth, n-fold, tree-fold, 2-stage stochastic, multistage stochastic, Mixed-Integer Programming}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.27
Assessing the Use of Mixed Reality as a Valid Tool for Human-Robot Interaction Studies in the Context of Space Exploration

Authors: Enrico Guerra, Sebastian Thomas Büttner, Alper Beşer, and Michael Prilla

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)

Abstract
Mixed Reality (MR) is a technology with strong potential for advancing research in Human-Robot Interaction (HRI) for space exploration. Apart from the efficiency and high flexibility MR can offer, we argue that its benefits for HRI research in space contexts lies particularly in its ability to aid human-in-the-loop development, offer realistic hybrid simulations, and foster broader participation in HRI research in the space exploration context. However, we believe that this is only plausible if MR-based simulations can yield comparable results to fully physical approaches in human-centred studies. In this position paper, we highlight several arguments in favour of MR as a tool for space HRI research, while emphasising the importance of the open question regarding its scientific validity. We believe MR could become a central tool for preparing for future human-robotic space exploration missions and significantly diversify research in this domain.
Cite as

Enrico Guerra, Sebastian Thomas Büttner, Alper Beşer, and Michael Prilla. Assessing the Use of Mixed Reality as a Valid Tool for Human-Robot Interaction Studies in the Context of Space Exploration. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 27:1-27:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guerra_et_al:OASIcs.SpaceCHI.2025.27,
  author =	{Guerra, Enrico and B\"{u}ttner, Sebastian Thomas and Be\c{s}er, Alper and Prilla, Michael},
  title =	{{Assessing the Use of Mixed Reality as a Valid Tool for Human-Robot Interaction Studies in the Context of Space Exploration}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{27:1--27:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.27},
  URN =		{urn:nbn:de:0030-drops-240175},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.27},
  annote =	{Keywords: Mixed Reality, Augmented Reality, Human-Robot Interaction, Space Exploration, Validity}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.7
Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii

Authors: Sayan Bandyapadhyay and Eli Mitchell

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We study the Discrete Covering with Two Types of Radii problem motivated by its application in wireless networks. In this problem, the goal is to assign either small-range high frequency or large-range low frequency to each access point, maximizing the number of users in high-frequency regions while ensuring that each user is in the range of an access point. Unlike other weighted covering problems, our problem requires satisfying two simultaneous objectives, which calls for novel approaches that leverage the underlying geometry of the problem. In our work, we present two new algorithms: the first is a polynomial-time (2.5 + ε)-approximation, and the second is an exact algorithm for sparse instances, which is fixed-parameter tractable (FPT) in the number of large-radius disks. We also prove that such an FPT algorithm is impossible for general instances lacking sparsity, assuming the Exponential Time Hypothesis. Before our work, the best-known polynomial-time approximation factor was 4 for the problem. Our approximation algorithm results from a fine-grained classification of points that can contribute to the gain of a solution. Based on this classification, we design two sub-algorithms with interdependent guarantees to recover the respective class of points as gain. Our algorithm exploits further properties of Delaunay triangulations to achieve the improved bound. The FPT algorithm is based on branching that utilizes the sparsity of the instances to limit the overall search space.
Cite as

Sayan Bandyapadhyay and Eli Mitchell. Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.WADS.2025.7,
  author =	{Bandyapadhyay, Sayan and Mitchell, Eli},
  title =	{{Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.7},
  URN =		{urn:nbn:de:0030-drops-242386},
  doi =		{10.4230/LIPIcs.WADS.2025.7},
  annote =	{Keywords: Covering, Disks, Approximation, FPT}
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.10
DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs

Authors: Ali Ghaffaari, Alexander Schönhuth, and Tobias Marschall

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Determining the distance between two loci within a genomic region is a recurrent operation in various tasks in computational genomics. A notable example of this task arises in paired-end read mapping as a form of validation of distances between multiple alignments. While straightforward for a single genome, graph-based reference structures render the operation considerably more involved. Given the sheer number of such queries in a typical read mapping experiment, an efficient algorithm for answering distance queries is crucial. In this paper, we introduce DiVerG, a compact data structure as well as a fast and scalable algorithm, for constructing distance indexes for general sequence graphs on multi-core CPU and many-core GPU architectures. DiVerG is based on PairG [Jain et al., 2019], but overcomes the limitations of PairG by exploiting the extensive potential for improvements in terms of scalability and space efficiency. As a consequence, DiVerG can process substantially larger datasets, such as whole human genomes, which are unmanageable by PairG. DiVerG offers faster index construction time and consistently faster query time with gains proportional to the size of the underlying compact data structure. We demonstrate that our method performs favorably on multiple real datasets at various scales. DiVerG achieves superior performance over PairG; e.g. resulting to 2.5-4x speed-up in query time, 44-340x smaller index size, and 3-50x faster construction time for the genome graph of the MHC region, as a particularly variable region of the human genome. The implementation is available at: https://github.com/cartoonist/diverg
Cite as

Ali Ghaffaari, Alexander Schönhuth, and Tobias Marschall. DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghaffaari_et_al:LIPIcs.WABI.2025.10,
  author =	{Ghaffaari, Ali and Sch\"{o}nhuth, Alexander and Marschall, Tobias},
  title =	{{DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.10},
  URN =		{urn:nbn:de:0030-drops-239369},
  doi =		{10.4230/LIPIcs.WABI.2025.10},
  annote =	{Keywords: Sequence graph, distance index, read mapping, sparse matrix}
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.14
Human Readable Compression of GFA Paths Using Grammar-Based Code

Authors: Peter Heringer and Daniel Doerr

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Pangenome graphs offer a compact and comprehensive representation of genomic diversity, improving tasks such as variant calling, genotyping, and other downstream analyses. Although the underlying graph structures scale sublinearly with the number of haplotypes, the widely used GFA file format suffers from rapidly growing file sizes due to the explicit and repetitive encoding of haplotype paths. In this work, we introduce an extension to the GFA format that enables efficient grammar-based compression of haplotype paths while retaining human readability. In addition, grammar-based encoding provides an efficient in-memory data structure that does not require decompression, but conversely improves the runtime of many computational tasks that involve haplotype comparisons. We present sqz, a method that makes use of the proposed format extension to encode haplotype paths using byte pair encoding, a grammar-based compression scheme. We evaluate sqz on recent human pangenome graphs from Heumos et al. and the Human Pangenome Reference Consortium (HPRC), comparing it to existing compressors bgzip, gbz, and sequitur. sqz scales sublinearly with the number of haplotypes in a pangenome graph and consistently achieves higher compression ratios than sequitur and up to 5 times better compression than bgzip in HPRC graphs and up to 10 times in the graph from Heumos et al.. When combined with bgzip, sqz matches or excels the compression ratio of gbz across all our datasets. These results demonstrate the potential of our proposed extension of the GFA format in reducing haplotype path redundancy and improving storage efficiency for pangenome graphs.
Cite as

Peter Heringer and Daniel Doerr. Human Readable Compression of GFA Paths Using Grammar-Based Code. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{heringer_et_al:LIPIcs.WABI.2025.14,
  author =	{Heringer, Peter and Doerr, Daniel},
  title =	{{Human Readable Compression of GFA Paths Using Grammar-Based Code}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.14},
  URN =		{urn:nbn:de:0030-drops-239395},
  doi =		{10.4230/LIPIcs.WABI.2025.14},
  annote =	{Keywords: pangenomics, pangenome graphs, compression, grammar-based code, byte pair encoding}
}
Document
Survey
DOI: 10.4230/TGDK.2.1.3
Semantic Web: Past, Present, and Future

Authors: Ansgar Scherp, Gerd Groener, Petr Škoda, Katja Hose, and Maria-Esther Vidal

Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1

Abstract
Ever since the vision was formulated, the Semantic Web has inspired many generations of innovations. Semantic technologies have been used to share vast amounts of information on the Web, enhance them with semantics to give them meaning, and enable inference and reasoning on them. Throughout the years, semantic technologies, and in particular knowledge graphs, have been used in search engines, data integration, enterprise settings, and machine learning. In this paper, we recap the classical concepts and foundations of the Semantic Web as well as modern and recent concepts and applications, building upon these foundations. The classical topics we cover include knowledge representation, creating and validating knowledge on the Web, reasoning and linking, and distributed querying. We enhance this classical view of the so-called "Semantic Web Layer Cake" with an update of recent concepts that include provenance, security and trust, as well as a discussion of practical impacts from industry-led contributions. We conclude with an outlook on the future directions of the Semantic Web. This is a living document. If you like to contribute, please contact the first author and visit: https://github.com/ascherp/semantic-web-primer
Cite as

Ansgar Scherp, Gerd Groener, Petr Škoda, Katja Hose, and Maria-Esther Vidal. Semantic Web: Past, Present, and Future. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 3:1-3:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{scherp_et_al:TGDK.2.1.3,
  author =	{Scherp, Ansgar and Groener, Gerd and \v{S}koda, Petr and Hose, Katja and Vidal, Maria-Esther},
  title =	{{Semantic Web: Past, Present, and Future}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:37},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.3},
  URN =		{urn:nbn:de:0030-drops-198607},
  doi =		{10.4230/TGDK.2.1.3},
  annote =	{Keywords: Linked Open Data, Semantic Web Graphs, Knowledge Graphs}
}
Document
DOI: 10.4230/DagRep.8.10.148
Visualization and Processing of Anisotropy in Imaging, Geometry, and Astronomy (Dagstuhl Seminar 18442)

Authors: Andrea Fuster, Evren Özarslan, Thomas Schultz, and Eugene Zhang

Published in: Dagstuhl Reports, Volume 8, Issue 10 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18442, "Visualization and Processing of Anisotropy in Imaging, Geometry, and Astronomy", which was attended by 30 international researchers, both junior and senior. Directional preferences or anisotropies are encountered across many different disciplines and spatial scales. These disciplines share a need for modeling, processing, and visualizing anisotropic quantities, which poses interesting challenges to applied computer science. With the goal of identifying open problems, making practitioners aware of existing solutions, and discovering synergies between different applications in which anisotropy arises, this seminar brought together researchers working on different aspects of computer science with experts from neuroimaging and astronomy. This report gathers abstracts of the talks held by the participants, as well as an account of topics raised within the breakout sessions.
Cite as

Andrea Fuster, Evren Özarslan, Thomas Schultz, and Eugene Zhang. Visualization and Processing of Anisotropy in Imaging, Geometry, and Astronomy (Dagstuhl Seminar 18442). In Dagstuhl Reports, Volume 8, Issue 10, pp. 148-172, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{fuster_et_al:DagRep.8.10.148,
  author =	{Fuster, Andrea and \"{O}zarslan, Evren and Schultz, Thomas and Zhang, Eugene},
  title =	{{Visualization and Processing of Anisotropy in Imaging, Geometry, and Astronomy (Dagstuhl Seminar 18442)}},
  pages =	{148--172},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{10},
  editor =	{Fuster, Andrea and \"{O}zarslan, Evren and Schultz, Thomas and Zhang, Eugene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.10.148},
  URN =		{urn:nbn:de:0030-drops-103524},
  doi =		{10.4230/DagRep.8.10.148},
  annote =	{Keywords: Anisotropy, astronomy, diffusion-weighted imaging (DWI), geometry processing, tensor fields, topology, visualization, uncertainty, shape modeling, microstructure imaging, statistical analysis}
}
Document
DOI: 10.4230/DagRep.6.4.16
Multidisciplinary Approaches to Multivalued Data: Modeling, Visualization, Analysis (Dagstuhl Seminar 16142)

Authors: Ingrid Hotz, Evren Özarslan, and Thomas Schultz

Published in: Dagstuhl Reports, Volume 6, Issue 4 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16142, "Multidisciplinary Approaches to Multivalued Data: Modelling, Visualization, Analysis", which was attended by 27 international researchers, both junior and senior. Modelling multivalued data using tensors and higher-order descriptors has become common practice in neuroscience, engineering, and medicine. Novel tools for image analysis, visualization, as well as statistical hypothesis testing and machine learning are required to extract value from such data, and can only be developed within multidisciplinary collaborations. This report gathers abstracts of the talks held by participants on recent advances and open questions related to these challenges, as well as an account of topics raised within two of the breakout sessions.
Cite as

Ingrid Hotz, Evren Özarslan, and Thomas Schultz. Multidisciplinary Approaches to Multivalued Data: Modeling, Visualization, Analysis (Dagstuhl Seminar 16142). In Dagstuhl Reports, Volume 6, Issue 4, pp. 16-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{hotz_et_al:DagRep.6.4.16,
  author =	{Hotz, Ingrid and \"{O}zarslan, Evren and Schultz, Thomas},
  title =	{{Multidisciplinary Approaches to Multivalued Data: Modeling, Visualization, Analysis (Dagstuhl Seminar 16142)}},
  pages =	{16--38},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{4},
  editor =	{Hotz, Ingrid and \"{O}zarslan, Evren and Schultz, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.4.16},
  URN =		{urn:nbn:de:0030-drops-61517},
  doi =		{10.4230/DagRep.6.4.16},
  annote =	{Keywords: visualization, image processing, statistical analysis, machine learning, tensor fields, higher-order descriptors, diffusion-weighted imaging (DWI), structural mechanics, fluid dynamics, microstructure imaging, connectomics, uncertainty visualization, feature extraction}
}
Document
DOI: 10.4230/OASIcs.GCB.2013.80
Dinucleotide distance histograms for fast detection of rRNA in metatranscriptomic sequences

Authors: Heiner Klingenberg, Robin Martinjak, Frank Oliver Glöckner, Rolf Daniel, Thomas Lingner, and Peter Meinicke

Published in: OASIcs, Volume 34, German Conference on Bioinformatics 2013

Abstract
With the advent of metatranscriptomics it has now become possible to study the dynamics of microbial communities. The analysis of environmental RNA-Seq data implies several challenges for the development of efficient tools in bioinformatics. One of the first steps in the computational analysis of metatranscriptomic sequencing reads requires the separation of rRNA and mRNA fragments to ensure that only protein coding sequences are actually used in a subsequent functional analysis. In the context of the rRNA filtering task it is desirable to have a broad spectrum of different methods in order to find a suitable trade-off between speed and accuracy for a particular dataset. We introduce a machine learning approach for the detection of rRNA in metatranscriptomic sequencing reads that is based on support vector machines in combination with dinucleotide distance histograms for feature representation. The results show that our SVM-based approach is at least one order of magnitude faster than any of the existing tools with only a slight degradation of the detection performance when compared to state-of-the-art alignment-based methods.
Cite as

Heiner Klingenberg, Robin Martinjak, Frank Oliver Glöckner, Rolf Daniel, Thomas Lingner, and Peter Meinicke. Dinucleotide distance histograms for fast detection of rRNA in metatranscriptomic sequences. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 80-89, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{klingenberg_et_al:OASIcs.GCB.2013.80,
  author =	{Klingenberg, Heiner and Martinjak, Robin and Gl\"{o}ckner, Frank Oliver and Daniel, Rolf and Lingner, Thomas and Meinicke, Peter},
  title =	{{Dinucleotide distance histograms for fast detection of rRNA in metatranscriptomic sequences}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{80--89},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-59-0},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{34},
  editor =	{Bei{\ss}barth, Tim and Kollmar, Martin and Leha, Andreas and Morgenstern, Burkhard and Schultz, Anne-Kathrin and Waack, Stephan and Wingender, Edgar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.80},
  URN =		{urn:nbn:de:0030-drops-42324},
  doi =		{10.4230/OASIcs.GCB.2013.80},
  annote =	{Keywords: Metatranscriptomics, metagenomics, rRNA detection, distance histograms}
}
Document
DOI: 10.4230/DFU.Vol2.SciViz.2011.322
Feature Extraction for DW-MRI Visualization: The State of the Art and Beyond

Authors: Thomas Schultz

Published in: Dagstuhl Follow-Ups, Volume 2, Scientific Visualization: Interactions, Features, Metaphors (2011)

Abstract
By measuring the anisotropic self-diffusion rates of water, Diffusion Weighted Magnetic Resonance Imaging (DW-MRI) provides a unique noninvasive probe of fibrous tissue. In particular, it has been explored widely for imaging nerve fiber tracts in the human brain. Geometric features provide a quick visual overview of the complex datasets that arise from DW-MRI. At the same time, they build a bridge towards quantitative analysis, by extracting explicit representations of structures in the data that are relevant to specific research questions. Therefore, features in DWMRI data are an active research topic not only within scientific visualization, but have received considerable interest from the medical image analysis, neuroimaging, and computer vision communities. It is the goal of this paper to survey contributions from all these fields, concentrating on streamline clustering, edge detection and segmentation, topological methods, and extraction of anisotropy creases. We point out interrelations between these topics and make suggestions for future research.
Cite as

Thomas Schultz. Feature Extraction for DW-MRI Visualization: The State of the Art and Beyond. In Scientific Visualization: Interactions, Features, Metaphors. Dagstuhl Follow-Ups, Volume 2, pp. 322-345, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InCollection{schultz:DFU.Vol2.SciViz.2011.322,
  author =	{Schultz, Thomas},
  title =	{{Feature Extraction for DW-MRI Visualization: The State of the Art and Beyond}},
  booktitle =	{Scientific Visualization: Interactions, Features, Metaphors},
  pages =	{322--345},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-26-2},
  ISSN =	{1868-8977},
  year =	{2011},
  volume =	{2},
  editor =	{Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol2.SciViz.2011.322},
  URN =		{urn:nbn:de:0030-drops-33010},
  doi =		{10.4230/DFU.Vol2.SciViz.2011.322},
  annote =	{Keywords: Diffusion-Weighted MRI, dMRI, DT-MRI, DTI, HARDI, Streamline Clustering, Edge Detection, DW-MRI Segmentation, Tensor Topology, Crease Surfaces}
}
Document
DOI: 10.4230/DagSemProc.05031.17
Network Discovery and Verification

Authors: Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak, and L. Shankar Ram

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
Consider the problem of discovering (or verifying) the edges and non-edges of a network, modelled as a connected undirected graph, using a minimum number of queries. A query at a vertex v discovers (or verifies) all edges and non-edges whose endpoints have different distance from v. In the network discovery problem, the edges and non-edges are initially unknown, and the algorithm must select the next query based only on the results of previous queries. We study the problem using competitive analysis and give a randomized on-line algorithm with competitive ratio O(sqrt(n*log n)) for graphs with n vertices. We also show that no deterministic algorithm can have competitive ratio better than 3. In the network verification problem, the graph is known in advance and the goal is to compute a minimum number of queries that verify all edges and non-edges. This problem has previously been studied as the problem of placing landmarks in graphs or determining the metric dimension of a graph. We show that there is no approximation algorithm for this problem with ratio o(log n) unless P=NP. Furthermore, we prove that the optimal number of queries for d-dimensional hypercubes is Theta(d/log d).
Cite as

Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak, and L. Shankar Ram. Network Discovery and Verification. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{beerliova_et_al:DagSemProc.05031.17,
  author =	{Beerliova, Zuzana and Eberhard, Felix and Erlebach, Thomas and Hall, Alexander and Hoffmann, Michael and Mihalak, Matus and Ram, L. Shankar},
  title =	{{Network Discovery and Verification}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.17},
  URN =		{urn:nbn:de:0030-drops-594},
  doi =		{10.4230/DagSemProc.05031.17},
  annote =	{Keywords: on-line algorithms , set cover , landmarks , metric dimension}
}
  • Refine by Type
  • 12 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2024
  • 1 2019
  • 1 2016
  • Show More...

  • Refine by Author
  • 3 Schultz, Thomas
  • 2 Özarslan, Evren
  • 1 Bandyapadhyay, Sayan
  • 1 Beerliova, Zuzana
  • 1 Beşer, Alper
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 2 OASIcs
  • 1 TGDK
  • 2 DagRep
  • 1 DFU
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Bioinformatics
  • 1 Applied computing → Computational genomics
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Computing methodologies → Ontology engineering
  • 1 Human-centered computing → Mixed / augmented reality
  • Show More...

  • Refine by Keyword
  • 2 diffusion-weighted imaging (DWI)
  • 2 microstructure imaging
  • 2 statistical analysis
  • 2 tensor fields
  • 2 visualization
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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