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

A study of accessible motifs and RNA folding complexity

10th Annual International Conference on Research in Computational Molecular Biology

作者： Wexler, Ydo Zilberstein, Chaya Ziv-Ukelson, Michal Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)3540332952

mRNA molecules are folded in the cells and therefore many of their substrings may actually be inaccessible to protein and microRNA binding. The need to apply an accessibility criterion to the task of genome-wide mRNA motif discovery raises the challenge of overcoming the core O(n(3)) factor imposed by the time complexity of the currently best known algorithms for RNA secondary structure prediction. We speed up the dynamic programming algorithms that are standard for RNA folding prediction. Our new approach significantly reduces the computations without sacrificing the optimality of the results, yielding an expected time complexity of O(n(2)psi(n)), where psi(n) is shown to be constant on average under standard polymer folding models. A benchmark analysis confirms that in practice the runtime ratio between the previous approach and the new algorithm indeed grows linearly with increasing sequence size. The fast new RNA folding algorithm is utilized for genome-wide discovery of accessible cis-regulatory motifs in data sets of ribosomal densities and decay rates of S. cerevisiae genes and to the mining of exposed binding sites of tissue-specific microRNAs in A. thaliana.

关键词： average case complexity binding sites dynamic programming optimal solution RNA folding

来源：评论

学校读者我要写书评

暂无评论

Uniformly Random Colourings of Sparse Graphs 2023

Uniformly Random Colourings of Sparse Graphs

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Hurley, Eoin Pirot, Francois Univ Paris Saclay Gif Sur Yvette France

ISBN: (纸本)9781450399135

We analyse uniformly random proper k-colourings of sparse graphs with maximum degree Delta in the regime Delta < k ln k. This regime corresponds to the lower side of the shattering threshold for random graph colouring, a paradigmatic example of the shattering threshold for random Constraint Satisfaction Problems. We prove a variety of results about the solution space geometry of colourings of fixed graphs, generalising work of Achlioptas and Coja-Oghlan, and Molloy on random graphs, and justifying the performance of stochastic local search algorithms in this regime. Our central proof relies only on elementary techniques, namely the first-moment method and a quantitative induction, yet it strengthens list-colouring results due to Vu, and more recently Davies, Kang, P., and Sereni, and generalises state-of-the-art bounds from Ramsey theory in the context of sparse graphs. It further yields an approximately tight lower bound on the number of colourings.

关键词： triangle-free graphs graph colouring constraint satisfaction problems average case complexity random colourings freezing threshold shattering threshold approximation schemes

来源：评论

学校读者我要写书评

暂无评论

An Efficient Quantum Parallel Repetition Theorem and Applications 2024

An Efficient Quantum Parallel Repetition Theorem and Applica...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Bostanci, John Qian, Luowen Spooner, Nicholas Yuen, Henry Columbia Univ New York NY 10027 USA Boston Univ Boston MA 02215 USA Univ Warwick Coventry W Midlands England NYU New York NY USA

ISBN: (纸本)9798400703836

We prove a tight parallel repetition theorem for 3-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of 4-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, and Naor. Finally, we prove that all quantum argument systems can be generically compiled to an equivalent 3-message argument system, mirroring the transformation for quantum proof systems. As immediate applications, we show how to derive hardness amplification theorems for quantum bit commitment schemes (answering a question of Yan), EFI pairs (answering a question of Brakerski, Canetti, and Qian), public-key quantum money schemes (answering a question of Aaronson and Christiano), and quantum zero-knowledge argument systems. We also derive an XOR lemma for quantum predicates as a corollary.

关键词： average case complexity direct product post-quantum security puzzle

来源：评论

学校读者我要写书评

暂无评论

average case ANALYSIS OF UNIFICATION ALGORITHMS 8th

引用

8TH ANNUAL SYMP ON THEORETICAL ASPECTS COMPUTER SCIENCE ( STACS 91 )

