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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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

分类表

所选分类

>> <<

限定检索结果

文献类型

64 篇 期刊文献
49 篇 会议
1 篇 学位论文

馆藏范围

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

日期分布

学科分类号

88 篇 工学
- 85 篇 计算机科学与技术...
- 9 篇 软件工程
- 3 篇 电气工程
- 2 篇 电子科学与技术（可...
- 1 篇 力学（可授工学、理...
73 篇 理学
- 72 篇 数学
- 4 篇 统计学（可授理学、...
- 2 篇 物理学
3 篇 管理学
- 3 篇 管理科学与工程(可...
1 篇 教育学
- 1 篇 教育学

主题

114 篇 average-case com...
9 篇 hardness amplifi...
6 篇 circuit complexi...
5 篇 time-bounded kol...
5 篇 kolmogorov compl...
5 篇 pseudorandomness
5 篇 minimum circuit ...
4 篇 analysis of algo...
4 篇 derandomization
3 篇 computational co...
3 篇 random graphs
3 篇 pseudorandom gen...
3 篇 sum-of-squares l...
3 篇 algorithms
3 篇 tree networks
3 篇 circuit lower bo...
3 篇 oracles
3 篇 meta-complexity
3 篇 monotone circuit...
3 篇 path coloring

机构

10 篇 natl inst inform...
6 篇 tokyo inst techn...
4 篇 mit cambridge ma...
4 篇 univ calif berke...
3 篇 univ versailles ...
3 篇 univ oxford dept...
2 篇 cuny city coll d...
2 篇 univ chicago il ...
2 篇 univ oxford oxfo...
2 篇 harvard univ div...
2 篇 lomonosov moscow...
2 篇 mit csail 77 mas...
2 篇 univ caen greyc ...
2 篇 columbia univ de...
2 篇 univ nacl gen sa...
2 篇 harvard univ sch...
2 篇 univ nacl gen sa...
2 篇 tsinghua univ pe...
2 篇 columbia univ ny...
2 篇 univ paris 11 lr...

作者

12 篇 hirahara shuichi
4 篇 bresler guy
4 篇 perez mariana
4 篇 privitelli melin...
4 篇 rossman benjamin
4 篇 santhanam rahul
4 篇 matera guillermo
3 篇 shaltiel ronen
3 篇 ren hanlin
3 篇 gardy d
3 篇 shimizu nobutaka
3 篇 valencia-pabon m
3 篇 barth d
3 篇 denise a
3 篇 corteel s
3 篇 drucker andrew
3 篇 nanashima mikito
3 篇 trevisan luca
2 篇 chen lijie
2 篇 ritter k

语言

112 篇 英文
1 篇 其他

检索条件"主题词=Average-case complexity"

共 114 条记录，以下是91-100 订阅

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

详细简洁

排序：

Graph Colouring Is Hard on average for Polynomial Calculus and Nullstellensatz 64

Graph Colouring Is Hard on Average for Polynomial Calculus a...

引用

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

作者： Conneryd, Jonas de Rezende, Susanna F. Nordstrom, Jakob Pang, Shuo Risse, Kilian Lund Univ Lund Sweden Univ Copenhagen Copenhagen Denmark Ecole Polytech Fed Lausanne Lausanne Switzerland

ISBN: (纸本)9798350318944

We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erdos-Renyi random graphs, are 3-colourable. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on proof size.

关键词： average-case complexity polynomial calculus Proof complexity

来源：评论

学校读者我要写书评

暂无评论

On Worst-case Learning in Relativized Heuristica 62

On Worst-Case Learning in Relativized Heuristica

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Hirahara, Shuichi Nanashima, Mikito Natl Inst Informat Tokyo Japan Tokyo Inst Technol Tokyo Japan

ISBN: (纸本)9781665420556

A PAC learning model involves two worst-case requirements: a learner must learn all functions in a class on all example distributions. However, basing the hardness of learning on NP-hardness has remained a key challenge for decades. In fact, recent progress in computational complexity suggests the possibility that a weaker assumption might be sufficient for worst-case learning than the feasibility of worst-case algorithms for NP problems. In this study, we investigate whether these worst-case requirements for learning are satisfied on the basis of only average-case assumptions in order to understand the nature of learning. First, we construct a strong worst-case learner based on the assumption that DistNP subset of AvgP, i.e., in Heuristica. Our learner agnostically learns all polynomial-size circuits on all unknown P/poly-samplable distributions in polynomial time, where the complexity of learning depends on the complexity of sampling examples. Second, we study the limitation of relativizing constructions of learners based on average-case heuristic algorithms. Specifically, we construct a powerful oracle such that DistPH subset of AvgP, i.e., every problem in PH is easy on average, whereas UP boolean AND coUP and PAC learning on almost-uniform distributions are hard even for 2(n/omega(log n))-time algorithms in the relativized world, which improves the oracle separation presented by Impagliazzo (CCC 2011). The core concept of our improvements is the consideration of a switching lemma on a large alphabet, which may be of independent interest. The lower bound on the time complexity is nearly optimal because Hirahara (STOC 2021) showed that DistPH subset of AvgP implies that PH can be solved in time 2(O(n/log n)) under any relativized world. The full version of this paper is available on ECCC [1].

关键词： oracle separation learning average-case complexity switching lemma

来源：评论

学校读者我要写书评

暂无评论

average-case Fine-Grained Hardness 2017

Average-Case Fine-Grained Hardness

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Ball, Marshall Rosen, Alon Sabin, Manuel Vasudevan, Prashant Nalini Columbia Univ New York NY 10027 USA IDC Efi Arazi Sch Comp Sci Herzliyya Israel Univ Calif Berkeley Berkeley CA USA MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781450345286

We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., IPL '94), but these have been canonical functions that have not found further use, while our functions are closely related to well-studied problems and have considerable algebraic structure. Based on the average-case hardness and structural properties of our functions, we outline the construction of a Proof of Work scheme and discuss possible approaches to constructing fine-grained One-Way Functions. We also show how our reductions make conjectures regarding the worst-case hardness of the problems we reduce from (and consequently the Strong Exponential Time Hypothesis) heuristically falsi fiable in a sense similar to that of (Naor, CRYPTO '03). We prove our hardness results in each case by showing fine grained reductions from solving one of three problems - namely, Orthogonal Vectors (OV), 3SUM, and All-Pairs Shortest Paths (APSP) in the worst case to computing our function correctly on a uniformly random input. The conjectured hardness of OV and 3SUM then gives us functions that require n(-0(1)) time to compute on average, and that of APSP gives us a function that requires n(3-0)(1) time. Using the same techniques we also obtain a conditional average-case time hierarchy of functions.

