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

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Rossman, Benjamin Tokyo Inst Technol Meguro Ku Tokyo 1528550 Japan

ISBN: (纸本)9781424485253

We present lower and upper bounds showing that the average-case complexity of the k-Clique problem on monotone circuits is n(k/4+O(1)). Similar bounds for AC(0) circuits were shown in Rossman [Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 721-730] and Amano [Comput. complexity, 19 (2010), pp. 183-210].

关键词： clique monotone circuits average-case complexity quasi-sunflowers

来源：评论

学校读者我要写书评

暂无评论

IMPROVED DIRECT PRODUCT THEOREMS FOR RANDOMIZED QUERY complexity

IMPROVED DIRECT PRODUCT THEOREMS FOR RANDOMIZED QUERY COMPLE...

引用

26th Annual IEEE Conference on Computational complexity (CCC)

作者： Drucker, Andrew MIT Cambridge MA 02139 USA

ISBN: (纸本)9781457701795

The "direct product problem" is a fundamental question in complexity theory which seeks to understand how the difficulty in computing a function on each of k independent inputs scales with k. We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1-epsilon in computing the Boolean function f on input distribution mu, then for alpha <= 1, every alpha epsilon Tk-query algorithm has success probability at most (2(alpha epsilon)(1-epsilon))(k) in computing the k-fold direct product f(circle times k) correctly on k independent inputs from mu. In light of examples due to Shaltiel, this statement gives an essentially optimal trade-off between the query bound and the error probability. Using this DPT, we show that for an absolute constant alpha > 0, the worst-case success probability of any alpha R-2(f) k-query randomized algorithm for f(circle dot k) falls exponentially with k. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k). Our proof technique involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve f(circle times k). Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.

关键词： Direct product theorems query complexity decision trees average-case complexity hardness amplification

来源：评论

学校读者我要写书评

暂无评论

On the AC⁰ complexity of Subgraph Isomorphism 55

On the AC<SUP>0</SUP> Complexity of Subgraph Isomorphism

引用

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

作者： Li, Yuan Razborov, Alexander Rossman, Benjamin Univ Chicago Chicago IL 60637 USA Natl Inst Informat Tokyo Japan

ISBN: (纸本)9781479965175

Let P be a fixed graph (hereafter called a "pattern"), and let SUBGRAPH(P) denote the problem of deciding whether a given graph G contains a subgraph isomorphic to P. We are interested in AC(0)-complexity of this problem, determined by the smallest possible exponent C(P) for which SUBGRAPH(P) possesses bounded-depth circuits of size n(C(P)+o(1)). Motivated by the previous research in the area, we also consider its "colorful" version SUBGRAPH(col)(P) in which the target graph G is V (P)-colored, and the average-case version SUBGRAPH(ave)(P) under the distribution G(n, n(-theta(P))), where theta(P) is the threshold exponent of P. Defining C-col(P) and C-ave(P) analogously to C(P), our main contributions can be summarized as follows. C-col(P) coincides with the tree-width of the pattern P within a logarithmic factor. This shows that the previously known upper bound by Alon, Yuster, Zwick [3] is almost tight. We give a characterization of C-ave(P) in purely combinatorial terms within a multiplicative factor of 2. This shows that the lower bound technique of Rossman [21] is essentially tight, for any pattern P whatsoever. We prove that if Q is a minor of P then SUBGRAPH(col)(Q) is reducible to SUBGRAPH(col)(P) via a linear-size monotone projection. At the same time, we show that there is no monotone projection whatsoever that reduces SUBGRAPH(M-3) to SUBGRAPH(P-3 + M-2) (P-3 is a path on 3 vertices, M-k is a matching with k edges, and "+" stands for the disjoint union). This result strongly suggests that the colorful version of the subgraph isomorphism problem is much better structured and well-behaved than the standard (worst-case, uncolored) one.

关键词： complexity theory Computer science Context Educational institutions Integrated circuit modeling Standards Upper bound AC0 average-case complexity subgraph isomorphism treewidth integrated circuit modelling complexity theory Educational institutions Upper bound computer science Phosphorus isomorphism

