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

arXiv 2024年

作者： Wang, Dingkang Wei, Jingjing Xiao, Fanghui Zheng, Xiaopeng KLMM Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing100190 China School of Mathematical Sciences University of Chinese Academy of Sciences Beijing100049 China Beijing ETown Academy Beijing100176 China MOE-LCSM School of Mathematics and Statistics Hunan Normal University Hunan410081 China

Based on the partition of parameter space, two algorithms for computing the rational univariate representation of zero-dimensional ideals with parameters are presented in the paper. Unlike the rational univariate representation of zero-dimensional ideals without parameters, the number of zeros of zero-dimensional ideals with parameters under various specializations is different, which leads to choosing and checking the separating element, the key to computing the rational univariate representation, is difficult. In order to pick out the separating element, we first ensure that under each branch the ideal has the same number of zeros by partitioning the parameter space. Subsequently two ideas are given to choose and check the separating element. One idea is that by extending the subresultant theorem to parametric cases, we utilize the extended subresultant theorem to choose the separating element with the further partition of parameter space and then with the help of parametric greatest common divisor theory compute rational univariate representations. Another one is that we go straight to choose and check the separating element by the computation of parametric greatest common divisors, then immediately get the rational univariate representations. Based on these, we design two different algorithms for computing rational univariate representations of zero-dimensional ideals with parameters. Furthermore, the algorithms have been implemented on Singular and the performance comparison are presented. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Inferring microbial co-occurrence networks from amplicon data: a systematic evaluation

引用

MSYSTEMS 2023年第4期8卷 e0096122页

作者： Kishore, Dileep Birzu, Gabriel Hu, Zhenjun DeLisi, Charles Korolev, Kirill S. Segre, Daniel Boston Univ Bioinformat Program Boston MA 02215 USA Boston Univ Biol Design Ctr Boston MA 02215 USA Biosci Div Oak Ridge Natl Lab Oak Ridge TN USA Boston Univ Dept Phys Boston MA 02215 USA Stanford Univ Dept Appl Phys Stanford CA USA Boston Univ Dept Biomed Engn Boston MA 02215 USA Boston Univ Dept Biol Boston MA 02215 USA

Microbes commonly organize into communities consisting of hundreds of species involved in complex interactions with each other. 16S ribosomal RNA (16S rRNA) amplicon profiling provides snapshots that reveal the phylogenies and abundance profiles of these microbial communities. These snapshots, when collected from multiple samples, can reveal the co-occurrence of microbes, providing a glimpse into the network of associations in these communities. However, the inference of networks from 16S data involves numerous steps, each requiring specific tools and parameter choices. Moreover, the extent to which these steps affect the final network is still unclear. In this study, we perform a meticulous analysis of each step of a pipeline that can convert 16S sequencing data into a network of microbial associations. Through this process, we map how different choices of algorithms and parameters affect the co-occurrence network and identify the steps that contribute substantially to the variance. We further determine the tools and parameters that generate robust co-occurrence networks and develop consensus network algorithms based on benchmarks with mock and synthetic data sets. The Microbial Co-occurrence Network Explorer, or MiCoNE (available at ) follows these default tools and parameters and can help explore the outcome of these combinations of choices on the inferred networks. We envisage that this pipeline could be used for integrating multiple data sets and generating comparative analyses and consensus networks that can guide our understanding of microbial community assembly in different biomes.

关键词： Microbiome 16S rRNA interaction denoising taxonomy network inference correlations QIIME2 co-occurrence networks consensus algorithm pipeline nextflow

来源：评论

学校读者我要写书评

暂无评论

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth

arXiv

引用

arXiv 2025年

作者： Jiang, Yonggang Yun, Changki MPI INF Saarland University Germany Seoul National University Seoul Korea Republic of

We present a randomized parallel algorithm in the PRAM model for k-vertex connectivity. Given an undirected simple graph, our algorithm either finds a set of fewer than k vertices whose removal disconnects the graph or reports that no such set exists. The algorithm runs in O(m · poly(k, log n)) work and O(poly(k, log n)) depth, which is nearly optimal for any k = poly(log n). Prior to our work, algorithms with near-linear work and polylogarithmic depth were known only for k = 3 [Miller, Ramachandran, STOC’87];for k = 4, sequential algorithms achieving near-linear time were known [Forster, Nanongkai, Yang, Saranurak, Yingchareonthawornchai, SODA’20], but no algorithm with near-linear work could achieve even sublinear (on n) depth. © 2025, CC BY.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Why Domain Generalization Fail? A View of Necessity and Sufficiency

arXiv