关键词： average-case complexity Fine-Grained complexity Cryptography Heuristic Falsifiability Proofs of Work Worst-case to average-case Reduction

来源：评论

学校读者我要写书评

暂无评论

Relativized Separations of Worst-case and average-case Complexities for NP

Relativized Separations of Worst-Case and Average-Case Compl...

引用

26th Annual IEEE Conference on Computational complexity (CCC)

作者： Impagliazzo, Russell Univ Calif San Diego San Diego CA USA

ISBN: (纸本)9780769544113

Non-relativization of complexity issues can be interpreted as showing that these issues cannot be resolved by "black-box" techniques. We show that the assumption DistNP subset of AvgP does not imply that NP subset of BPP by relativizing techniques. More precisely, we give an oracle relative to which the assumption holds but the conclusion fails. Moreover, relative to our oracle, there are problems in NP boolean AND Co - NP that require exponential circuit complexity. We also give an alternate version where DistNP subset of AvgP is true, but a problem in the second level of the polynomial hierarchy is hard on the uniform distribution.

关键词： P vs. NP average-case complexity oracles relativization heuristica

来源：评论

学校读者我要写书评

暂无评论

Learning in Pessiland via Inductive Inference 64

Learning in Pessiland via Inductive Inference

引用

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

作者： Hirahara, Shuichi Nanashima, Mikito Natl Inst Informat Tokyo Japan Tokyo Inst Technol Tokyo Japan

