5 Search Results for "Yang, Yi"


Document
A Distribution Testing Oracle Separating QMA and QCMA

Authors: Anand Natarajan and Chinmay Nirkhe

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)


Abstract
It is a long-standing open question in quantum complexity theory whether the definition of non-deterministic quantum computation requires quantum witnesses (QMA) or if classical witnesses suffice (QCMA). We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes. Previous separations [Aaronson and Kuperberg, 2007; Bill Fefferman and Shelby Kimmel, 2018] required a quantum unitary oracle. The separating problem is deciding whether a distribution supported on regular un-directed graphs either consists of multiple connected components (yes instances) or consists of one expanding connected component (no instances) where the graph is given in an adjacency-list format by the oracle. Therefore, the oracle is a distribution over n-bit boolean functions.

Cite as

Anand Natarajan and Chinmay Nirkhe. A Distribution Testing Oracle Separating QMA and QCMA. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 22:1-22:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{natarajan_et_al:LIPIcs.CCC.2023.22,
  author =	{Natarajan, Anand and Nirkhe, Chinmay},
  title =	{{A Distribution Testing Oracle Separating QMA and QCMA}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{22:1--22:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.22},
  URN =		{urn:nbn:de:0030-drops-182928},
  doi =		{10.4230/LIPIcs.CCC.2023.22},
  annote =	{Keywords: quantum non-determinism, complexity theory}
}
Document
Computational Methods for Melody and Voice Processing in Music Recordings (Dagstuhl Seminar 19052)

Authors: Meinard Müller, Emilia Gómez, and Yi-Hsun Yang

Published in: Dagstuhl Reports, Volume 9, Issue 1 (2019)


Abstract
In our daily lives, we are constantly surrounded by music, and we are deeply influenced by music. Making music together can create strong ties between people, while fostering communication and creativity. This is demonstrated, for example, by the large community of singers active in choirs or by the fact that music constitutes an important part of our cultural heritage. The availability of music in digital formats and its distribution over the world wide web has changed the way we consume, create, enjoy, explore, and interact with music. To cope with the increasing amount of digital music, one requires computational methods and tools that allow users to find, organize, analyze, and interact with music--topics that are central to the research field known as \emph{Music Information Retrieval} (MIR). The Dagstuhl Seminar 19052 was devoted to a branch of MIR that is of particular importance: processing melodic voices (with a focus on singing voices) using computational methods. It is often the melody, a specific succession of musical tones, which constitutes the leading element in a piece of music. In the seminar we discussed how to detect, extract, and analyze melodic voices as they occur in recorded performances of a piece of music. Gathering researchers from different fields, we critically reviewed the state of the art of computational approaches to various MIR tasks related to melody processing including pitch estimation, source separation, singing voice analysis and synthesis, and performance analysis (timbre, intonation, expression). This triggered interdisciplinary discussions that leveraged insights from fields as disparate as audio processing, machine learning, music perception, music theory, and information retrieval. In particular, we discussed current challenges in academic and industrial research in view of the recent advances in deep learning and data-driven models. Furthermore, we explored novel applications of these technologies in music and multimedia retrieval, content creation, musicology, education, and human-computer interaction. In this report, we give an overview of the various contributions and results of the seminar. We start with an executive summary, which describes the main topics, goals, and group activities. Then, we present a more detailed overview of the participants' contributions (listed alphabetically by their last names) as well as of the ideas, results, and activities of the group meetings, the demo, and the music sessions.

Cite as

Meinard Müller, Emilia Gómez, and Yi-Hsun Yang. Computational Methods for Melody and Voice Processing in Music Recordings (Dagstuhl Seminar 19052). In Dagstuhl Reports, Volume 9, Issue 1, pp. 125-177, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Article{muller_et_al:DagRep.9.1.125,
  author =	{M\"{u}ller, Meinard and G\'{o}mez, Emilia and Yang, Yi-Hsun},
  title =	{{Computational Methods for Melody and Voice Processing in Music Recordings (Dagstuhl Seminar 19052)}},
  pages =	{125--177},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{1},
  editor =	{M\"{u}ller, Meinard and G\'{o}mez, Emilia and Yang, Yi-Hsun},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.1.125},
  URN =		{urn:nbn:de:0030-drops-105732},
  doi =		{10.4230/DagRep.9.1.125},
  annote =	{Keywords: Acoustics of singing, audio signal processing, machine learning, music composition and performance, music information retrieval, music perception and cognition, music processing, singing voice processing, sound source separation, user interaction and interfaces}
}
Document
On The I/O Complexity of Dynamic Distinct Counting

Authors: Xiaocheng Hu, Yufei Tao, Yi Yang, Shengyu Zhang, and Shuigeng Zhou

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)


Abstract
In dynamic distinct counting, we want to maintain a multi-set S of integers under insertions to answer efficiently the query: how many distinct elements are there in S? In external memory, the problem admits two standard solutions. The first one maintains $S$ in a hash structure, so that the distinct count can be incrementally updated after each insertion using O(1) expected I/Os. A query is answered for free. The second one stores S in a linked list, and thus supports an insertion in O(1/B) amortized I/Os. A query can be answered in O(N/B log_{M/B} (N/B)) I/Os by sorting, where N=|S|, B is the block size, and M is the memory size. In this paper, we show that the above two naive solutions are already optimal within a polylog factor. Specifically, for any Las Vegas structure using N^{O(1)} blocks, if its expected amortized insertion cost is o(1/log B}), then it must incur Omega(N/(B log B)) expected I/Os answering a query in the worst case, under the (realistic) condition that N is a polynomial of B. This means that the problem is repugnant to update buffering: the query cost jumps from 0 dramatically to almost linearity as soon as the insertion cost drops slightly below Omega(1).

Cite as

Xiaocheng Hu, Yufei Tao, Yi Yang, Shengyu Zhang, and Shuigeng Zhou. On The I/O Complexity of Dynamic Distinct Counting. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 265-276, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.ICDT.2015.265,
  author =	{Hu, Xiaocheng and Tao, Yufei and Yang, Yi and Zhang, Shengyu and Zhou, Shuigeng},
  title =	{{On The I/O Complexity of Dynamic Distinct Counting}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{265--276},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.265},
  URN =		{urn:nbn:de:0030-drops-49895},
  doi =		{10.4230/LIPIcs.ICDT.2015.265},
  annote =	{Keywords: distinct counting, lower bound, external memory}
}
Document
Improving Safety-Critical Systems by Visual Analysis

