检索结果-内蒙古大学图书馆

43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

作者： Cooper, Colin Rivera, Nicolas Department of Informatics King's College London London United Kingdom

ISBN: (纸本)9783959770132

We study voting models on graphs. In the beginning, the vertices of a given graph have some initial opinion. Over time, the opinions on the vertices change by interactions between graph neighbours. Under suitable conditions the system evolves to a state in which all vertices have the same opinion. In this work, we consider a new model of voting, called the Linear Voting Model. This model can be seen as a generalization of several models of voting, including among others, pull voting and push voting. One advantage of our model is that, even though it is very general, it has a rich structure making the analysis tractable. In particular we are able to solve the basic question about voting, the probability that certain opinion wins the poll, and furthermore, given appropriate conditions, we are able to bound the expected time until some opinion wins. © Colin Cooper and Nicolas Rivera.

关键词： Interacting particles Probabilistic voting randomized algorithm Voter model

来源：评论

学校读者我要写书评

暂无评论

Computational Methods For Functional Motif Identification and Approximate Dimension Reduction in Genomic Data

Computational Methods For Functional Motif Identification an...

引用

作者： Georgiev, Stoyan Duke University

学位级别：Ph.D.

Uncovering the DNA regulatory logic in complex organisms has been one of the important goals of modern biology in the post-genomic era. The sequencing of multiple genomes in combination with the advent of DNA microarrays and, more recently, of massively parallel high-throughput sequencing technologies has made possible the adoption of a global perspective to the inference of the regulatory rules governing the context-specific interpretation of the genetic code that complements the more focused classical experimental approaches. Extracting useful information and managing the complexity resulting from the sheer volume and the high-dimensionality of the data produced by these genomic assays has emerged as a major challenge which we attempt to address in this work by developing computational methods and tools, specifically designed for the study of the gene regulatory processes in this new global genomic context. First, we focus on the genome-wide discovery of physical interactions between regulatory sequence regions and their cognate proteins at both the DNA and RNA level. We present a motif analysis framework that leverages the genome-wide evidence for sequence-specific interactions between trans-acting factors and their preferred cis-acting regulatory regions. The utility of the proposed framework is demonstarted on DNA and RNA cross-linking high-throughput data. A second goal of this thesis is the development of scalable approaches to dimension reduction based on spectral decomposition and their application to the study of population structure in massive high-dimensional genetic data sets. We have developed computational tools and have performed theoretical and empirical analyses of their statistical properties with particular emphasis on the analysis of the individual genetic variation measured by Single Nucleotide Polymorphism (SNP) microrarrays.

关键词： Bioinformatics binding site chip-seq dimension reduction population structure randomized algorithm transcription factor

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for Large-Scale Phylogenetic Reconstruction

Fast Algorithms for Large-Scale Phylogenetic Reconstruction

引用

作者： Truszkowski, Jakub University of Waterloo

学位级别：master

One of the most fundamental computational problems in biology is that of inferring evolutionary histories of groups of species from sequence data. Such evolutionary histories, known as phylogenies are usually represented as binary trees where leaves represent extant species, whereas internal nodes represent their shared ancestors. As the amount of sequence data available to biologists increases, very fast phylogenetic reconstruction algorithms are becoming necessary. Currently, large sequence alignments can contain up to hundreds of thousands of sequences, making traditional methods, such as Neighbor Joining, computationally prohibitive. To address this problem, we have developed three novel fast phylogenetic algorithms. The first algorithm, QTree, is a quartet-based heuristic that runs in O(n log n) time. It is based on a theoretical algorithm that reconstructs the correct tree, with high probability, assuming every quartet is inferred correctly with constant probability. The core of our algorithm is a balanced search tree structure that enables us to locate an edge in the tree in O(log n) time. Our algorithm is several times faster than all the current methods, while its accuracy approaches that of Neighbour Joining. The second algorithm, LSHTree, is the first sub-quadratic time algorithm with theoretical performance guarantees under a Markov model of sequence evolution. Our new algorithm runs in O(n^{1+γ(g)} log^2 n) time, where γ is an increasing function of an upper bound on the mutation rate along any branch in the phylogeny, and γ(g) < 1 for all g. For phylogenies with very short branches, the running time of our algorithm is close to linear. In experiments, our prototype implementation was more accurate than the current fast algorithms, while being comparably fast. In the final part of this thesis, we apply the algorithmic framework behind LSHTree to the problem of placing large numbers of short sequence reads onto a fixed phylogenetic tree. Our initial res

关键词： phylogeny randomized algorithm quartet Markov chain

来源：评论

学校读者我要写书评

暂无评论

A Packet Scheduling Mechanism for Wireless Peer-to-Peer Content Distribution