作者： ALBERT, L CASAS, R FAGES, F TORRECILLAS, A ZIMMERMANN, P Institut National de Recherche en Informatique et Automatique Domaine de Voluceau Rocquencourt BP 105 Le Chesnay Cedex 78150 France Department of Llenguatges i Sistemes Informàtics Universitat Politècnica de Catalunya Pau Gargallo 5 Barcelona 08028 Spain LIENS URA 1327 CNRS Eeole Normale Supdrieure 45 rue d’Ulm Paris 75005 France

ISBN: (纸本)3540537090

Unification in first-order languages is a central operation in symbolic computation and logic programming. Many unification algorithms have been proposed in the past, however there is no consensus on which algorithm is the best to use in practice. While Paterson and Wegman’s linear unification algorithm has the lowest time complexity in the worst case, it requires an important overhead to be implemented. This is true also, although less importantly, for Martelli and Montanari’s algorithm [MM82], and Robinson’s algorithm [Rob71] is finally retained in many applications despite its exponential worst-case time complexity. There are many explanations for that situation: one important argument is that in practice unification subproblems are not independent, and linear unification algorithms do not perform well on sequences of unify-deunify operations [MU86]. In this paper we present average case complexity theoretic arguments. We first show that the family of unifiable pairs of binary trees is exponentially negligible with respect to the family of arbitrary pairs of binary trees formed over l binary function symbols, c constants and v variables. We analyze the different reasons for failure and get asymptotical and numerical evaluations. We then extend the previous results of [DL89] to these families of trees, we show that a slight modification of Herbrand-Robinson’s algorithm has a constant average cost on random pairs of trees. On the other hand, we show that various variants of Martelli and Montanari’s algorithm all have a linear average cost on random pairs of trees. The point is that failures by clash are not sufficient to lead to a constant average cost, an efficient occur check (i.e. without a complete traversal of subterms) is necessary. In the last section we extend the results on the probability of the occur check in presence of an unbounded number of variables. © Springer-Verlag Berlin Heidelberg 1991.

关键词： UNIFICATION ALGORITHMS average case complexity GENERATING FUNCTIONS

来源：评论

学校读者我要写书评

暂无评论

On optimal randomized group testing with one defective item and a constrained number of positive responses

引用

DISCRETE OPTIMIZATION 2021年 39卷 100621-100621页

作者： Cheng, Yongxi Yang, Yunyue Du, Ding-Zhu Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

Consider the group testing problem with an input set of size n and the number of defective items being d = 1, that allows at most y positive responses. Let A(n, y) denote the minimum expected number of tests required by a randomized testing strategy for this problem. The testing strategy is required to be Las Vagas, that is, guaranteed to give the correct classification of the items. Based on Yao's minimax principle, A(n, y) is equal to the minimum average number of tests for a deterministic group testing strategy allowing at most y positive responses, where the average is taken over all the n possible input sets of size n with d = 1. The main contribution of our paper is to show that A(n, y) is y/y+1 (ny!)(1/y) + O(y), for 1 <= y [log(2) n]. This solves an open question left in Damaschke (2016). (c) 2020 Elsevier B.V. All rights reserved.

关键词： Group testing Randomized algorithms average case complexity Lower bounds

来源：评论

学校读者我要写书评

暂无评论

On the average complexity of partial derivative transducers *,**,***

引用

THEORETICAL COMPUTER SCIENCE 2023年 956卷

作者： Konstantinidis, Stavros Machiavelo, Antonio Moreira, Nelma Reis, Rogerio Univ Porto CMUP & DM DCC Fac Ciencias Rua Campo Alegre P-4169007 Porto Portugal St Marys Univ 923 Robie Str Halifax NS Canada