引用

arXiv 2025年

作者： Vuong, Tung-Long Vo, Vy Dang, Hien Nguyen, Van-Anh Do, Thanh-Toan Harandi, Mehrtash Le, Trung Phung, Dinh Monash University Australia University of Texas Austin United States

Despite a strong theoretical foundation, empirical experiments reveal that existing domain generalization (DG) algorithms often fail to consistently outperform the ERM baseline. We argue that this issue arises because most DG studies focus on establishing theoretical guarantees for generalization under unrealistic assumptions, such as the availability of sufficient, diverse (or even infinite) domains or access to target domain knowledge. As a result, the extent to which domain generalization is achievable in scenarios with limited domains remains largely unexplored. This paper seeks to address this gap by examining generalization through the lens of the conditions necessary for its existence and learnability. Specifically, we systematically establish a set of necessary and sufficient conditions for generalization. Our analysis highlights that existing DG methods primarily act as regularization mechanisms focused on satisfying sufficient conditions, while often neglecting necessary ones. However, sufficient conditions cannot be verified in settings with limited training domains. In such cases, regularization targeting sufficient conditions aims to maximize the likelihood of generalization, whereas regularization targeting necessary conditions ensures its existence. Using this analysis, we reveal the shortcomings of existing DG algorithms by showing that, while they promote sufficient conditions, they inadvertently violate necessary conditions. To validate our theoretical insights, we propose a practical method that promotes the sufficient condition while maintaining the necessary conditions through a novel subspace representation alignment strategy. This approach highlights the advantages of preserving the necessary conditions on well-established DG benchmarks. © 2025, CC BY.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

THE SEA algorithm FOR ENDOMORPHISMS OF SUPERSINGULAR ELLIPTIC CURVES

arXiv

引用

arXiv 2025年

作者： Morrison, Travis Panny, Lorenz Sotáková, Jana Wills, Michael Virginia Tech United States Technische Universität München Germany University of Amsterdam Netherlands University of Virginia United States

For a prime p > 3 and a supersingular elliptic curve E defined over Fp2 with j(E) ∈/ {0, 1728}, consider an endomorphism α of E represented as a composition of L isogenies of degree at most d. We prove that the trace of α may be computed in O(n4(log n)2 + dLn3) bit operations, where n = log(p), using a generalization of the SEA algorithm for computing the trace of the Frobenius endomorphism of an ordinary elliptic curve. When L ∈ O(log p) and d ∈ O(1), this complexity matches the heuristic complexity of the SEA algorithm. Our theorem is unconditional, unlike the complexity analysis of the SEA algorithm, since the kernel of an arbitrary isogeny of a supersingular elliptic curve is defined over an extension of constant degree, independent of p. We also provide practical speedups, including a fast algorithm to compute the trace of α modulo p. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

An inertial proximal splitting algorithm for hierarchical bilevel equilibria in Hilbert spaces

arXiv

引用

arXiv 2025年

作者： Balhag, Aicha Mazgouri, Zakaria Riahi, Hassan Théra, Michel Ecole Normale Supérieure Université Cadi Ayyad Marrakesh Morocco National School of Applied Sciences Sidi Mohamed Ben Abdellah University Fez30000 Morocco Université Cadi Ayyad Faculté des Sciences Semlalia Département de Mathématiques MarrakeshB.P. 2390 Morocco XLIM UMR CNRS 7252 Université de Limoges Limoges France

In this article, we aim to approximate a solution to the bilevel equilibrium problem (BEP) for short: find x¯ ∈ Sf such that g(x¯, y) ≥ 0, ∀y ∈ Sf, where Sf = {u ∈ K: f(u, z) ≥ 0, ∀z ∈ K}. Here, K is a closed convex subset of a real Hilbert space H, and f and g are two real-valued bifunctions defined on K×K. We propose an inertial version of the proximal splitting algorithm introduced by Z. Chbani and H. Riahi: Weak and strong convergence of prox-penalization and splitting algorithms for bilevel equilibrium problems. Numer. Algebra Control Optim., 3 (2013), pp. 353-366. Under suitable conditions, we establish the weak and strong convergence of the sequence generated by the proposed iterative method. We also report a numerical example illustrating our theoretical *** Codes 90C33, 49J40, 46N10, 65K15, 65K10 © 2025, CC BY.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Average Case Complexity of Berge algorithm

SSRN

引用

SSRN 2025年

作者： David, Julien Gholami, Mostafa Lhote, Loick CNRS NormaSTIC FR 3638 France Université Caen Normandie ENSICAEN CNRS Normandie Univ GREYC UMR6072 CaenF-14000 France