Authors: Yi Yang, Patric Keller, Yarden Livnat, and Peter Liggesmeyer

Published in: OASIcs, Volume 27, Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011


Abstract
The importance analysis provides a means of analyzing the contribution of potential low-level system failures to identify and assess vulnerabilities of safety-critical systems. Common approaches attempt to enhance the system safety by addressing vulnerabilities using an iterative analysis process, while considering relevant constraints, e.g., cost, for optimizing the improvements. Typically, data regarding the analysis process is presented across several views with few interactive associations among them. Consequently, this hampers the identification of meaningful information supporting the decision making process. In this paper, we propose a visualization system that visually supports engineers in identifying proper solutions. The visualization integrates a decision tree with a plot representing the cause-effect relationship between the improvement ideas of vulnerabilities and the resulting risk reduction of system. Associating a component fault tree view with the plot allows to maintain helpful context information. The introduced visualization approach enables system and safety engineers to identify and analyze optimal solutions facilitating the improvement of the overall system safety.

Cite as

Yi Yang, Patric Keller, Yarden Livnat, and Peter Liggesmeyer. Improving Safety-Critical Systems by Visual Analysis. In Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011. Open Access Series in Informatics (OASIcs), Volume 27, pp. 43-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{yang_et_al:OASIcs.VLUDS.2011.43,
  author =	{Yang, Yi and Keller, Patric and Livnat, Yarden and Liggesmeyer, Peter},
  title =	{{Improving Safety-Critical Systems by Visual Analysis}},
  booktitle =	{Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011},
  pages =	{43--58},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-46-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{27},
  editor =	{Garth, Christoph and Middel, Ariane and Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.VLUDS.2011.43},
  URN =		{urn:nbn:de:0030-drops-37406},
  doi =		{10.4230/OASIcs.VLUDS.2011.43},
  annote =	{Keywords: fault tree analysis, importance and sensitivity analysis, information vi- sualization, decision tree, safety analysis}
}
Document
ViSSaAn: Visual Support for Safety Analysis

Authors: Yi Yang, Dirk Zeckzer, Peter Liggesmeyer, and Hans Hagen

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


Abstract
Safety of technical systems are becoming more and more important nowadays. Fault trees and minimal cut sets are usually used to attack the problems of assessing safety-critical systems. A visualization system named ViSSaAn, consisting of a matrix view, is proposed that supports an efficient safety analysis based on the information from these techniques. Interactions such as zooming and grouping are provided to support the task of finding the safety problems from the analysis information. An example based on real data shows the usefulness of ViSSaAn.

Cite as

Yi Yang, Dirk Zeckzer, Peter Liggesmeyer, and Hans Hagen. ViSSaAn: Visual Support for Safety Analysis. In Scientific Visualization: Interactions, Features, Metaphors. Dagstuhl Follow-Ups, Volume 2, pp. 378-395, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InCollection{yang_et_al:DFU.Vol2.SciViz.2011.378,
  author =	{Yang, Yi and Zeckzer, Dirk and Liggesmeyer, Peter and Hagen, Hans},
  title =	{{ViSSaAn: Visual Support for Safety Analysis}},
  booktitle =	{Scientific Visualization: Interactions, Features, Metaphors},
  pages =	{378--395},
  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-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol2.SciViz.2011.378},
  URN =		{urn:nbn:de:0030-drops-33073},
  doi =		{10.4230/DFU.Vol2.SciViz.2011.378},
  annote =	{Keywords: Safety Analysis, Fault Tree Analysis, Minimal Cut Sets, Safety Visualization, Information Visualization}
}
  • Refine by Author
  • 3 Yang, Yi
  • 2 Liggesmeyer, Peter
  • 1 Gómez, Emilia
  • 1 Hagen, Hans
  • 1 Hu, Xiaocheng
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Quantum computation theory

  • Refine by Keyword
  • 1 Acoustics of singing
  • 1 Fault Tree Analysis
  • 1 Information Visualization
  • 1 Minimal Cut Sets
  • 1 Safety Analysis
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2011
  • 1 2012
  • 1 2015
  • 1 2019
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail