150 research outputs found
An Improved Algorithm for Incremental DFS Tree in Undirected Graphs
Get PDFDepth first search (DFS) tree is one of the most well-known data structures for designing efficient graph algorithms. Given an undirected graph G=(V,E) with n vertices and m edges, the textbook algorithm takes O(n+m) time to construct a DFS tree. In this paper, we study the problem of maintaining a DFS tree when the graph is undergoing incremental updates. Formally, we show:
Given an arbitrary online sequence of edge or vertex insertions, there is an algorithm that reports a DFS tree in O(n) worst case time per operation, and requires O (min {m log n, n^2}) preprocessing time.
Our result improves the previous O(n log^3 n) worst case update time algorithm by Baswana et al. [Baswana et al., 2016] and the O(n log n) time by Nakamura and Sadakane [Nakamura and Sadakane, 2017], and matches the trivial Omega(n) lower bound when it is required to explicitly output a DFS tree.
Our result builds on the framework introduced in the breakthrough work by Baswana et al. [Baswana et al., 2016], together with a novel use of a tree-partition lemma by Duan and Zhang [Duan and Zhang, 2016], and the celebrated fractional cascading technique by Chazelle and Guibas [Chazelle and Guibas, 1986a; Chazelle and Guibas, 1986b]
Research on the relationship between audit fees and audit quality under audit market competition based on modified Jones model
No full textToward Practical Quantum Computing Systems with Intelligent Cross-Stack Co-Design
No full textQuantum Computing (QC) has the potential to solve classically hard problems with greater speed and efficiency, and recent years have seen exciting advancements in this field. However, significant gaps remain between application requirements and the capabilities of current devices, particularly in terms of software framework support, efficiency, and reliability. To bridge these gaps and fully unleash the power of quantum computing, it is critical to perform AI-enhanced co-design across various technology stacks, from algorithm and program design to compilation and hardware architecture. In this thesis, we aim to develop architectural and system supports for quantum computing. To address the software support gap, I will discuss two compilation frameworks—FPQAC and Q-Pilot—designed for the Field-Programmable Qubit Array (FPQA) implemented with emerging reconfigurable neutral atom arrays. This architecture leverages movable atoms for routing two-qubit gates and we optimize atom movements and gate scheduling for high scalability and parallelism. To enhance reliability, I will introduce QuantumNAS and TorchQuantum, frameworks for quantum program structure (ansatz) design for variational quantum algorithms. QuantumNAS employs an intelligent search engine and utilizes noisy feedback from quantum devices to optimize program structure and qubit mapping tailored to specific hardware, leading to significant resource reduction and reliability improvements. Additionally, I will present QuantumNAT, QOC, and RobustState for noise-aware training of parameters in variational quantum algorithms to ensure high reliability. The DGR framework will also be discussed for addressing drifted and correlated errors in quantum error correction decoding. Furthermore, I will introduce QuEST, which leverages data-driven AI models to predict the reliability of arbitrary quantum circuits on real quantum hardware. Finally, to close the efficiency gap, I will present SpAtten, an algorithm-architecture-circuit co-design aimed at efficient Transformer-based quantum error correction decoding, and SpArch accelerator, designed for sparse tensor algebra for efficient quantum control signals generations.Ph.D
Did temporary people flow facilitate trade?: evidence from Schengen area and its partners
No full textM.Phil.This paper aims to identify the effect of the visa-free policy on the international trade of goods and service. It undertakes a natural experiment in the Schengen Area and uses the DID (Difference-in-Difference) model to reveal that the visa-free policy positively affects the trade of goods and service. Visa requirement is equivalent to approximately 6% additional tariff for international service trade when elasticiy of substitution equals 5, and the tariff equivalent for export of goods trade is even higher. The heterogeneous effects of visa-free policy on different industries were examined as well. This study enriches the understanding of international trade through the angle of temporary people ow instead of permanent people flow or migration, which has been the focus of existing literature. Besides, it introduces a new topic, visa-free policy, and tries to identify the impact on international trade.本篇文章意圖研究免簽政策對包括貨物貿易和服務貿易在內的國際貿易的影響。通過利用在向根地區的自然實驗和雙重查分法，本文發現兔簽政策的確對服務貿易和兔簽政策的停供國的貨物貿易出口有積極作用。對服務貿易來說，當設定彈性係數為5 的時候，簽證要求大約等同於額外百分之六的關稅。而對貨物貿易出口來說，簽證要求的關稅等值甚至更高。文章同樣檢測了其對不同亞組(或行業)的異質性效果。本文為我們理解圍際貿易提供了一個新的角度: 人口的短期國際流動。現有文獻主要關注於長期的乃至永久的人口流動，例如移民。另外，本文亦引入了一個新的話題:簽證政策， 並識別了其對國際貿易的影響。Zeng, Hanrui.Thesis M.Phil. Chinese University of Hong Kong 2019.Includes bibliographical references (leaves 31-32).Abstracts also in Chinese.Title from PDF title page (viewed on 21 May, 2021)
Diffusion-based Adversarial Purification Protecting Face Authentication Systems from Multi-task Gray-box Attacks
No full textDeep learning technologies have achieved superior performance in security applications, e.g., the face authentication. However, increasing security concerns are raised by adversarial attacks, which uncover critical vulnerabilities of deep learning models. This thesis revisits these vulnerabilities of deep learning technologies and reveals the limitations of existing adversarial attacks and defenses. Furthermore, this thesis proposes two adversarial attacks as measurement tools in such attack scenarios that existing methods do not apply. Finally, this thesis proposes defenses against adversarial attacks to enhance the security of face authentication systems
How does the method of farmland transfer affect the “non-grain” of farmland in China?
Get PDFIntroductionThe phenomenon of “non-grain” of farmland poses a major threat to food security. Currently, there is still debate about the relationship between farmland transfer and the “non-grain” of farmland. Currently, there is no consensus on the relationship between farmland transfer and the non-grain use of farmland. This article focuses on the evolution of farmland transfer methods, examines the impact of farmland transfer methods on the non-grain use of farmland, and highlights the importance of effectively promoting farmland transfer, curbing the non-grain use of farmland, and ensuring food security.MethodsBased on the China Rural Revitalization Survey (CRRS) data, this paper uses probit and ivprobit models to estimate the causal relationship between farmland transfer methods and the “non-grain” of farmland. Grouped regressions are conducted from three dimensions of geographical environment, village governance, and economic development to test the heterogeneity of the impact of farmland transfer methods. Finally, the pathways of action are analyzed from the perspectives of farmers’ identity transformation and contract signing.ResultsThe organized transfer can significantly reduce the degree of “non-grain” of farmland, and its effect is stronger when the village party secretary has a higher level of education and also serves as the village head. This effect is mainly manifested through increasing the probability of farmers becoming new agricultural operators, joining cooperatives, signing formal contracts, and determining the lease term.DiscussionThe policy implications of this study emphasize that to curb the “non-grain” of farmland and ensure food security, it is important not only to increase the rate of farmland transfer but also to promote the organization of farmland transfer transactions. This includes facilitating the transfer of farmland from inefficient smallholders and cultivating new agricultural operators. Simultaneously, leveraging the supervisory and management role of village collectives can encourage farmers to sign more formal written contracts, clarify the purpose of farmland transfer, and supervise and manage the use of farmland during the subsequent contract execution stage. A limitation of this study is that it relies on cross-sectional data and does not observe the time variation of farmland transfer methods for the same farmers or their long-term impact on the “non-grain” of farmland
Interleukin 1β Mediates the Pathogenesis of Nasal Mucosal Epithelial Barrier Dysfunction in Allergic Rhinitis
Get PDFHanrui Wang,1– 4,* Xiaoyu Song,1– 4,* Yao Wang,1– 4 Ting Yang,1– 4 Wanchen Liu,1– 4 Yakui Mou,1– 4,* Chao Ren,1– 5 Xicheng Song1– 4 1Department of Otorhinolaryngology, Head and Neck Surgery, Yantai Yuhuangding Hospital, Qingdao University, Yantai, People’s Republic of China; 2Shandong Provincial Key Laboratory of Neuroimmune Interaction and Regulation, Yantai Yuhuangding Hospital, Yantai, People’s Republic of China; 3Shandong Provincial Clinical Research Center for Otorhinolaryngologic Diseases, Yantai Yuhuangding Hospital, Yantai, People’s Republic of China; 4Yantai Key Laboratory of Otorhinolaryngologic Diseases, Yantai Yuhuangding Hospital, Qingdao University, Yantai, People’s Republic of China; 5Department of Neurology, Yantai Yuhuangding Hospital, Qingdao University, Yantai, People’s Republic of China*These authors contributed equally to this workCorrespondence: Xicheng Song; Chao Ren, Yantai Yuhuangding Hospital, Qingdao University, No. 20, East Road, Zhifu District, Yantai, 264000, People’s Republic of China, Tel +86535 6691999, Fax +86535 6240341, Email [email protected]; [email protected]: The nasal mucosal epithelial barrier is the primary site of allergic rhinitis (AR). Interleukin-1β (IL-1β), as a crucial factor in immune inflammation, not only plays a crucial role in hypersensitivity reactions but also affects the digestive mucosa and skin epithelial barrier. However, the role of IL-1β in the nasal mucosal epithelial barrier in AR has not been reported, and this study aimed to investigate the effect and possible mechanisms involved.Methods: Dermatophagoides pteronyssinus 1 was used as an allergen to construct an AR mouse model and stimulate human nasal mucosal epithelial cells (HNEpCs) and observe the expression changes of IL-1β and epithelial barrier indicators CLDN1 and OCLN in mouse nasal mucosa and HNEpCs. Then, the possible mechanisms of action were explored via exogenous IL-1β stimulation and pharmacological inhibition of IL-1β or its receptor interleukin-1 receptor type 1 (IL-1R1).Results: The results showed that Dermatophagoides pteronyssinus 1-primed mouse nasal mucosa or human HENpCs had increased expression of IL-1β and decreased CLDN1 and OCLN, and IL-1β could directly lead to reduced expression of epithelial barrier indexes in HNEpCs. In addition, inhibition of IL-1β or IL-1R1 can effectively alleviate the damage to the epithelial barrier.Conclusion: IL-1β has a destructive effect on the nasal mucosal epithelial barrier in AR, and inhibition of IL-1β or its receptor IL-1R1 can effectively protect the nasal mucosal barrier. IL-1β is a potential target for the treatment of AR.Keywords: interleukin-1β, allergic rhinitis, nasal mucous membrane, epithelial barrier, DerP
Thermal contact conductance of ceramic AlN and oxygen-free high-conductivity copper interfaces under low temperature and vacuum for high-temperature superconducting cryocooler cooling
No full textVoting with Your Feet: The Impact of Urban Public Health Service Accessibility on the Permanent Migration Intentions of Rural Migrants in China
No full textThe accessibility of urban public health services is not only relevant to the health status of rural migrants but also plays an increasingly important role in their migration decisions. Most existing studies have focused on the effects of the level of public health service provision and parity on rural migrants’ migration behavior, ignoring the role of public health service accessibility. This paper systematically examines the overall impact, heterogeneous impact and mechanism of action of public health service accessibility on rural migrants’ intentions to migrate permanently based on data from the 2017 China Mobile Population Dynamics Monitoring Survey using probit, IVprobit, eprobit, omitted variable test model and KHB mediating effect model. It was found that: (1) public health service accessibility significantly increased rural migrants’ intentions to migrate permanently, and the results remained robust after using instrumental variables to mitigate endogeneity problems and omitted variable tests. (2) Heterogeneity analysis shows that public health service accessibility has a greater effect on enhancing the intentions to migrate permanently among females and rural migrants born in 1980 and later. (3) Further mechanism testing revealed that public health service accessibility could indirectly increase rural migrants’ intentions to migrate permanently by improving health habits, health status, identity, and social integration, with identity playing a greater indirect effect. The findings of this paper not only provide empirical evidence for the existence of Tiebout’s “voting with your feet” mechanism in China but also contribute to the scientific understanding of the role of equalization of public health services in the process of population migration
- …
