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

您好，读者！请登录

内蒙古大学图书馆

首页
概况
党建
资源
服务
科研支持
- 论文收录引用证明
- 科技查新
知识产权
档案馆
帮助

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入0个字，您还可以输入200个字

全部搜索
期刊论文
图书
学位论文
标准
纸本馆藏
外文资源发现
数据库导航
超星发现

高级检索

时间限定

出版年份：

文献类型

图书期刊文献学位论文多媒体

馆藏选择

电子馆藏纸本馆藏

核心期刊

全部期刊 SCI 收录期刊 SSCI 收录期刊 EI 收录期刊 CSCD 收录期刊 CSSCI 收录期刊

语言

中文英文

文献类型

期刊文献图书学位论文标准纸本馆藏

帮助

文字说明：

T=题名（书名、题名），A=作者（责任者），K=主题词，P=出版物名称，PU=出版社名称，O=机构（作者单位、学位授予单位、专利申请人），L=中图分类号，C=学科分类号，U=全部字段，Y=年（出版发行年、学位年度、标准发布年）

检索规则说明：

AND代表“并且”；OR代表“或者”；NOT代表“不包含”；(注意必须大写,运算符两边需空一格)

检索范例：

范例一：(K=图书馆学 OR K=情报学) AND A=范并思 AND Y=1982-2016
范例二：P=计算机应用与软件 AND (U=C++ OR U=Basic) NOT K=Visual AND Y=2011-2016

分类表

所选分类

>> <<

限定检索结果

文献类型

5 篇 会议
1 篇 学位论文

馆藏范围

6 篇 电子文献
0 种 纸本馆藏

日期分布

学科分类号