来源：评论

学校读者我要写书评

暂无评论

On worst-case to average-case reductions for NP problems

引用

SIAM JOURNAL ON COMPUTING 2006年第4期36卷 1119-1159页

作者： Bogdanov, Andrej Trevisan, Luca Inst Adv Study Princeton NJ 08540 USA Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA

We show that if an NP-complete problem has a nonadaptive self-corrector with respect to any samplable distribution, then coNP is contained in NP/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow [SIAM J. Comput., 22 ( 1993), pp. 994 - 1005] show the same conclusion under the stronger assumption that an NP-complete problem has a nonadaptive random self-reduction. A self-corrector for a language L with respect to a distribution D is a worst-case to average-case reduction that transforms any given algorithm that correctly decides L on most inputs ( with respect to D) into an algorithm of comparable efficiency that decides L correctly on every input. A random self-reduction is a special case of a self-corrector, where the reduction, given an input x, is restricted to only making oracle queries that are distributed according to D. The result of Feigenbaum and Fortnow depends essentially on the property that the distribution of each query in a random self-reduction is independent of the input of the reduction. Our result implies that the average-case hardness of a problem in NP or the security of a one-way function cannot be based on the worst-case complexity of an NP-complete problem via nonadaptive reductions ( unless the polynomial hierarchy collapses).

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

来源：评论

学校读者我要写书评

暂无评论

A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2000年第1-2期17卷 69-96页

作者： Lemaire, C Moreau, JM ENSMSE LISSE St Etienne France CEA Bruyeres Le Chatel France