A Packet Scheduling Mechanism for Wireless Peer-to-Peer Cont...

引用

作者： Liu, Yao Texas A&M University

学位级别：硕士

This thesis studies the problem of content distribution in wireless peer-to-peer networks with selfish nodes. In this problem a group of wireless nodes need to exchange a set of files over a lossless broadcast channel. Each node aims to maximize its own download rate and minimize its upload rate. We propose a distributed protocol that provides incentives for selfish nodes to participate in the content exchange. Our protocol does not require any exchange of money and reputation and hence can be easily implemented without additional infrastructure. Then, we will analyze the performance of our protocol by focusing on the import-ant case in which the system contains two files that need to be distributed. We derive a closed-form expression of Nash Equilibrium and characterize the corresponding system performance in discrete time. Furthermore, we propose a distributed mechanism where the strategy of each node is only based on the observed history of the system and not on the private information of other nodes. We also study the performance characteristics of the systems that employ network coding to facilitate data exchange. We show that, due to the free rider problem network coding does not necessary improve the performance of the system and, in some cases, may lead to worse system performance. We propose a novel approach to this problem based on random coding. The performance of the network coding algorithms is validated by performing extensive simulation study.

关键词： Peer-to-Peer Wireless Game Theory Network Coding randomized algorithm Thesis

来源：评论

学校读者我要写书评

暂无评论

Topology optimization with multiple materials, multiple constraints, and multiple load cases

Topology optimization with multiple materials, multiple cons...

引用

作者： Zhang, Xiaojia Shelly Georgia Institute of Technology

学位级别：博士

Topology optimization is a practical tool that allows for improved structural designs. This thesis focuses on developing both theoretical foundations and computational algorithms for topology optimization to effectively and efficiently handle many materials, many constraints, and many load cases. Most work in topology optimization is restricted to linear material with limited constraint settings for multiple materials. To address these issues, we propose a general multi-material topology optimization formulation with material nonlinearity. This formulation handles an arbitrary number of materials with flexible properties, features freely specified material layers, and includes a generalized volume constraint setting. To efficiently handle such arbitrary constraints, we derive an update scheme, named ZPR, that performs robust updates of design variables associated with each constraint independently. The derivation is based on the separable feature of the dual problem of the convex approximated primal subproblem with respect to the Lagrange multipliers, and thus the update of design variables in each constraint only depends on the corresponding Lagrange multiplier. This thesis also presents an efficient filtering scheme, with reduced-order modeling, and demonstrates its application to 2D and 3D topology optimization of truss networks. The proposed filtering scheme extracts valid structures, yields the displacement field without artificial stiffness, and improve convergence, leading to drastically improved computational performance. To obtain designs under many load cases, we present a randomized approach that efficiently optimizes structures under hundreds of load cases. This approach only uses 5 or 6 stochastic sample load cases, instead of hundreds, to obtain similar optimized designs (for both continuum and truss approaches). Through examples using Ogden-based, bilinear, and linear materials, we demonstrate that proposed topology optimization frameworks with the ne

关键词： Topology optimization Multi-material topology optimization Nonlinear topology optimization Multi-objective optimization Density-based method Ground structure method Truss layout optimization Michell structures Optimality conditions Material nonlinearity Hyperelastic model Multiple constraints Multiple load cases Discrete filter Material selection algorithm Update scheme ZPR update algorithm Stochastic sampling randomized algorithm Additive manufacturing

来源：评论

学校读者我要写书评

暂无评论

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-651

引用

2016年

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-651 by published by

关键词： adversary algorithm chapter execution general model lemma mit-lcs-tr-651 mutual exclusion optimal randomized player probability probability distribution probability space random random variable random variables randomized randomized algorithm randomized algorithms randomized computing set

来源：评论

学校读者我要写书评

暂无评论

Signature-Free Asynchronous Byzantine Consensus with t < n/3 and O(n²) Messages 14

Signature-Free Asynchronous Byzantine Consensus with <i>t</i...

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Mostefaoui, Achour Moumen, Hamouma Raynal, Michel Univ Nantes LINA F-44322 Nantes France Univ Bejaia Bejaia Algeria Univ Rennes Inst Univ France Rennes France Univ Rennes IRISA Rennes France

ISBN: (纸本)9781450329446

This paper presents a new round-based asynchronous consensus algorithm that copes with up to t < n/3 Byzantine processes, where n is the total number of processes. In addition of not using signature, not assuming a computationally-limited adversary, while being optimal with respect to the value of t, this algorithm has several noteworthy properties: the expected number of rounds to decide is four, each round is composed of two or three communication steps and involves O(n(2)) messages, and a message is composed of a round number plus a single bit. To attain this goal, the consensus algorithm relies on a common coin as defined by Rabin, and a new extremely simple and powerful broadcast abstraction suited to binary values. The main target when designing this algorithm was to obtain a cheap and simple algorithm. This was motivated by the fact that, among the first-class properties, simplicity -albeit sometimes under-estimated or even ignored- is a major one.

