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

New upper bounds on the boolean circuit complexity of symmetric functions

INFORMATION PROCESSING LETTERS 2010年第7期110卷 264-267页

作者： Demenkov, E. Kojevnikov, A. Kulikov, A. Yaroslavtsev, G. VA Steklov Math Inst St Petersburg 191011 Russia St Petersburg State Univ St Petersburg Russia Acad Univ Moscow Russia

In this note, we present improved upper bounds on the circuit complexity of symmetric boolean functions. In particular, we describe circuits of size 4.5n + o(n) for any symmetric function of n variables, as well as ci... 详细信息

关键词： Computational complexity boolean circuit complexity Upper bounds Symmetric functions Modular functions

来源：评论

学校读者我要写书评

暂无评论

circuit complexity of symmetric boolean functions in antichain basis

引用

DISCRETE MATHEMATICS AND APPLICATIONS 2016年第1期26卷 31-39页

作者： Podolskaya, Olga V. Moscow MV Lomonosov State Univ Moscow 117234 Russia

We study the circuit complexity of boolean functions in an infinite basis consisting of all characteristic functions of antichains over the boolean cube. For an arbitrary symmetric function we obtain the exact value of its circuit complexity in this basis. In particular, we prove that the circuit complexities of the parity function and the majority function of n variables for all integers n 1 in this basis are [n+1/2] and [n/2] + 1 respectively. For the maximum circuit complexity of n-variable boolean functions in this basis, we show that its order of growth is equal ton.

关键词： boolean circuit complexity antichain functions boolean circuits symmetric boolean functions the Shannon function

来源：评论

学校读者我要写书评

暂无评论

A switching lemma for small restrictions and lower bounds for k-DNF resolution

引用

SIAM JOURNAL ON COMPUTING 2004年第5期33卷 1171-1200页

作者： Segerlind, N Buss, S Impagliazzo, R Inst Adv Study Sch Math Princeton NJ 08540 USA Univ Calif San Diego Dept Math La Jolla CA 92092 USA Univ Calif San Diego Dept Comp Sci La Jolla CA 92092 USA

We prove a new switching lemma that works for restrictions that set only a small fraction of the variables and is applicable to formulas in disjunctive normal form (DNFs) with small terms. We use this to prove lower bounds for the Res(k) propositional proof system, an extension of resolution which works with k-DNFs instead of clauses. We also obtain an exponential separation between depth d circuits of bottom fan-in k and depth d circuits of bottom fan-in k+1. Our results for Res(k) are as follows: 1. The 2n to n weak pigeonhole principle requires exponential size to refute in Res(k) for krootlog n/log log n. 2. For each constant k, there exists a constant w>k so that random w-CNFs require exponential size to refute in Res(k). 3. For each constant k, there are sets of clauses which have polynomial size Res(k+1) refutations but which require exponential size Res(k) refutations.

关键词： propositional proof complexity boolean circuit complexity switching lemmas lower bounds k-DNFs resolution Res(k) circuit bottom fan-in random restriction Sipser functions weak pigeonhole principles random CNFs

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A LOGARITHMIC boolean TIME ALGORITHM FOR PARALLEL POLYNOMIAL DIVISION

引用

INFORMATION PROCESSING LETTERS 1987年第4期24卷 233-237页

作者： BINI, D PAN, VY SUNY ALBANY DEPT COMP SCIALBANYNY 12222

A new algorithm is presented to improve by a factor of log m the estimates for both parallel and sequential time complexity of division with remainder of two integer polynomials. Under the parallel model, this means boolean logarithmic time, which is asymptotically optimum. The algorithm exploits the reduction of the problem to integer division; the polynomial remainder and quotient are recovered from integer remainder and quotient via binary segmentation.

关键词： Parallel computational complexity boolean circuit complexity polynomial division triangular Toeplitz matrix inversion interpolation by binary segmentation

来源：评论

学校读者我要写书评

暂无评论

Exponential lower bound for bounded depth circuits with few threshold gates

引用

INFORMATION PROCESSING LETTERS 2012年第7期112卷 267-271页

作者： Podolskii, Vladimir V. VA Steklov Math Inst Moscow 119991 Russia

We prove an exponential lower bound on the size of bounded depth circuits with O(log n) threshold gates computing an explicit function (namely, the parity function). Previously exponential lower bounds were known only for circuits with one threshold gate. Superpolynomial lower bounds are known for circuits with O(log(2) n) threshold gates. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Computational complexity boolean circuit complexity Threshold circuits Threshold functions Bounded depth circuits Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Uniqueness of optimal mod 3 polynomials for parity

