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

Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth

THEORETICAL COMPUTER SCIENCE 2020年 820卷 17-25页

作者： Lingas, Andrzej Lund Univ Dept Comp Sci Lund Sweden

We consider normalized boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized boolean circuits computing boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., the maximum number of and-gates on a directed path to an output gate). In particular, we show that any normalized boolean circuit of at most epsilon log n conjunction-depth computing the n-dimensional boolean vector convolution has Omega(n(2-4 epsilon)) and-gates. For boolean matrix product, we derive even a stronger lower-bound trade-off. Instead of conjunction-depth we use the negation-dependent conjunction-depth, where one counts only and-gates whose each direct predecessor has a (not necessarily direct) predecessor representing a negated input variable. We show that if a normalized boolean circuit of at most epsilon log n negation-dependent conjunction-depth computes the n x n boolean matrix product then the circuit has Omega(n(3-2 epsilon)) and-gates. We complete our lower-bound trade-offs for the boolean convolution and matrix product with upper-bound trade-offs of similar form yielded by the known fast algebraic algorithms. (C) 2020 Elsevier B.V. All rights reserved.

关键词： boolean circuits boolean circuit complexity Semi-disjoint bilinear form boolean vector convolution boolean matrix product

来源：评论

学校读者我要写书评

暂无评论

Extreme Witnesses and Their Applications

引用

ALGORITHMICA 2018年第12期80卷 3943-3957页

作者： Lingas, Andrzej Persson, Mia Lund Univ Dept Comp Sci S-22100 Lund Sweden Malmo Univ Dept Comp Sci S-20506 Malmo Sweden

We study the problem of computing the so called minimum and maximum witnesses for boolean vector convolution. We also consider a generalization of the problem which is to determine for each positive value at a coordinate of the convolution vector, q smallest (largest) witnesses, where q is the minimum of a parameter k and the number of witnesses for this coordinate. We term this problem the smallest k-witness problem or the largest k-witness problem, respectively. We also study the corresponding smallest and largest k-witness problems for boolean matrix product. First, we present an (O) over tilde (n(1.5)k(0.5))-time algorithm for the smallest or largest k-witness problem for the boolean convolution of two n-dimensional vectors, where the notation (O) over tilde ( ) suppresses polylogarithmic in n factors. In consequence, we obtain new upper time bounds on reporting positions of mismatches in potential string alignments and on computing restricted cases of the (min, +) vector convolution. Next, we present a fast (substantially subcubic in n and linear in k) algorithm for the smallest or largest k-witness problem for the boolean matrix product of two n x n boolean matrices. It yields fast algorithms for reporting k lightest (heaviest) triangles in a vertex-weighted graph.

关键词： boolean vector convolution boolean matrix product String matching Witnesses Minimum and maximum witnesses Lightest triangles Time complexity

来源：评论

学校读者我要写书评

暂无评论

Small Normalized boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth 33

Small Normalized Boolean Circuits for Semi-disjoint Bilinear...

引用

33rd Computational Complexity Conference (CCC)

作者： Lingas, Andrzej Lund Univ Dept Comp Sci Box 118 S-22100 Lund Sweden

ISBN: (纸本)9783959770699

关键词： boolean circuits semi-disjoint bilinear form boolean vector convolution boolean matrix product

来源：评论

学校读者我要写书评

暂无评论

Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the boolean convolution 14th

Towards an Almost Quadratic Lower Bound on the Monotone Circ...

引用

14th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Lingas, Andrzej Lund Univ Dept Comp Sci Lund Sweden

ISBN: (纸本)9783319559117;9783319559100

We study the monotone circuit complexity of the so called semi-disjoint bilinear forms over the boolean semi-ring, in particular the n-dimensional boolean vector convolution. Besides the size of a monotone boolean circuit, we consider also the and-depth of the circuit, i.e., the maximum number of and-gates on a path to an output gate, and the monom number of the circuit which is the number of distinct subsets of input variables induced by monoms at the output gates. We show that any monotone boolean circuit of epsilon log n-bounded and-depth computing a boolean semi-disjoint form with 2n input variables and q prime implicants has Omega(q/n(2 epsilon)) size. As a corollary, we obtain the Omega(n(2-2 epsilon)) lower bound on the size of any monotone boolean circuit of so bounded and-depth computing the n-dimensional boolean vector convolution. Furthermore, we show that any monotone boolean circuit of 2(n epsilon)-bounded monom number, computing a boolean semi-disjoint form on 2n variables, where each variable occurs in p prime implicants, has Omega(n(1-2 epsilon)p) size. As a corollary, we obtain the Omega(n(2-2 epsilon)) lower bound on the size of any monotone boolean circuit of 2(n epsilon)-bounded monom number computing the n-dimensional boolean vector convolution. Finally, we demonstrate that in any monotone boolean circuit for a semi-disjoint bilinear form with q prime implicants that has size substantially smaller than q, the majority of the terms at the output gates representing prime implicants have to have very large length (i. e., the number of variable occurrences). In particular, in any monotone circuit for the n-dimensional boolean vector convolution of size o(n(2-4 epsilon)/log n) almost all prime implicants of the convolution have to be represented by terms at the circuit output gates of length at least n(epsilon).

关键词： Semi-disjoint bilinear form boolean vector convolution Monotone boolean circuit complexity

来源：评论

学校读者我要写书评

暂无评论

Extreme Witnesses and Their Applications 9th

Extreme Witnesses and Their Applications

引用

9th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Lingas, Andrzej Persson, Mia Lund Univ Dept Comp Sci Box 118 S-22100 Lund Sweden Malmo Univ Dept Comp Sci Malmo Sweden

ISBN: (纸本)9783319266268;9783319266251

关键词： boolean vector convolution boolean matrix product String matching Witnesses Minimum and maximum witnesses Time complexity Lightest triangles

来源：评论

学校读者我要写书评

暂无评论

Small normalized boolean circuits for semi-disjoint bilinear forms require logarithmic conjunction-depth 18

Small normalized boolean circuits for semi-disjoint bilinear...

引用

Proceedings of the 33rd Computational Complexity Conference

作者： Andrzej Lingas Lund University Lund Sweden

ISBN: (纸本)9783959770699

关键词： semi-disjoint bilinear form boolean vector convolution boolean matrix product boolean circuits

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：