关键词： Abstraction Asynchronous message-passing system Broadcast abstraction Byzantine process Common coin Consensus Distributed algorithm Optimal resilience randomized algorithm Signature-free algorithm Simplicity

来源：评论

学校读者我要写书评

暂无评论

randomized self-updating process for clustering large-scale data

引用

Statistics and Computing 2024年第1期34卷 47-47页

作者： Shiu, Shang-Ying Chin, Yen-Shiu Lin, Szu-Han Chen, Ting-Li Department of Statistics National Taipei University New Taipei Taiwan Institute of Statistics National Tsing Hua University Hsinchu Taiwan Institute of Statistical Science Academia Sinica Taipei Taiwan

This paper introduces the randomized self-updating process (rSUP) algorithm for clustering large-scale data. rSUP is an extension of the self-updating process (SUP) algorithm, which has shown effectiveness in clustering data with characteristics such as noise, varying cluster shapes and sizes, and numerous clusters. However, SUP’s reliance on pairwise dissimilarities between data points makes it computationally inefficient for large-scale data. To address this challenge, rSUP performs location updates within randomly generated data subsets at each iteration. The Law of Large Numbers guarantees that the clustering results of rSUP converge to those of the original SUP as the partition size grows. This paper demonstrates the effectiveness and computational efficiency of rSUP in large-scale data clustering through simulations and real datasets. © 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

关键词： Clustering analysis Large-scale data randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

FLIP-FLOP SPECTRUM-REVEALING QR FACTORIZATION AND ITS APPLICATIONS TO SINGULAR VALUE DECOMPOSITION

引用

ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS 2019年 51卷 469-494页

作者： Feng, Yuehua Xiao, Jianwei Gu, Ming Shanghai Univ Engn Sci Sch Math Phys & Stat Shanghai Peoples R China Univ Calif Berkeley Dept Math Berkeley CA 94720 USA

We present the Flip-Flop Spectrum-Revealing QR (Flip-Flop SRQR) factorization, a significantly faster and more reliable variant of the QLP factorization of Stewart for low-rank matrix approximations. Flip-Flop SRQR uses SRQR factorization to initialize a partial column-pivoted QR factorization and then computes a partial LQ factorization. As observed by Stewart in his original QLP work, Flip-Flop SRQR tracks the exact singular values with "considerable fidelity". We develop singular value lower bounds and residual error upper bounds for the Flip-Flop SRQR factorization. In situations where singular values of the input matrix decay relatively quickly, the low-rank approximation computed by Flip-Flop SRQR is guaranteed to be as accurate as the truncated SVD. We also perform a complexity analysis to show that Flip-Flop SRQR is faster than the randomized subspace iteration for approximating the SVD, the standard method used in the Matlab tensor toolbox. We additionally compare Flip-Flop SRQR with alternatives on two applications, a tensor approximation and a nuclear norm minimization, to demonstrate its efficiency and effectiveness.

关键词： QR factorization randomized algorithm low-rank approximation approximate SVD higher-order SVD nuclear norm minimization

来源：评论

学校读者我要写书评

暂无评论

Blockchain-based immunization against kleptographic attacks

引用

Science China(Information Sciences) 2024年第7期67卷 172-183页

作者： Changsong JIANG Chunxiang XU Jie CHEN Kefei CHEN School of Computer Science and Engineering University of Electronic Science and Technology of China Yangtze Delta Region Institute (Huzhou) University of Electronic Science and Technology of China Department of Mathematics Hangzhou Normal University

Adversarial implementations of cryptographic primitives called kleptographic attacks cause the leakage of secret information. Subliminal channel attacks are one of the kleptographic attacks. In such attacks, backdoors are embedded in implementations of randomized algorithms to elaborately control randomness generation, such that the secrets will be leaked from biased outputs. To thwart subliminal channel attacks, double-splitting is a feasible solution, which splits the randomness generator of a randomized algorithm into two independent generators. In this paper, we instantiate double-splitting to propose a secure randomness generation algorithm dubbed SRG using two physically independent generators: ordinary and public randomness generators. Based on public blockchains, we construct the public randomness generator,which can be verified publicly. Hashes of a sufficient number of consecutive blocks that are newly confirmed on a blockchain are used to produce public randomness. In SRG, outputs from the two generators are taken as inputs of an immunization function. SRG accomplishes immunization against subliminal channel ***, we discuss the application strategies of SRG for symmetric and public-key encryption.

关键词： kleptographic attacks subliminal channel blockchain immunization randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：