引用

JOURNAL OF NUMBER THEORY 2010年第4期130卷 961-975页

作者： Green, Frederic Roy, Amitabha Clark Univ Dept Math & Comp Sci Worcester MA 01610 USA Akamai Technol Inc Cambridge MA 02142 USA

Text. In this paper, we completely characterize the quadratic polynomials modulo 3 with the largest (hence "optimal") correlation with parity. This result is obtained by analysis of the exponential sum S(t, k, n) = 1/2n Sigma(xi is an element of{1,-1)1 <= i <= n) (Pi(n)(i=1) xi) omega(t(x1,x2,....xn)+k(x1,x2..... xn)) where t(x(1),..., x(n)) and k(x(1), ..., x(n)) are quadratic and linear forms respectively, over Z(3)[x(1), ..., x(n)], and omega = e(2 pi i/3) is the primitive cube root of unity. In Green (2004) [7]. it was shown that |S(t, k, n)] <= (root 3/2)([n/2]) where this upper bound is tight. In this paper, we show that the polynomials achieving this bound are unique up to permutations and constant factors. We also prove that if |S(t, k, n)| <= (root 3/2)([n/2]), then |S(t, k, n)| <= (root 3/2)([n/2]). This verifies two conjectures made in Dueflez et al. (2006) [5] for the special case of quadratic polynomials in Z(3). Video. For a video summary of this paper, please click here or visit http://***/watch?v=mBojrn1DuOM. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Exponential sums Quadratic forms Tight bounds boolean circuit complexity

来源：评论

学校读者我要写书评

暂无评论

AREA TIME OPTIMAL FAST IMPLEMENTATION OF SEVERAL FUNCTIONS IN A VLSI MODEL

引用

IEEE TRANSACTIONS ON COMPUTERS 1984年第5期33卷 455-462页

作者： WADA, K HAGIHARA, K TOKURA, N Faculty of Engineering Science Department of Information and Computer Sciences Osaka University

Area and computation time are considered to be important measures with which VLSI circuits are evaluated. In this paper, the area-time complexity for nontrivial n-input m-output boolean functions, such as a decoder and an encoder, is studied with a model similar to Brent-Kung"s model. A lower bound on area-time-product (ATαaα.≥1) for these functions is shown: for example, ATα= ω(2n. nα-l) for an n-input 2V-output decoder, and ATα= ω( n . logα-1n) for an n-input ⌈log n⌉-output encoder. The results shown in this paper are complementary to those by Brent-Kung or Thompson, and are useful for a class of functions of rather simple structures, e.g., a priority encoder, a comparator, and symmetric functions.

关键词： Area efficient layout boolean circuit complexity VLSI model area-time complexity priority encoder

来源：评论

学校读者我要写书评

暂无评论

APPLICATIONS OF A PLANAR SEPARATOR THEOREM: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1980年第3期9卷 615-627页; 作者： LIPTON, RJ TARJAN, RE; Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only O(n−<span style="position: absolute; font-family: MathJax_Main; top:; Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only $O (\sqrt{n})$; 来源：评论; 学校读者我要写书评

暂无评论

LOCALITY FROM circuit LOWER BOUNDS

引用

SIAM JOURNAL ON COMPUTING 2012年第6期41卷 1481-1523页

作者： Anderson, Matthew van Melkebeek, Dieter Schweikardt, Nicole Segoufin, Luc Univ Wisconsin Dept Comp Sci Madison WI 53706 USA Goethe Univ Frankfurt Inst Math D-60325 Frankfurt Germany INRIA LSV F-84235 Cachan France ENS F-84235 Cachan France

We study the locality of an extension of first-order logic that captures graph queries computable in AC(0), i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the particular interpretation of the numerical predicates. We refer to such formulas as Arb-invariant first-order. We consider the two standard notions of locality, Gaifman and Hanf locality. Our main result gives a Gaifman locality theorem: An Arb-invariant first-order formula cannot distinguish between two tuples that have the same neighborhood up to distance (log n)(c), where n represents the number of elements in the structure and c is a constant depending on the formula. When restricting attention to string structures, we achieve the same quantitative strength for Hanf locality. In both cases we show that our bounds are tight. We also present an application of our results to the study of regular languages. Our proof exploits the close connection between first-order formulas and the complexity class AC(0) and hinges on the tight lower bounds for parity on constant-depth circuits.

关键词： finite model theory order-invariance Arb-invariance Gaifman locality Hanf locality boolean circuit complexity constant-depth circuits regular languages

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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