ISBN: (纸本)9798350318944

Pessiland is one of Impagliazzo's five possible worlds in which NP is hard on average, yet no one-way function exists. This world is considered the most pessimistic because it offers neither algorithmic nor cryptographic benefits. In this paper, we develop a unified framework for constructing strong learning algorithms under the non-existence of a one-way function, indicating a positive aspect of Pessiland. Using our framework, we improve the learning algorithm for adaptively changing distributions, which was introduced by Naor and Rothblum (ICML'06). Although the previous learner assumes the knowledge of underlying distributions, our learner is universal, i.e., does not assume any knowledge on distributions, and has better sample complexity. We also employ our framework to construct a strong agnostic learner with optimal sample complexity, which improves the previous PAC learner of Blum, Furst, Kearns, and Lipton (Crypto'93). Our learning algorithms are worst-case algorithms that run in exponential time with respect to computational depth, and as a by-product, we present the first characterization of the existence of a one-way function by the worst-case hardness of some promise problem in AM. As a corollary of our results, we establish the robustness of average-case learning, that is, the equivalence among various average-case learning tasks, such as (strong and weak) agnostic learning, learning adaptively changing distributions with respect to arbitrary unknown distributions, and weak learning with membership queries with respect to the uniform distribution. Our framework is based on the theory of Solomonoff's inductive inference and the universal extrapolation algorithm of Impagliazzo and Levin (FOCS'90). Conceptually, the framework demonstrates that Pessiland is, in fact, a wonderland for machine learning in which various learning tasks can be efficiently solved by the generic algorithm of universal extrapolation.

关键词： learning cryptography average-case complexity one-way function inductive inference

来源：评论

学校读者我要写书评

暂无评论

Hardness Self-Amplification from Feasible Hard-Core Sets 63

Hardness Self-Amplification from Feasible Hard-Core Sets

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Hirahara, Shuichi Shimizu, Nobutaka Natl Inst Informat Tokyo Japan Tokyo Inst Technol Tokyo Japan

ISBN: (纸本)9781665455190

We consider the question of hardness self-amplification: Given a Boolean function f that is hard to compute on an o(1)-fraction of inputs drawn from some distribution, can we prove that f is hard to compute on a ( 1/2 - o(1))-fraction of inputs drawn from the same distribution? We prove hardness self-amplification results for natural distributional problems studied in fine-grained average-case complexity, such as the problem of counting the number of the triangles modulo 2 in a random tripartite graph and the online vector-matrix-vector multiplication problem over F-2. More generally, we show that any problem that can be decomposed into "computationally disjoint" subsets of inputs admits hardness self-amplification. This is proved by generalizing the security proof of the Nisan-Wigderson pseudorandom generator, in which case nearly disjoint subsets of inputs are considered. At the core of our proof techniques is a new notion of feasible hard-core set, which generalizes Impagliazzo's hard-core set [Impagliazzo, FOCS'95]. We show that any weak average-case hard function f has a feasible hard-core set H: any small H-oracle circuit (that is allowed to make queries q to H if f(q) can be computed without the oracle) fails to compute f on a ( 1/2 - o(1))-fraction of inputs in H.

关键词： average-case complexity Hardness Amplification Hardcore Lemma

来源：评论

学校读者我要写书评

暂无评论

Approximating the Permanent of a Random Matrix with Vanishing Mean 59

Approximating the Permanent of a Random Matrix with Vanishin...

引用

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

作者： Eldar, Lior Mehraban, Saeed MIT EECS 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781538642306

The permanent is #P-hard to compute exactly on average for natural random matrices including matrices over finite fields or Gaussian ensembles. Should we expect that it remains #P-hard to compute on average if we only care about approximation instead of exact computation? In this work we take a first step towards resolving this question: We present a quasi-polynomial time deterministic algorithm for approximating the permanent of a typical n x n random matrix with unit variance and vanishing mean mu = O(ln ln n)(-1/8) to within inverse polynomial multiplicative error. (alternatively, one can achieve permanent approximation for matrices with mean mu = 1/polylog(n) in time 2(n epsilon), for arbitrarily small epsilon > 0). The proposed algorithm significantly extends the regime of matrices for which efficient approximation of the permanent is known. This is because unlike previous algorithms which require a stringent correlation between the signs of the entries of the matrix [1], [2] it can tolerate random ensembles in which this correlation is negligible (albeit non-zero). Among important special cases we note: 1) Biased Gaussian: each entry is a complex Gaussian with unit variance 1 and mean mu. 2) Biased Bernoulli: each entry is -1 + mu with probability 1/2, and 1 with probability 1/2. These results counter the common intuition that the difficulty of computing the permanent, even approximately, stems merely from our inability to treat matrices with many opposing signs. The Gaussian ensemble approaches the threshold of a conjectured hardness [3] of computing the permanent of a zero mean Gaussian matrix. This conjecture is one of the baseline assumptions of the BosonSampling paradigm that has received vast attention in recent years in the context of quantum supremacy experiments. We furthermore show that the permanent of the biased Gaussian ensemble is #P-hard to compute exactly on average. To our knowledge, this is the first natural example of a counting problem that

关键词： permanent approximation algorithm average-case complexity Boson Sampling anti-concentration complex analysis

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique 36

Detection-Recovery and Detection-Refutation Gaps via Reducti...

引用

36th Annual Conference on Learning Theory (COLT)

作者： Bresler, Guy Jiang, Tianze 77 Massachusetts Ave Cambridge MA 02139 USA

Planted Dense Subgraph (PDS) problem is a prototypical problem with a computational-statistical gap. It also exhibits an intriguing additional phenomenon: different tasks, such as detection or recovery, appear to have different computational limits. A detection-recovery gap for PDS was substantiated in the form of a precise conjecture given by Chen and Xu (2014) (based on the parameter values for which a convexified MLE succeeds), and then shown to hold for low-degree polynomial algorithms by Schramm and Wein (2022) and for MCMC algorithms for Ben Arous et al. (2020). In this paper we demonstrate that a slight variation of the Planted Clique Hypothesis with secret leakage (introduced in Brennan and Bresler (2020)), implies a detection-recovery gap for PDS. In the same vein, we also obtain a sharp lower bound for refutation, yielding a detection-refutation gap. Our methods build on the framework of Brennan and Bresler (2020) to construct average-case reductions mapping secret leakage Planted Clique to appropriate target problems.

关键词： average-case complexity Planted Clique Algorithmic Hardness

来源：评论

学校读者我要写书评

暂无评论

The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials 62

The Algorithmic Phase Transition of Random k-SAT for Low Deg...

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Bresler, Guy Huang, Brice MIT Dept Elect Engn & Comp Sci 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781665420556

Let Phi be a uniformly random k-SAT formula with n variables and m clauses. We study the algorithmic task of finding a satisfying assignment of Phi. It is known that satisfying assignments exist with high probability up to clause density m/n = 2(k) log 2 - 1/2(log 2 + 1) + o(k)(1), while the best polynomial-time algorithm known, the Fix algorithm of Coja-Oghlan [1], finds a satisfying assignment at the much lower clause density (1 - o(k)(1))2(k) log k/k. This prompts the question: is it possible to efficiently find a satisfying assignment at higher clause densities? We prove that the class of low degree polynomial algorithms cannot find a satisfying assignment at clause density (1 + o(k)(1))kappa*2(k) log k/k for a universal constant kappa* approximate to 4.911. This class encompasses Fix, message passing algorithms including Belief and Survey Propagation guided decimation (with bounded or mildly growing number of rounds), and local algorithms on the factor graph. This is the first hardness result for any class of algorithms at clause density within a constant factor of that achieved by Fix. Our proof establishes and leverages a new many-way overlap gap property tailored to random k-SAT.

关键词： random k-SAT average-case complexity algorithmic phase transition low degree polynomial hardness overlap gap property

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共12页 << < 3 4 5 6 7 8 9 10 11 12 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：