2D regular expressions represent rational relations over two alphabets sigma and A. In standard 2D expressions (S2D-RE) the basic terms are generators of sigma* x A*, while in generalised 2D expressions (2D-RE) the basic terms are pairs of (ordinary) regular expressions over one alphabet (1D). In this paper we study the average state complexity of partial derivative standard transducers (TPD) for both S2D-RE and 2D-RE. For S2D-RE we obtain the same asymptotic bounds as for partial derivative automata. For 2D-RE, while in the worst case the number of states of TPD can be O (n2), where n is the size of the expression, asymptotically and on average that value is bounded from above by O (n 2 ). We also show that asymptotically and on average the alphabetic size of a 2D-RE is half of its size. All results are obtained in the framework of analytic combinatorics considering generating functions of parametrised combinatorial classes defined implicitly by algebraic curves. In particular, we generalise the methods developed in previous work to a broad class of analytic functions.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Transducers Rational expressions Partial derivatives Analytic combinatorics average case complexity

来源：评论

学校读者我要写书评

暂无评论

RANDOM QUANTUM SATISFIABIILTY

引用

QUANTUM INFORMATION & COMPUTATION 2010年第1-2期10卷 1-15页

作者： Laumann, C. R. Moessner, R. Scardicchio, A. Sondhi, S. L. Princeton Univ Dept Phys Princeton Ctr Theoret Sci Princeton NJ 08544 USA Max Planck Inst Phys Komplexer Syst D-01187 Dresden Germany

Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. We study random ensembles of the QMA(1)-complete quantum satisfiability (QSAT) problem introduced by Bravyi [1]. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for any hypergraph exhibit the same dimension of the satisfying manifold. This establishes the QSAT decision problem as equivalent to a, potentially new, graph theoretic problem and that the hardest typical instances are likely to be localized in a bounded range of clause density.

关键词： disordered quantum satisfiability QSAT SAT average case complexity

来源：评论

学校读者我要写书评

暂无评论

CONSTRAINED INHOMOGENEOUS SPHERICAL EQUATIONS: average-case HARDNESS

引用

GROUPS complexity CRYPTOLOGY 2024年第1期16卷 3:1-3:18页

作者： Ushakov, Alexander Stevens Inst Technol Dept Math Sci Hoboken NJ 07030 USA

In this paper we analyze computational properties of the Diophantine problem (and its search variant) for spherical equations Pi(m)(i =1) z(i)(-1) c(i)z(i) = 1 (and their variants) over the class of finite metabelian groups G(p,n) = Z(p)(n) (sic) Z(p*), where n is an element of N and p is prime. We prove that the problem of finding solutions for certain constrained spherical equations is computationally hard on average (assuming that some lattice approximation problem is hard in the worst case).

关键词： Spherical equations finite groups semidirect products metabelian groups average case complexity hash function family group-based cryptography

来源：评论

学校读者我要写书评

暂无评论

Erratum for: on basing one-way functions on NP-hardness 10

Erratum for: on basing one-way functions on NP-hardness

引用

Proceedings of the forty-second ACM symposium on Theory of computing

作者： Adi Akavia Oded Goldreich Shafi Goldwasser Dana Moshkovitz The Weizmann Institute of Science Rehovot Israel MIT and The Weizmann Institute of Science Cambridge MA and Rehovot USA The Institute for Advanced Study Princeton NJ USA

This is an errata for our STOC'06 paper, "On Basing One-Way Functions on NP-Hardness".There is a gap in the proof of our results regarding adaptive reductions, and we currently do not know whether Theore... 详细信息

ISBN: (纸本)9781450300506

关键词： one-way function worst case complexity erratum average case complexity

来源：评论

学校读者我要写书评

暂无评论

Probabilistic analysis of a parallel algorithm for finding maximal independent sets

引用

Random Structures & Algorithms 1990年第1期1卷 39-50页

作者： Calkin, Neil Frieze, Alan Department of Mathematics Carnegie Mellon University Pittsburgh Pennsylvania 15213-3890 United States

We consider a natural parallel version of the classical greedy algorithm for finding a maximal independent set in a graph. This version was studied in Coppersmith, Raghavan, and Tompa and they conjecture there that its expected running time on random graphs of arbitrary edge density of O (log n). We prove that conjecture. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company

关键词： average case complexity independent sets parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：