This paper exploits the notion of "unfinished site", introduced by Katajainen and Koppinen (1998) in the analysis of a two-dimensional Delaunay triangulation algorithm, based on a regular grid. We generalize the notion and its properties to any dimension k greater than or equal to 2: in the case of uniform distributions, the expected number of unfinished sites in a k-rectangle is O(N1-1/k). This implies, under some specific assumptions, the linearity of a class of divide-and-conquer schemes based on balanced k-d trees. This general result is then applied to the analysis of a new algorithm for constructing Delaunay triangulations in the plane. According to Su and Drysdale (1995, 1997), the best known algorithms for this problem run in linear expected time, thanks in particular to the use of bucketing techniques to partition the domain. In our algorithm, the partitioning is based on a 2-d tree instead, the construction of which takes Theta (N log N) time, and we show that the rest of the algorithm runs in linear expected time. This "preprocessing" allows the algorithm to adapt efficiently to irregular distributions, as the domain is partitioned using point coordinates, as opposed to a fixed, regular basis (buckets or grid). We checked that even for the largest data sets that could fit in internal memory lover 10 million points), constructing the 2-d tree takes noticeably less CPU time than triangulating the data. With this in mind, our algorithm is only slightly slower than the reputedly best algorithms on uniform distributions, and is even the most efficient for data sets of up to several millions of points distributed in clusters, (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： Delaunay triangulation k-d tree worst-case complexity average-case complexity multi-dimensional divide-and-conquer

来源：评论

学校读者我要写书评

暂无评论

Quantum Pattern Matching Fast on average

引用

ALGORITHMICA 2017年第1期77卷 16-39页

作者： Montanaro, Ashley Univ Bristol Dept Comp Sci Bristol Avon England

The d-dimensional pattern matching problem is to find an occurrence of a pattern of length m x ... x m within a text of length n x ... x n, with n >= m. This task models various problems in text and image processing, among other application areas. This work describes a quantum algorithm which solves the pattern matching problem for random patterns and texts in time (O) over tilde((n/m)(d/2)2(O)(d(3/2) root log m)). For large m this is super-polynomially faster than the best possible classical algorithm, which requires time (Omega) over tilde (n(d/2) + (n/m)(d)). The algorithm is based on the use of a quantum subroutine for finding hidden shifts in d dimensions, which is a variant of algorithms proposed by Kuperberg.

关键词： Quantum algorithms Quantum query complexity Pattern matching average-case complexity

来源：评论

学校读者我要写书评

暂无评论

A FASTER DIVIDE-AND-CONQUER ALGORITHM FOR CONSTRUCTING DELAUNAY TRIANGULATIONS

引用

ALGORITHMICA 1987年第2期2卷 137-151页

作者： DWYER, RA 1. Carnegie-Mellon University Pittsburgh Pennsylvania USA

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its Θ(n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn≤2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1p≤∞.

关键词： Delaunay triangulation Voronoi diagram L p metric Computational geometry average-case complexity Analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

引用

ALGORITHMICA 2023年第7期85卷 2131-2155页

作者： Cavalar, Bruno P. Lu, Zhenjian Univ Warwick Dept Comp Sci Coventry W Midlands England Univ Oxford Dept Comp Sci Oxford England

In this paper, we initiate the study of average-case complexity and circuit analysis algorithms for comparator circuits. Departing from previous approaches, we exploit the technique of shrinkage under random restrictions to obtain a variety of new results for this model. Among them, we show center dot average-case Lower Bounds For every k = k(n) with k >= log n, there exists a polynomial-time computable function fk on n bits such that, for every comparator circuit C with at most n(1.5)/O (k center dot root log n) gates, we have Pr (x is an element of{0,1}n) [C(x) = fk (x)] <= 1/2 + 1/2(Omega(k)). This average-case lower bound matches the worst-case lower bound of Gal and Robere by letting k = O(log n). center dot # SAT Algorithms There is an algorithm that counts the number of satisfying assignments of a given comparator circuit with at most n(1.5)/O (k center dot root log n) gates, in time 2(n-k) center dot poly(n), for any k <= n/4. The running time is non-trivial (i.e., 2(n)/n(omega(1))) when k =omega(log n). center dot Pseudorandom Generators and MCSP Lower Bounds There is a pseudorandom generator of seed length s(2/3+o(1)) that fools comparator circuits with s gates. Also, using this PRG, we obtain an n(1.5-o(1)) lower bound for MCSP against comparator circuits.

关键词： Comparator circuits average-case complexity Satisfiability algorithms Pseudorandom generators

来源：评论

学校读者我要写书评

暂无评论

Space-efficient routing tables for almost all networks and the incompressibility method

引用

SIAM JOURNAL ON COMPUTING 1999年第4期28卷 1414-1432页

作者： Buhrman, H Hoepman, JH Vitányi, P Ctr Wiskunde & Informat NL-1098 SJ Amsterdam Netherlands Univ Twente Dept Comp Sci NL-7500 AE Enschede Netherlands

We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network topologies. In most models for routing, for almost all labeled graphs, Theta(n(2)) bits are necessary and sufficient for shortest path routing. By "almost all graphs" we mean the Kolmogorov random graphs which constitute a fraction of 1 ? 1/n(c) of all graphs on n nodes, where c > 0 is an arbitrary fixed constant. There is a model for which the average case lower bound rises to Omega(n(2) log n) and another model where the average case upper bound drops to O(n log(2) n). This clearly exposes the sensitivity of such bounds to the model under consideration. If paths have to be short, but need not be shortest (if the stretch factor may be larger than 1), then much less space is needed on average, even in the more demanding models. Full-information routing requires Theta(n(3)) bits on average. For worst-case static networks we prove an Omega(n(2) log n) lower bound for shortest path routing and all stretch factors < 2 in some networks where free relabeling is not allowed.

关键词： computer networks routing algorithms compact routing tables Kolmogorov complexity incompressibility method random graphs average-case complexity space complexity

来源：评论

学校读者我要写书评

暂无评论

FUNCTION COMPOSITION AND AUTOMATIC average-case ANALYSIS

引用

DISCRETE MATHEMATICS 1995年第1-3期139卷 443-453页

作者： ZIMMERMANN, P Domaine de Voluceau B.P. 105 78153 Le Chesnay cedex France

We define the composition of functions defined over extended context-free languages. We show that this composition is automatically computable. It enables the automatic analysis of complex problems with small input de... 详细信息

关键词： AUTOMATIC ANALYSIS OF ALGORITHMS average-case complexity PROGRAM TRANSFORMATION

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：