5 篇 理学
- 5 篇 数学
5 篇 工学
- 5 篇 计算机科学与技术...
1 篇 管理学
- 1 篇 管理科学与工程(可...

主题

6 篇 randomness in co...
2 篇 average-case com...
1 篇 intermittent sea...
1 篇 quantum computin...
1 篇 computational co...
1 篇 succinct data st...
1 篇 information theo...
1 篇 smoothed analysi...
1 篇 ccrw
1 篇 random walks
1 篇 computational bi...
1 篇 combinatorics an...
1 篇 trace reconstruc...
1 篇 sublinear algori...
1 篇 levy flights
1 篇 search algorithm...

机构

1 篇 columbia univers...
1 篇 nyu ny 10003 usa
1 篇 univ paris irif ...
1 篇 stanford univ ma...
1 篇 stanford univ ms...
1 篇 univ washington ...
1 篇 mit lids cambrid...
1 篇 columbia univ ny...
1 篇 univ maryland co...
1 篇 tel aviv univ te...

作者

1 篇 peri noam
1 篇 korman amos
1 篇 bresler guy
1 篇 cohen gil
1 篇 liu yang p.
1 篇 sidford aaron
1 篇 mutreja saachi
1 篇 goldin eli
1 篇 guinard brieuc
1 篇 ball marshall
1 篇 jambulapati arun
1 篇 guo chenghao
1 篇 lee james r.
1 篇 polyanskiy yury
1 篇 ta-shma amnon
1 篇 sinha sandip
1 篇 dachman-soled da...

语言

6 篇 英文

检索条件"主题词=Randomness in computing"

共 6 条记录，以下是1-10 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

Sparsifying Sums of Norms 64

Sparsifying Sums of Norms

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Jambulapati, Arun Lee, James R. Liu, Yang P. Sidford, Aaron Univ Washington Comp Sci & Engn Seattle WA 98195 USA Stanford Univ Math Palo Alto CA USA Stanford Univ MS&E Palo Alto CA USA

ISBN: (纸本)9798350318944

For any norms N-1, ... , N-m on R-n and N(x) := N-1(x) + ... + N-m(x), we show there is a sparsified norm (N) over tilde (x) = w(1)N(1)(x) + ... + w(m)N(m)(x) such that vertical bar N(x)-(N) over tilde (x)vertical bar <= epsilon N(x) for all x is an element of R-n, where w(1), ... , w(m) are non-negative weights, of which only O(epsilon(-2) n log(n/epsilon)(log n)(2.5)) are non-zero. Additionally, we show that such weights can be found with high probability in time O(m(log n)(O(1)) + poly(n))T, where T is the time required to evaluate a norm N-i(x), assuming that N(x) is poly(n)-equivalent to the Euclidean norm. This immediately yields analogous statements for sparsifying sums of symmetric submodular functions. More generally, we show how to sparsify sums of pth powers of norms when the sum is p-uniformly smooth. (1)

关键词： randomness in computing

来源：评论

学校读者我要写书评

暂无评论

Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles 64

Algorithmic Decorrelation and Planted Clique in Dependent Ra...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Bresler, Guy Guo, Chenghao Polyanskiy, Yury MIT LIDS Cambridge MA 02139 USA

ISBN: (纸本)9798350318944

We aim to understand the extent to which the noise distribution in a planted signal-plus-noise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erdos-Renyi G(n, p), which has independent edges, we take the ambient graph to be the random graph with triangles (RGT) obtained by adding triangles to G(n, p). We show that the RGT can be efficiently mapped to the corresponding G(n, p), and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erdos-Renyi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations.

关键词： average-case complexity randomness in computing

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths 37

Tight Bounds for the Cover Times of Random Walks with Hetero...

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Guinard, Brieuc Korman, Amos Univ Paris IRIF CNRS Paris France

ISBN: (纸本)9783959771405

Search patterns of randomly oriented steps of different lengths have been observed on all scales of the biological world, ranging from microscopic to the ecological, including in protein motors, bacteria, T-cells, honeybees, marine predators, and more, see e.g., [21, 22, 31, 33, 34, 35, 36]. Through different models, it has been demonstrated that adopting a variety in the magnitude of the step lengths can greatly improve the search efficiency. However, the precise connection between the search efficiency and the number of step lengths in the repertoire of the searcher has not been identified. Motivated by biological examples in one-dimensional terrains, a recent paper studied the best cover time on an n-node cycle that can be achieved by a random walk process that uses k step lengths [7]. By tuning the lengths and corresponding probabilities the authors therein showed that the best cover time is roughly n(1+circle minus(1/k)). While this bound is useful for large values of k, it is hardly informative for small k values, which are of interest in biology [2, 4, 25, 30]. In this paper, we provide a tight bound for the cover time of such a walk, for every integer k > 1. Specifically, up to lower order polylogarithmic factors, the cover time is n(1+ 1/2k-1). For k = 2, 3, 4 and 5 the bound is thus n(4/3), n(6/5), n(8/7), and n(10/9), respectively. Informally, our result implies that, as long as the number of step lengths k is not too large, incorporating an additional step length to the repertoire of the process enables to improve the cover time by a polynomial factor, but the extent of the improvement gradually decreases with k.

关键词： Computational Biology randomness in computing Search Algorithms Random Walks Levy Flights Intermittent Search CCRW

来源：评论

学校读者我要写书评

暂无评论

Extracting randomness from Samplable Distributions, Revisited 64

Extracting Randomness from Samplable Distributions, Revisite...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Ball, Marshall Goldin, Eli Dachman-Soled, Dana Mutreja, Saachi NYU New York NY 10003 USA Univ Maryland College Pk MD USA Columbia Univ New York NY USA

ISBN: (纸本)9798350318944

randomness extractors provide a generic way of converting sources of randomness that are merely unpredictable into almost uniformly random bits. While in general, deterministic randomness extraction is impossible, it is possible if the source has some structural constraints. While much of the literature on deterministic extraction has focused on sources with strong independence properties, a natural class where deterministic extraction is possible is sources that can sampled by a polynomial size circuit, Levin [SIAM J Comp'86]. Trevisan and Vadhan [FOCS'00] explicitly constructed deterministic randomness extractors for this class of sources, assuming very strong circuit lower bounds. We suggest that there is perhaps an even more reasonable model of natural sources of randomness than Levin's: sources sampled by polynomial size quantum circuits. Under a suitable circuit lower bound, we show that Trevisan and Vadhan's extractor indeed works for this class. Along the way, we substantially improve their analysis in the classical case, showing that a circuit lower bound against NP-circuits suffice in the classical case (as opposed to a lower bounds on Sigma(5)-circuits, as shown by Trevisan and Vadhan). Moreover, we show that under this assumption, it is possible to handle sources sampled by postselecting circuits (a variant of nondeterministic circuits). We show that this model is sufficient to capture randomness extraction in the presence of efficiently computable leakage.

关键词： average-case complexity quantum computing randomness in computing

来源：评论

学校读者我要写书评

暂无评论

Expander Random Walks: A Fourier-Analytic Approach 2021

Expander Random Walks: A Fourier-Analytic Approach

引用

53rd Annual ACM SIGACT Symposium on Theory of computing (STOC)

作者： Cohen, Gil Peri, Noam Ta-Shma, Amnon Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9781450380539

In this work we ask the following basic question: assume the vertices of an expander graph are labelled by 0, 1. What "test" functions f : {0, 1}(t) -> {0, 1} cannot distinguish t independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and Szemeredi (STOC 1987) is captured by the AND test function, whereas the fundamental expander Chernoff bound due to Gillman (SICOMP 1998), Heally (Computational Complexity 2008) is about test functions indicating whether the weight is close to the mean. In fact, it is known that all threshold functions are fooled by a random walk (Kipnis and Varadhan, Communications in Mathematical Physics 1986). Recently, it was shown that even the highly sensitive PARITY function is fooled by a random walk Ta-Shma (STOC 2017). We focus on balanced labels. Our first main result is proving that all symmetric functions are fooled by a random walk. Put differently, we prove a central limit theorem (CLT) for expander random walks with respect to the total variation distance, significantly strengthening the classic CLT for Markov Chains that is established with respect to the Kolmogorov distance (Kipnis and Varadhan, Communications in Mathematical Physics 1986). Our approach significantly deviates from prior works. We first study how well a Fourier character xs is fooled by a random walk as a function of S. Then, given a test function f, we expand f in the Fourier basis and combine the above with known results on the Fourier spectrum of f. We also proceed further and consider general test functions not necessarily symmetric. As our approach is Fourier analytic, it is general enough to analyze such versatile test functions. For our second result, we prove that random walks on sufficiently good expander graphs fool tests functions computed by AC(0) circuits, read-once branching programs, and functions with bounded query complexity.

关键词： Combinatorics and graph theory Computational complexity randomness in computing

来源：评论

学校读者我要写书评

暂无评论

Efficient Recovery Algorithms with Restricted Access to Strings

Efficient Recovery Algorithms with Restricted Access to Stri...

引用

作者： Sinha, Sandip Columbia University

学位级别：Ph.D., Doctor of Philosophy

We design efficient algorithms for computational problems over strings in several models where the algorithms have limited access to the input. These models, and algorithms developed respecting these constraints, are becoming increasingly relevant due to the rapidly increasing size of datasets in myriad applications. Our first problem of interest is trace reconstruction. This is an important problem in learning theory and coding theory, and has applications in computational biology. In this problem, the goal is to recover an unknown string given independent samples (traces) of it generated via a probabilistic noise process called the deletion channel. We give state-of-the-art algorithms for this problem in several settings. Then we consider the problem of estimating the longest increasing subsequence (LIS) of a given string in sublinear time, given query access to the string. While the LIS of a string can be computed exactly in near-linear time, the optimal complexity of approximating the LIS length, especially when the LIS is much less than the string length, is still open. We significantly improve upon prior work in terms of both approximation and time complexity in this regime. The runtime of our algorithm essentially matches the trivial query complexity lower bound as a function of the length of the LIS. Finally, we consider the problem of local decoding, or random access, on compressed strings. The Burrows-Wheeler Transform (BWT) is an important preprocessing step in lossless text compression that rearranges a string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings. However, the decoding process of the BWT is inherently sequential, and prevents fast random access to the original string. We design a succinct data structure for locally decoding short substrings (and answering several other queries) of a given string under its compressed BWT efficiently.

关键词： Information theory randomness in computing Smoothed analysis Sublinear algorithms Succinct data structures Trace reconstruction

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

全选清除本页清除全部题录导出标记到“检索档案”

共1页 << < 1 > >>

检索报告对象比较合并检索0

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

电话和邮箱必须正确填写，我们会与您联系确认。

联系人：

所在院系：

联系邮箱：

联系电话：

内蒙古自治区呼和浩特市赛罕区大学西街235号邮编: 010021

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：