Given a hypergraph, computing its transversal hypergraph is a classical problem whose exact worst-case complexity is still unknown today. In this article, for Erdos and Renyi random hypergraph models, we compute the average number of minimal transversals. We also study the average complexity of Berge's algorithm, which sequentially enumerates the minimal transversals. We prove that the average complexity of Berge is quasi-linear in the average number of minimal traverses. Our contribution is also methodological: we use a wide range of analytic combinatorics techniquesto extract the coefficients of probabilistic generating functions. © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Composing Quantum algorithms

arXiv

引用

arXiv 2025年

作者： Jeffery, Stacey QuSoft CWI University of Amsterdam Netherlands

Composition is something we take for granted in classical algorithms design, and in particular, we take it as a basic axiom that composing "efficient" algorithms should result in an "efficient" algorithm – even using this intuition to justify our definition of "efficient." Composing quantum algorithms is a much more subtle affair than composing classical algorithms. It has long been known that zero-error quantum algorithms do not compose, but it turns out that, using the right algorithmic lens, bounded-error quantum algorithms do. In fact, in the bounded-error setting, quantum algorithms can even avoid the log factor needed in composing bounded-error randomized algorithms that comes from amplifying the success probability via majority voting. In this article, aimed at a general computer science audience, we try to give some intuition for these results: why composing quantum algorithms is tricky, particularly in the zero-error setting, but why it nonetheless works better than classical composition in the bounded-error setting. © 2025, CC BY.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Faster Distributed ∆-Coloring via Ruling Subgraphs

arXiv

引用

arXiv 2025年

作者： Bourreau, Yann Brandt, Sebastian Nolin, Alexandre CISPA Helmholtz Center for Information Security Germany

Brooks’ theorem states that all connected graphs but odd cycles and cliques can be colored with ∆ colors, where ∆ is the maximum degree of the graph. Such colorings have been shown to admit non-trivial distributed algorithms [Panconesi and Srinivasan, Combinatorica 1995] and have been studied intensively in the distributed literature. In particular, it is known that any deterministic algorithm computing a ∆-coloring requires Ω(log n) rounds in the LOCAL model [Chang, Kopelowitz, and Pettie, FOCS 2016], and that this lower bound holds already on constant-degree graphs. In contrast, the best upper bound in this setting is given by an O(log2 n)-round deterministic algorithm that can be inferred already from the works of [Awerbuch, Goldberg, Luby, and Plotkin, FOCS 1989] and [Panconesi and Srinivasan, Combinatorica 1995] roughly three decades ago, raising the fundamental question about the true complexity of ∆-coloring in the constant-degree setting. We answer this long-standing question almost completely by providing an almost-optimal deterministic O(log n log∗ n)-round algorithm for ∆-coloring, matching the lower bound up to a log∗ n-factor. Similarly, in the randomized LOCAL model, we provide an O(log log n log∗ n)-round algorithm, improving over the state-of-the-art upper bound of O(log2 log n) [Ghaffari, Hirvonen, Kuhn, and Maus, Distributed Computing 2021] and almost matching the Ω(log log n)-round lower bound by [BFHKLRSU, STOC 2016]. Our results make progress on several important open problems and conjectures. One key ingredient for obtaining our results is the introduction of ruling subgraph families as a novel tool for breaking symmetry between substructures of a graph, which we expect to be of independent interest. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Tight Analysis of Difference-of-Convex algorithm (DCA) Improves Convergence Rates for Proximal Gradient Descent

arXiv

引用

arXiv 2025年

作者： Rotaru, Teodor Patrinos, Panagiotis Glineur, François KU Leuven UCLouvain Belgium KU Leuven Belgium UCLouvain Belgium

We investigate a difference-of-convex (DC) formulation where the second term is allowed to be weakly convex. We examine the precise behavior of a single iteration of the difference-of-convex algorithm (DCA), providing a tight characterization of the objective function decrease, distinguishing between six distinct parameter regimes. Our proofs, inspired by the performance estimation framework, are notably simplified compared to related prior research. We subsequently derive sublinear convergence rates for the DCA towards critical points, assuming at least one of the functions is smooth. Additionally, we explore the underexamined equivalence between proximal gradient descent (PGD) and DCA iterations, demonstrating how DCA, a parameter-free algorithm, without the need for a stepsize, serves as a tool for studying the exact convergence rates of PGD. Finally, we propose a method to optimize the DC decomposition to achieve optimal convergence rates, potentially transforming the subtracted function to become weakly convex. © 2025, CC BY-NC-ND.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：