13 Search Results for "Yu, Hung-I"

Document
Short Paper
DOI: 10.4230/OASIcs.SLATE.2023.7
Automatic Speech Recognition of Non-Native Child Speech for Language Learning Applications (Short Paper)

Authors: Simone Wills, Yu Bai, Cristian Tejedor-García, Catia Cucchiarini, and Helmer Strik

Published in: OASIcs, Volume 113, 12th Symposium on Languages, Applications and Technologies (SLATE 2023)

Abstract
Voicebots have provided a new avenue for supporting the development of language skills, particularly within the context of second language learning. Voicebots, though, have largely been geared towards native adult speakers. We sought to assess the performance of two state-of-the-art ASR systems, Wav2Vec2.0 and Whisper AI, with a view to developing a voicebot that can support children acquiring a foreign language. We evaluated their performance on read and extemporaneous speech of native and non-native Dutch children. We also investigated the utility of using ASR technology to provide insight into the children’s pronunciation and fluency. The results show that recent, pre-trained ASR transformer-based models achieve acceptable performance from which detailed feedback on phoneme pronunciation quality can be extracted, despite the challenging nature of child and non-native speech.
Cite as

Simone Wills, Yu Bai, Cristian Tejedor-García, Catia Cucchiarini, and Helmer Strik. Automatic Speech Recognition of Non-Native Child Speech for Language Learning Applications (Short Paper). In 12th Symposium on Languages, Applications and Technologies (SLATE 2023). Open Access Series in Informatics (OASIcs), Volume 113, pp. 7:1-7:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wills_et_al:OASIcs.SLATE.2023.7,
  author =	{Wills, Simone and Bai, Yu and Tejedor-Garc{\'\i}a, Cristian and Cucchiarini, Catia and Strik, Helmer},
  title =	{{Automatic Speech Recognition of Non-Native Child Speech for Language Learning Applications}},
  booktitle =	{12th Symposium on Languages, Applications and Technologies (SLATE 2023)},
  pages =	{7:1--7:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-291-4},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{113},
  editor =	{Sim\~{o}es, Alberto and Ber\'{o}n, Mario Marcelo and Portela, Filipe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2023.7},
  URN =		{urn:nbn:de:0030-drops-185218},
  doi =		{10.4230/OASIcs.SLATE.2023.7},
  annote =	{Keywords: Automatic Speech Recognition, ASR, Child Speech, Non-Native Speech, Human-computer Interaction, Whisper, Wav2Vec2.0}
}
Document
DOI: 10.4230/DagRep.12.4.1
Symmetric Cryptography (Dagstuhl Seminar 22141)

Authors: Nils Gregor Leander, Bart Mennink, María Naya-Plasencia, Yu Sasaki, and Eran Lambooij

Published in: Dagstuhl Reports, Volume 12, Issue 4 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 20041 "Symmetric Cryptography". The seminar was held on April 3-8, 2022 in Schloss Dagstuhl - Leibniz Center for Informatics. This was the eigth seminar in the series "Symmetric Cryptography". Previous editions were held in 2007, 2009, 2012, 2014, 2016, 2018, and 2022. Participants of the seminar presented their ongoing work and new results on topics of (quantum) cryptanalysis and provable security of symmetric cryptographic primitives. In this report, a brief summary of the seminar is given followed by the abstracts of given talks.
Cite as

Nils Gregor Leander, Bart Mennink, María Naya-Plasencia, Yu Sasaki, and Eran Lambooij. Symmetric Cryptography (Dagstuhl Seminar 22141). In Dagstuhl Reports, Volume 12, Issue 4, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{leander_et_al:DagRep.12.4.1,
  author =	{Leander, Nils Gregor and Mennink, Bart and Naya-Plasencia, Mar{\'\i}a and Sasaki, Yu and Lambooij, Eran},
  title =	{{Symmetric Cryptography (Dagstuhl Seminar 22141)}},
  pages =	{1--12},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{4},
  editor =	{Leander, Nils Gregor and Mennink, Bart and Naya-Plasencia, Mar{\'\i}a and Sasaki, Yu and Lambooij, Eran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.4.1},
  URN =		{urn:nbn:de:0030-drops-172779},
  doi =		{10.4230/DagRep.12.4.1},
  annote =	{Keywords: block ciphers, cryptography, hash functions, stream cipers, symmetric cryptography}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.WABI.2022.1
Efficient Solutions to Biological Problems Using de Bruijn Graphs (Invited Talk)

Authors: Leena Salmela

Published in: LIPIcs, Volume 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)

Abstract
The de Bruijn graph has become a standard method in the analysis of sequencing reads in computational biology due to its ability to represent the information contained in large read sets in small space. A de Bruijn graph represents a set of sequencing reads by its k-mers, i.e. the set of substrings of length k that occur in the reads. In the classical definition, the k-mers are the edges of the graph and the nodes are the k-1 bases long prefixes and suffixes of the k-mers. Usually only k-mers occurring several times in the read set are kept to filter out noise in the data. De Bruijn graphs have been used to solve many problems in computational biology including genome assembly [Ramana M. Idury and Michael S. Waterman, 1995; Pavel A. Pevzner et al., 2001; Anton Bankevich et al., 2012; Yu Peng et al., 2010], sequencing error correction [Leena Salmela and Eric Rivals, 2014; Giles Miclotte et al., 2016; Leena Salmela et al., 2017; Limasset et al., 2019], reference free variant calling [Raluca Uricaru et al., 2015], indexing read sets [Camille Marchet et al., 2021], and so on. Next I will discuss two of these problems in more depth. The de Bruijn graph first emerged in computation biology in the context of genome assembly [Ramana M. Idury and Michael S. Waterman, 1995; Pavel A. Pevzner et al., 2001] where the task is to reconstruct a genome based on sequencing reads. As the de Bruijn graph can represent large read sets compactly, it became the standard approach to assemble short reads [Anton Bankevich et al., 2012; Yu Peng et al., 2010]. In the theoretical framework of de Bruijn graph based genome assembly, a genome is thought to be the Eulerian path in the de Bruijn graph built on the sequencing reads. In practise, the Eulerian path is not unique and thus not useful in the biological context. Therefore, practical implementations report subpaths that are guaranteed to be part of any Eulerian path and thus part of the actual genome. Such models include unitigs, which are nonbranching paths of the de Bruijn graph, and more involved definitions such as omnitigs [Alexandru I. Tomescu and Paul Medvedev, 2017]. In genome assembly the choice of k is a crucial matter. A small k can result in a tangled graph, whereas a too large k will fragment the graph. Furthermore, a different value of k may be optimal for different parts of the genome. Variable order de Bruijn graphs [Christina Boucher et al., 2015; Djamal Belazzougui et al., 2016], which represent de Bruijn graphs of all orders k in a single data structure, have been proposed as a solution but no rigorous definition corresponding to unitigs has been presented. We give the first definition of assembled sequences, i.e. contigs, on such graphs and an algorithm for enumerating them. Another problem that can be solved with de Bruijn graphs is the correction of sequencing errors [Leena Salmela and Eric Rivals, 2014; Giles Miclotte et al., 2016; Leena Salmela et al., 2017; Limasset et al., 2019]. Because each position of a genome is sequenced several times, it is possible to correct sequencing errors in reads if we can identify data originating from the same genomic region. A de Bruijn graph can be used to represent compactly the reliable information and the individual reads can be corrected by aligning them to the graph.
Cite as

Leena Salmela. Efficient Solutions to Biological Problems Using de Bruijn Graphs (Invited Talk). In 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 242, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{salmela:LIPIcs.WABI.2022.1,
  author =	{Salmela, Leena},
  title =	{{Efficient Solutions to Biological Problems Using de Bruijn Graphs}},
  booktitle =	{22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)},
  pages =	{1:1--1:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-243-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{242},
  editor =	{Boucher, Christina and Rahmann, Sven},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.1},
  URN =		{urn:nbn:de:0030-drops-170357},
  doi =		{10.4230/LIPIcs.WABI.2022.1},
  annote =	{Keywords: de Bruijn graph, variable order de Bruijn graph, genome assembly, sequencing error correction, k-mers}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.11
Sample Efficient Identity Testing and Independence Testing of Quantum States

Authors: Nengkun Yu

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
In this paper, we study the quantum identity testing problem, i.e., testing whether two given quantum states are identical, and quantum independence testing problem, i.e., testing whether a given multipartite quantum state is in tensor product form. For the quantum identity testing problem of 𝒟(ℂ^d) system, we provide a deterministic measurement scheme that uses 𝒪(d²/ε²) copies via independent measurements with d being the dimension of the state and ε being the additive error. For the independence testing problem 𝒟(ℂ^d₁⊗ℂ^{d₂}⊗⋯⊗ℂ^{d_m}) system, we show that the sample complexity is Θ̃((Π_{i = 1}^m d_i)/ε²) via collective measurements, and 𝒪((Π_{i = 1}^m d_i²)/ε²) via independent measurements. If randomized choice of independent measurements are allowed, the sample complexity is Θ(d^{3/2}/ε²) for the quantum identity testing problem, and Θ̃((Π_{i = 1}^m d_i^{3/2})/ε²) for the quantum independence testing problem.
Cite as

Nengkun Yu. Sample Efficient Identity Testing and Independence Testing of Quantum States. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{yu:LIPIcs.ITCS.2021.11,
  author =	{Yu, Nengkun},
  title =	{{Sample Efficient Identity Testing and Independence Testing of Quantum States}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.11},
  URN =		{urn:nbn:de:0030-drops-135504},
  doi =		{10.4230/LIPIcs.ITCS.2021.11},
  annote =	{Keywords: Quantum property testing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.31
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness

Authors: Joshua A. Grochow and Youming Qiao

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We study the complexity of isomorphism problems for tensors, groups, and polynomials. These problems have been studied in multivariate cryptography, machine learning, quantum information, and computational group theory. We show that these problems are all polynomial-time equivalent, creating bridges between problems traditionally studied in myriad research areas. This prompts us to define the complexity class TI, namely problems that reduce to the Tensor Isomorphism (TI) problem in polynomial time. Our main technical result is a polynomial-time reduction from d-tensor isomorphism to 3-tensor isomorphism. In the context of quantum information, this result gives multipartite-to-tripartite entanglement transformation procedure, that preserves equivalence under stochastic local operations and classical communication (SLOCC).
Cite as

Joshua A. Grochow and Youming Qiao. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grochow_et_al:LIPIcs.ITCS.2021.31,
  author =	{Grochow, Joshua A. and Qiao, Youming},
  title =	{{On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.31},
  URN =		{urn:nbn:de:0030-drops-135702},
  doi =		{10.4230/LIPIcs.ITCS.2021.31},
  annote =	{Keywords: complexity class, tensor isomorphism, polynomial isomorphism, group isomorphism, stochastic local operations and classical communication}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.8
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces

Authors: Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, and Xiaoming Sun

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
In the 1970’s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017). In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration. (Dedicated to the memory of Ker-I Ko)
Cite as

Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, and Xiaoming Sun. From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 8:1-8:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bei_et_al:LIPIcs.ITCS.2020.8,
  author =	{Bei, Xiaohui and Chen, Shiteng and Guan, Ji and Qiao, Youming and Sun, Xiaoming},
  title =	{{From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{8:1--8:48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.8},
  URN =		{urn:nbn:de:0030-drops-116932},
  doi =		{10.4230/LIPIcs.ITCS.2020.8},
  annote =	{Keywords: independent set, vertex coloring, graphs, matrix spaces, isotropic subspace}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.57
Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges

Authors: Yufei Tao and Yu Wang

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
A family R of ranges and a set X of points, all in R^d, together define a range space (X, R|_X), where R|_X = {X cap h | h in R}. We want to find a structure to estimate the quantity |X cap h|/|X| for any range h in R with the (rho, epsilon)-guarantee: (i) if |X cap h|/|X| > rho, the estimate must have a relative error epsilon; (ii) otherwise, the estimate must have an absolute error rho epsilon. The objective is to minimize the size of the structure. Currently, the dominant solution is to compute a relative (rho, epsilon)-approximation, which is a subset of X with O~(lambda/(rho epsilon^2)) points, where lambda is the VC-dimension of (X, R|_X), and O~ hides polylog factors. This paper shows a more general bound sensitive to the content of X. We give a structure that stores O(log (1/rho)) integers plus O~(theta * (lambda/epsilon^2)) points of X, where theta - called the disagreement coefficient - measures how much the ranges differ from each other in their intersections with X. The value of theta is between 1 and 1/rho, such that our space bound is never worse than that of relative (rho, epsilon)-approximations, but we improve the latter’s 1/rho term whenever theta = o(1/(rho log (1/rho))). We also prove that, in the worst case, summaries with the (rho, 1/2)-guarantee must consume Omega(theta) words even for d = 2 and lambda <=3. We then constrain R to be the set of halfspaces in R^d for a constant d, and prove the existence of structures with o(1/(rho epsilon^2)) size offering (rho,epsilon)-guarantees, when X is generated from various stochastic distributions. This is the first formal justification on why the term 1/rho is not compulsory for "realistic" inputs.
Cite as

Yufei Tao and Yu Wang. Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{tao_et_al:LIPIcs.SoCG.2019.57,
  author =	{Tao, Yufei and Wang, Yu},
  title =	{{Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{57:1--57:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.57},
  URN =		{urn:nbn:de:0030-drops-104617},
  doi =		{10.4230/LIPIcs.SoCG.2019.57},
  annote =	{Keywords: Relative Approximation, Disagreement Coefficient, Data Summary}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.57
Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension

Authors: Gleb Posobin and Alexander Shen

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
Consider a bit string x of length n and Kolmogorov complexity alpha n (for some alpha<1). It is always possible to increase the complexity of x by changing a small fraction of bits in x [Harry Buhrman et al., 2005]. What happens with the complexity of x when we randomly change each bit independently with some probability tau? We prove that a linear increase in complexity happens with high probability, but this increase is smaller than in the case of arbitrary change considered in [Harry Buhrman et al., 2005]. The amount of the increase depends on x (strings of the same complexity could behave differently). We give exact lower and upper bounds for this increase (with o(n) precision). The same technique is used to prove the results about the (effective Hausdorff) dimension of infinite sequences. We show that random change increases the dimension with probability 1, and provide an optimal lower bound for the dimension of the changed sequence. We also improve a result from [Noam Greenberg et al., 2018] and show that for every sequence omega of dimension alpha there exists a strongly alpha-random sequence omega' such that the Besicovitch distance between omega and omega' is 0. The proofs use the combinatorial and probabilistic reformulations of complexity statements and the technique that goes back to Ahlswede, Gács and Körner [Ahlswede et al., 1976].
Cite as

Gleb Posobin and Alexander Shen. Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{posobin_et_al:LIPIcs.STACS.2019.57,
  author =	{Posobin, Gleb and Shen, Alexander},
  title =	{{Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{57:1--57:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.57},
  URN =		{urn:nbn:de:0030-drops-102969},
  doi =		{10.4230/LIPIcs.STACS.2019.57},
  annote =	{Keywords: Kolmogorov complexity, effective Hausdorff dimension, random noise}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.38
An Analytical Framework for Understanding Urban Functionality from Human Activities (Short Paper)

Authors: Chaogui Kang and Yu Liu

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
The intertwined relationship between urban functionality and human activity has been widely recognized and quantified with the assistance of big geospatial data. In specific, urban land uses as an important facet of urban structure can be identified from spatiotemporal patterns of aggregate human activities. In this article, we propose a space, time and activity cuboid based analytical framework for clustering urban spaces into different categories of urban functionality based on the variation of activity intensity (T-fiber), mixture (A-fiber) and interaction (I- and O-fiber). The ability of the proposed framework is empirically evaluated by three case studies.
Cite as

Chaogui Kang and Yu Liu. An Analytical Framework for Understanding Urban Functionality from Human Activities (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 38:1-38:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kang_et_al:LIPIcs.GISCIENCE.2018.38,
  author =	{Kang, Chaogui and Liu, Yu},
  title =	{{An Analytical Framework for Understanding Urban Functionality from Human Activities}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{38:1--38:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.38},
  URN =		{urn:nbn:de:0030-drops-93668},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.38},
  annote =	{Keywords: Urban functionality, Human activity, STA cuboid, Spatiotemporal distribution, Clustering}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.33
Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures

Authors: Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, and Yuancheng Yu

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
Since the introduction of retroactive data structures at SODA 2004, a major unsolved problem has been to bound the gap between the best partially retroactive data structure (where changes can be made to the past, but only the present can be queried) and the best fully retroactive data structure (where the past can also be queried) for any problem. It was proved in 2004 that any partially retroactive data structure with operation time T_{op}(n,m) can be transformed into a fully retroactive data structure with operation time O(sqrt{m} * T_{op}(n,m)), where n is the size of the data structure and m is the number of operations in the timeline [Demaine et al., 2004]. But it has been open for 14 years whether such a gap is necessary. In this paper, we prove nearly matching upper and lower bounds on this gap for all n and m. We improve the upper bound for n << sqrt m by showing a new transformation with multiplicative overhead n log m. We then prove a lower bound of min {n log m, sqrt m}^{1-o(1)} assuming any of the following conjectures: - Conjecture I: Circuit SAT requires 2^{n - o(n)} time on n-input circuits of size 2^{o(n)}. This conjecture is far weaker than the well-believed SETH conjecture from complexity theory, which asserts that CNF SAT with n variables and O(n) clauses already requires 2^{n-o(n)} time. - Conjecture II: Online (min,+) product between an integer n x n matrix and n vectors requires n^{3 - o(1)} time. This conjecture is weaker than the APSP conjectures widely used in fine-grained complexity. - Conjecture III (3-SUM Conjecture): Given three sets A,B,C of integers, each of size n, deciding whether there exist a in A, b in B, c in C such that a + b + c = 0 requires n^{2 - o(1)} time. This 1995 conjecture [Anka Gajentaan and Mark H. Overmars, 1995] was the first conjecture in fine-grained complexity. Our lower bound construction illustrates an interesting power of fully retroactive queries: they can be used to quickly solve batched pair evaluation. We believe this technique can prove useful for other data structure lower bounds, especially dynamic ones.
Cite as

Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, and Yuancheng Yu. Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.SWAT.2018.33,
  author =	{Chen, Lijie and Demaine, Erik D. and Gu, Yuzhou and Williams, Virginia Vassilevska and Xu, Yinzhan and Yu, Yuancheng},
  title =	{{Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{33:1--33:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.33},
  URN =		{urn:nbn:de:0030-drops-88593},
  doi =		{10.4230/LIPIcs.SWAT.2018.33},
  annote =	{Keywords: retroactive data structure, conditional lower bound}
}
Document
DOI: 10.4230/DagRep.7.5.97
Challenges and Opportunities of User-Level File Systems for HPC (Dagstuhl Seminar 17202)

Authors: André Brinkmann, Kathryn Mohror, and Weikuan Yu

Published in: Dagstuhl Reports, Volume 7, Issue 5 (2018)

Abstract
The performance gap between magnetic disks and data processing on HPC systems has become that huge that an efficient data processing can only be achieved by introducing non-volatile memory (NVRAM) as a new storage tier. Although the benefits of hierarchical storage have been adequately demonstrated to the point that the newest leadership class HPC systems will employ burst buffers, critical questions remain for supporting hierarchical storage systems, including: How should we present hierarchical storage systems to user applications, such that they are easy to use and that application code is portable across systems? How should we manage data movement through a storage hierarchy for best performance and resilience of data? How do the particular I/O use cases mandate the way we manage data? There have been many efforts to explore this space in the form of file systems, with increasingly more implemented at the user level. This is because it is relatively easy to swap in new, specialized user-level file systems for use by applications on a case-by-case basis, as opposed to the current mainstream approach of using general-purpose, system-level file systems which may not be optimized for HPC workloads and must be installed by administrators. In contrast, file systems at the user level can be tailored for specific HPC workloads for high performance and can be used by applications without administrator intervention. Many user-level file system developers have found themselves “having to reinvent the wheel” to implement various optimizations in their file systems. Thus, a main goal of this meeting was to bring together experts in I/O performance, file systems, and storage, and collectively explore the space of current and future problems and solutions for I/O on hierarchical storage systems in order to begin a community effort in enabling user-level file system support for HPC systems. We had a lively week of learning about each other’s approaches as well as unique I/O use cases that can influence the design of a community-driven file and storage system standards. The agenda for this meeting contained talks from participants on the following high level topics: HPC storage and I/O support today; what do HPC users need for I/O; existing user-level file system efforts; object stores and other alternative storage systems; and components for building user-level file systems. The talks were short and intended to be conversation starters for more in-depth discussions with the whole group. The participants engaged in lengthy discussions on various questions that arose from the talks including: Are we ready to program to a memory hierarchy versus block devices? Are the needs of HPC users reflected in our existing file systems and storage systems? Should we drop or keep POSIX moving forward? What do we mean when we say "user-level file system"? Do we all mean the same thing? How should the IO 500 benchmark be defined so it is fair and useful? and How are stage-in and stage-out actually going to work? The report for this seminar contains a record of the talks from the participants as well as the resulting discussions. Our hope is that the effort initiated during this seminar will result in long-term collaborations that will benefit the HPC community as a whole.
Cite as

André Brinkmann, Kathryn Mohror, and Weikuan Yu. Challenges and Opportunities of User-Level File Systems for HPC (Dagstuhl Seminar 17202). In Dagstuhl Reports, Volume 7, Issue 5, pp. 97-139, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{brinkmann_et_al:DagRep.7.5.97,
  author =	{Brinkmann, Andr\'{e} and Mohror, Kathryn and Yu, Weikuan},
  title =	{{Challenges and Opportunities of User-Level File Systems for HPC (Dagstuhl Seminar 17202)}},
  pages =	{97--139},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{5},
  editor =	{Brinkmann, Andr\'{e} and Mohror, Kathryn and Yu, Weikuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.5.97},
  URN =		{urn:nbn:de:0030-drops-82820},
  doi =		{10.4230/DagRep.7.5.97},
  annote =	{Keywords: High Performance Computing, I/O and Storage, Object Stores, User-level Storage Systems}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.64
The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints

Authors: Hung-I Yu, Tien-Ching Lin, and Der-Tsai Lee

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
In 1982, Drezner proposed the (1|1)-centroid problem on the plane, in which two players, called the leader and the follower, open facilities to provide service to customers in a competitive manner. The leader opens the first facility, and then the follower opens the second. Each customer will patronize the facility closest to him (ties broken in favor of the leader's one), thereby decides the market share of the two players. The goal is to find the best position for the leader’s facility so that his market share is maximized. The best algorithm for this problem is an O(n^2 log n)-time parametric search approach, which searches over the space of possible market share values. In the same paper, Drezner also proposed a general version of (1|1)-centroid problem by introducing a minimal distance constraint R, such that the follower's facility is not allowed to be located within a distance R from the leader's. He proposed an O(n^5 log n)-time algorithm for this general version by identifying O(n^4) points as the candidates of the optimal solution and checking the market share for each of them. In this paper, we develop a new parametric search approach searching over the O(n^4) candidate points, and present an O(n^2 log n)-time algorithm for the general version, thereby closing the O(n^3) gap between the two bounds.
Cite as

Hung-I Yu, Tien-Ching Lin, and Der-Tsai Lee. The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 64:1-64:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{yu_et_al:LIPIcs.ISAAC.2016.64,
  author =	{Yu, Hung-I and Lin, Tien-Ching and Lee, Der-Tsai},
  title =	{{The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{64:1--64:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.64},
  URN =		{urn:nbn:de:0030-drops-68337},
  doi =		{10.4230/LIPIcs.ISAAC.2016.64},
  annote =	{Keywords: competitive facility, Euclidean plane, parametric search}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.24
Polynomial Bounds for Decoupling, with Applications

Authors: Ryan O'Donnell and Yu Zhao

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
Let f(x) = f(x_1, ..., x_n) = sum_{|S|<=k} a_S prod_{i in S} x_i be an n-variate real multilinear polynomial of degree at most k, where S subseteq [n] = {1, 2, ..., n}. For its one-block decoupled version, vf(y,z) = sum_{abs(S)<=k} a_S sum_{i in S}} y_i prod_{j in S\{i}} z_j, we show tail-bound comparisons of the form Pr(abs(vf)(y,z)) > C_k t} <= D_k Pr(abs(f(x)) > t). Our constants C_k, D_k are significantly better than those known for "full decoupling". For example, when x, y, z are independent Gaussians we obtain C_k = D_k = O(k); when x, by, z are +/-1 random variables we obtain C_k = O(k^2), D_k = k^{O(k)}. By contrast, for full decoupling only C_k = D_k = k^{O(k)} is known in these settings. We describe consequences of these results for query complexity (related to conjectures of Aaronson and Ambainis) and for analysis of Boolean functions (including an optimal sharpening of the DFKO Inequality).
Cite as

Ryan O'Donnell and Yu Zhao. Polynomial Bounds for Decoupling, with Applications. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{odonnell_et_al:LIPIcs.CCC.2016.24,
  author =	{O'Donnell, Ryan and Zhao, Yu},
  title =	{{Polynomial Bounds for Decoupling, with Applications}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.24},
  URN =		{urn:nbn:de:0030-drops-58520},
  doi =		{10.4230/LIPIcs.CCC.2016.24},
  annote =	{Keywords: Decoupling, Query Complexity, Fourier Analysis, Boolean Functions}
}
  • Refine by Author
  • 2 Qiao, Youming
  • 1 Bai, Yu
  • 1 Bei, Xiaohui
  • 1 Brinkmann, André
  • 1 Chen, Lijie
  • Show More...

  • Refine by Classification
  • 2 Computing methodologies → Linear algebra algorithms
  • 1 Applied computing → Education
  • 1 Applied computing → Sequencing and genotyping technologies
  • 1 Computing methodologies → Algebraic algorithms
  • 1 General and reference → General literature
  • Show More...

  • Refine by Keyword
  • 1 ASR
  • 1 Automatic Speech Recognition
  • 1 Boolean Functions
  • 1 Child Speech
  • 1 Clustering
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 2 2016
  • 2 2018
  • 2 2019
  • 2 2021
  • 2 2022
  • Show More...

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact