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

15th Latin American Symposium on Theoretical Informatics

作者： Mattes, Caroline Weiss, Armin Univ Stuttgart Inst Formale Methoden Informat Stuttgart Germany

ISBN: (纸本)9783031206238;9783031206245

The Baumslag group had been a candidate for a group with an extremely difficult word problem until Myasnikov, Ushakov, and Won succeeded to show that its word problem can be solved in polynomial time. Their result used the newly developed data structure of power circuits allowing for a non-elementary compression of integers. Later this was extended in two directions: Laun showed that the same applies to generalized Baumslag groups G(1, q) for q >= 2 and we established that the word problem of the Baumslag group G(1,2) can be solved in TC2. In this work we further improve upon both previous results by showing that the word problems of all the generalized Baumslag groups G(1, q) can be solved in TC1 - even for negative q. Our result is based on using refined operations on reduced power circuits. Moreover, we prove that the conjugacy problem in G(1, q) is strongly generically in TC1 (meaning that for "most" inputs it is in TC1). Finally, for every fixed g is an element of G(1, q) conjugacy to g can be decided in TC1 for all inputs.

关键词： Algorithmic group theory Power circuit TC1 Word problem Conjugacy problem Baumslag group parallel complexity

来源：评论

学校读者我要写书评

暂无评论

Bipartite Perfect Matching Is in Quasi-NC 16

Bipartite Perfect Matching Is in Quasi-NC

引用

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

作者： Fenner, Stephen Gurjar, Rohit Thierauf, Thomas Univ South Carolina Columbia SC 29208 USA Aalen Univ Aalen Germany

ISBN: (纸本)9781450341325

We show that the bipartite perfect matching problem is in quasi-NC2. That is, it has uniform circuits of quasi polynomial size n(O(log n)) and O(log(2) n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

关键词： Graph Matching parallel complexity Derandomization quasi-NC

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for Monotone Switching Networks via Fourier Analysis 12

Tight Bounds for Monotone Switching Networks via Fourier Ana...

引用

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

作者： Chan, Siu Man Potechin, Aaron Univ Calif Berkeley Berkeley CA 94720 USA MIT Cambridge MA USA

ISBN: (纸本)9781450312455

We prove tight size bounds on monotone switching networks for the k-clique problem, and for an explicit monotone problem by analyzing the generation problem with a pyramid structure of height h. This gives alternative proofs of the separations of m-NC from m-P and of m-NCi from m-NCi+1, different from Raz-McKenzie (Combinatorica '99). The enumerative-combinatorial and Fourier analytic techniques in this work are very different from a large body of work on circuit depth lower bounds, and may be of independent interest.

关键词： Lower bounds space complexity parallel complexity monotone complexity switching networks

来源：评论

学校读者我要写书评

暂无评论

ALOGTIME and a conjecture of S.A. Cook

引用

Annals of Mathematics and Artificial Intelligence 1992年第1-3期6卷 57-106页

作者： Clote, Peter Department of Computer Science Boston College Chestnut Hill 02167 MA United States

Using sequential, machine-independent characterization of the parallel complexity classes ACk and NCk, we establish the following conjecture of S.A. Cook. There is a free variable equational logic ALV with the propert... 详细信息

Using sequential, machine-independent characterization of the parallel complexity classes AC^k and NC^k, we establish the following conjecture of S.A. Cook. There is a free variable equational logic ALV with the property that if f, g are function symbols for ALOGTIME computable functions for which "f=g" is provable in ALV, then there are polynomial size Frege proofs for the infinite family {|f=g|_mⁿ:n, m∈ℕ} of propositional tautologies. Here, the propositional formula |f=g|_mⁿ expresses the equality of f and g on inputs of length at most n, provided that the function values are of length at most m. We establish a related result with constant formula-depth polynomial size Frege proofs for a system AV related to uniform AC⁰ functions. © 1992 J.C. Baltzer A.G. Scientific Publishing Company.

关键词： Frege proofs NC, free variable equational logic parallel complexity propositional calculus resolution proof

来源：评论

学校读者我要写书评

暂无评论

Improved Lower Bounds for Submodular Function Minimization 63

Improved Lower Bounds for Submodular Function Minimization

引用

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

作者： Chakrabarty, Deeparnab Graur, Andrei Jiang, Haotian Sidford, Aaron Dartmouth Coll Dept Comp Sci Hanover NH 03755 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA Univ Washington Paul G Allen Sch Comp Sci & Engn Seattle WA 98195 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA

ISBN: (纸本)9781665455190

We provide a generic technique for constructing families of submodular functions to obtain lower bounds for submodular function minimization (SFM). Applying this technique, we prove that any deterministic SFM algorithm on a ground set of n elements requires at least Omega(n log n) queries to an evaluation oracle. This is the first super-linear query complexity lower bound for SFM and improves upon the previous best lower bound of 2n given by [Graur et al., ITCS 2020]. Using our construction, we also prove that any (possibly randomized) parallel SFM algorithm, which can make up to poly(n) queries per round, requires at least Omega(n/ log n) rounds to minimize a submodular function. This improves upon the previous best lower bound of (Omega) over tilde (n(1/3)) rounds due to [Chakrabarty et al., FOCS 2021], and settles the parallel complexity of query-efficient SFM up to logarithmic factors due to a recent advance in [Jiang, SODA 2021]. Index

关键词： submodular function minimization lower bound query complexity parallel complexity

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for m-out-of-n threshold voting

Parallel algorithms for m-out-of-n threshold voting

引用

1996 IEEE 2nd International Conference on Algorithms and Architectures for parallel Processing (ICA3PP 96)

作者： Parhami, B Univ of California Santa Barbara United States

ISBN: (纸本)0780335295

Voting on large collections of input objects is becoming increasingly important in data fusion, signal and image processing, and distributed computing. To achieve high speed in voting, the multiple processing resources typically available in such applications should be utilized;hence the need for parallel voting algorithms. We develop efficient parallel algorithms for threshold voting which generalize and extend previous work on both sequential threshold voting and parallel majority voting. We show how a well-known O(n)-time sequential algorithm for m-out-of-n voting can be parallelized through a simple divide-and-conquer strategy. When m = theta(n), the resulting algorithm has O(log(2) n) time complexity on PRAM and hypercube computers and optimal O(n(1/k)) complexity on a k-dimensional mesh-connected architecture. We also analyze the time complexity of the algorithm in the case of m = o(n) and for certain weighted threshold voting schemes.

关键词： data fusion dependable computation distributed processing majority voting multi-channel computation parallel complexity voting schemes

来源：评论

学校读者我要写书评

暂无评论

Submodular Maximization with Matroid and Packing Constraints in parallel 2019

Submodular Maximization with Matroid and Packing Constraints...

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Ene, Alina Nguyen, Huy L. Vladu, Adrian Boston Univ Dept Comp Sci 111 Cummington St Boston MA 02215 USA Northeastern Univ Coll Comp & Informat Sci Boston MA 02115 USA

ISBN: (纸本)9781450367059

We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries. We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a 1 - 1/e - epsilon approximation for monotone functions and a 1/e - epsilon approximation for non-monotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is O(log(2) n/epsilon(3)), which is an exponential speedup over the existing algorithms. We obtain the first parallel algorithm for non-monotone submodular maximization subject to packing constraints. Our algorithm achieves a 1/e - epsilon approximation using O(log(n/epsilon) log(1/epsilon) log(n + m)/epsilon(2)) parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a 1-1/e - epsilon approximation inO(log(n/epsilon) logm/epsilon(2)) parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective (Mahoney et al., 2016). Our results apply more generally to the problem of maximizing a diminishing returns submodular (DR-submodular) function.

关键词： DR-submodular maximization packing matroid parallel complexity

来源：评论

学校读者我要写书评

暂无评论

The characterization of parallel real-time optimization problems 16

The characterization of parallel real-time optimization prob...

引用

16th Annual International Symposium on High Performance Computing Systems and Applications

作者： Bruda, SD Akl, SG Queens Univ Dept Comp & Informat Sci Kingston ON K7L 3N6 Canada

ISBN: (纸本)0769516262

We identify the class of optimization problem expressible as independence systems that can be solved in real time using a parallel machine with polynomially bounded resources as being exactly the class of matroid for which the size of the optimal solution can be computed in parallel real time. We also extend previous results, showing that the solution obtained by a parallel algorithm is arbitrarily better than the solution reported by a sequential one not only for the real-time minimum-weight spanning tree (as previously known). Indeed, we show that, for all practical purposes, such a property does in fact hold for any optimization problem that falls into the aforementioned class.

关键词： real time parallel complexity optimization independence systems matroids

来源：评论

学校读者我要写书评

暂无评论

Efficient and optimal parallel algorithms for cholesky decomposition

引用

Journal of Mathematical Modelling and Algorithms 2003年第3期2卷 217-234页

作者： Santos, Eunice E. Chu, Pei-Yue Department of Computer Science Virginia Polytechnic Institute and State University Blacksburg VA 24061 United States Department of Computer Science and Engineering Lehigh University Bethlehem PA 18015 United States

In this paper, we consider the problem of developing efficient and optimal parallel algorithms for Cholesky decomposition. We design our algorithms based on different data layouts and methods. We thereotically analyze the run-time of each algorithm. In order to determine the optimality of the algorithms designed, we derive theoretical lower bounds on running time based on initial data layout and compare them against the algorithmic run-times. To address portability, we design our algorithms and perform complexity analysis on the LogP model. Lastly, we implement our algorithms and analyze performance data. © 2004 Kluwer Academic Publishers. Printed in the Netherlands.

关键词： Algorithms and complexity Cholesky decomposition LogP model Numerical linear algebra parallel complexity

来源：评论

学校读者我要写书评

暂无评论

Sparse Submodular Function Minimization 64

Sparse Submodular Function Minimization

引用

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

作者： Graur, Andrei Jiang, Haotian Sidford, Aaron Stanford Univ Management Sci & Engn Stanford CA 94305 USA Microsoft Res Redmond WA USA

ISBN: (纸本)9798350318944

In this paper we study the problem of minimizing a submodular function f : 2(V) -> R that is guaranteed to have a k-sparse minimizer. We give a deterministic algorithm that computes an additive epsilon-approximate minimizer of such f in (O) over tilde (poly(k) log(|f|/epsilon) parallel depth using a polynomial number of queries to an evaluation oracle of f, where |f| = max(S subset of V) |f(S)|. Further, we give a randomized algorithm that computes an exact minimizer of f with high probability using (O) over tilde(|V|.poly(k)) queries and polynomial time. When k = (O) over tilde (1), our algorithms use either nearly-constant parallel depth or a nearly-linear number of evaluation oracle queries. All previous algorithms for this problem either use delta(|V|) parallel depth or Omega(|V|(2)) queries. In contrast to state-of-the-art weakly-polynomial and strongly-polynomial time algorithms for SFM, our algorithms use first-order optimization methods, e.g., mirror descent and follow the regularized leader. We introduce what we call sparse dual certificates, which encode information on the structure of sparse minimizers, and both our parallel and sequential algorithms provide new algorithmic tools for allowing first-order optimization methods to efficiently compute them. Correspondingly, our algorithm does not invoke fast matrix multiplication or general linear system solvers and in this sense is more combinatorial than previous state-of-the-art methods.

关键词： submodular function minimization convex optimization sparsity query complexity parallel complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：