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

Upper bounds on the depth of symmetric boolean functions

Moscow University Computational Mathematics and Cybernetics 2013年第4期37卷 195-201页

作者： Sergeev, I.S. Moscow State University Moscow 119991 Russian Federation

A new method for implementing the counting function with boolean circuits is proposed. It is based on modular arithmetic and allows us to derive new upper bounds for the depth of the majority function of n variables: 3.34log₂ n over the basis B ₂ of all binary boolean functions and 4.87log₂ n over the standard basis B ₀ = {∧, ∨, -}. As a consequence, the depth of the multiplication of n-digit binary numbers does not exceed 4.34log₂ n and 5.87log₂ n over the bases B ₂ and B ₀, respectively. The depth of implementation of an arbitrary symmetric boolean function of n variables is shown to obey the bounds 3.34log₂ n and 4.88log₂ n over the same bases. © 2013 Allerton Press, Inc.

关键词： boolean circuits Depth majority function multiplication symmetric boolean functions

来源：评论

学校读者我要写书评

暂无评论

Upper Bounds for the Formula Size of symmetric boolean functions

引用

RUSSIAN MATHEMATICS 2014年第5期58卷 30-42页

作者： Sergeev, I. S. Moscow MV Lomonosov State Univ GSP 1 Moscow 119991 Russia

We prove that the complexity of the implementation of the counting function of n boolean variables by binary formulas is at most n(3.03), and it is at most n(4.47) for DeMorgan formulas. Hence, the same bounds are valid for the formula size of any threshold symmetric function of n variables, particularly, for the majority function. The following bounds are proved for the formula size of any symmetric boolean function of n variables: n(3.04) for binary formulas and n(4.48) for DeMorgan ones. The proof is based on the modular arithmetic.

关键词： formula size symmetric boolean functions majority function multiplication

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Basic theory in construction of boolean functions with maximum possible annihilator immunity

引用

DESIGNS CODES AND CRYPTOGRAPHY 2006年第1期40卷 41-58页

作者： Dalai, Deepak Kumar Maitra, Subhamoy Sarkar, Sumanta Indian Stat Inst Appl Stat Unit Kolkata 700108 W Bengal India

So far there is no systematic attempt to construct boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric boolean function with O(n(2)) time and O(n) space complexity.

关键词： algebraic attack algebraic degree algebraic immunity annihilator annihilator immunity balancedness boolean functions Krawtchouk polynomials nonlinearity symmetric boolean functions

来源：评论

学校读者我要写书评

暂无评论

RECURSIONS FOR MODIFIED WALSH TRANSFORMS OF SOME FAMILIES OF boolean functions

引用

ROCKY MOUNTAIN JOURNAL OF MATHEMATICS 2022年第4期52卷 1355-1373页

作者： Gomez-Flores, Axel O. Medina, Luis A. Stanica, Pantelimon Ohio State Univ Dept Math 231 W 18th Ave Columbus OH 43210 USA Univ Puerto Rico Dept Math San Juan PR 00936 USA Naval Postgrad Sch Dept Appl Math Monterey CA USA

We show that, under certain conditions, restricted and biased exponential sums and Walsh transforms of symmetric and rotation symmetric boolean functions are, as in the case of nonbiased domain, C-finite sequences. We also prove that under other conditions, these sequences are P-finite, which is a somewhat different behavior than their nonbiased counterparts. We further show that exponential sums and Walsh transforms of a family of rotation symmetric monomials over the restricted domain E-n,E-j = {x is an element of F-2(n) : wt ( x) = j} (wt (x) is the weight of the vector x) are given by polynomials of degree at most j, and so, they are also C-finite sequences. Finally, we also present a study of the behavior of symmetric boolean functions under these biased transforms.

关键词： biased Walsh transform restricted Walsh transform restricted domains symmetric boolean functions rotation symmetric boolean functions linear recurrences

来源：评论

学校读者我要写书评

暂无评论

Efficient quantum algorithms to construct arbitrary Dicke states

引用

QUANTUM INFORMATION PROCESSING 2014年第9期13卷 2049-2069页

作者： Chakraborty, Kaushik Choi, Byung-Soo Maitra, Arpita Maitra, Subhamoy Indian Stat Inst Kolkata India Duke Univ Dept Elect & Comp Engn Durham NC 27708 USA

In this paper, we study several quantum algorithms toward the efficient construction of arbitrary arbitrary Dicke state. The proposed algorithms use proper symmetric boolean functions that involve manipulation with Krawtchouk polynomials. Deutsch-Jozsa algorithm, Grover algorithm, and the parity measurement technique are stitched together to devise the complete algorithm. In addition to that we explore how the biased Hadamard transformation can be utilized into our strategy, motivated by the work of Childs et al. (Quantum Inf Comput 2(3):181-191, 2002).

关键词： Biased Hadamard transform Deutsch-Jozsa algorithm Dicke state Grover algorithm Krawtchouk polynomial Parity measurement symmetric boolean functions

来源：评论

学校读者我要写书评

暂无评论

Conjugate symmetry

引用

FORMAL METHODS IN SYSTEM DESIGN 2011年第3期38卷 263-288页

作者： Maurer, Peter M. Baylor Univ Dept Comp Sci Waco TX 76798 USA

Conjugate symmetry is an entirely new approach to symmetric boolean functions that can be used to extend existing methods for handling symmetric functions to a much wider class of functions. These are functions that currently appear to have no symmetries of any kind. Conjugate symmetries occur widely in practice. In fact, we show that even the simplest circuits exhibit conjugate symmetry. To demonstrate the effectiveness of conjugate symmetry we modify an existing simulation algorithm, the hyperlinear algorithm, to take advantage of conjugate symmetry. This algorithm can simulate symmetric functions faster than non-symmetric ones, but due to the rarity of symmetric functions, this optimization is of limited benefit. Because the standard benchmark circuits contain many symmetries it is possible to simulate these circuits faster than is possible with the fastest known event-driven algorithm. The detection and exploitation of conjugate symmetries makes use of GF(2) matrices. It is likely that conjugate symmetry and GF(2) matrices will find applications in many other areas of EDA.

关键词： symmetric boolean functions Logic simulation

来源：评论

学校读者我要写书评

暂无评论

Synthesis of symmetric functions for path-delay fault testability

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2000年第9期19卷 1076-1081页

作者： Chakrabarti, S Das, S Das, DK Bhattacharya, BB Univ Kalyani Dept Comp Sci Kalyani 741235 W Bengal India Indian Stat Inst ACM Unit Kolkata 700035 W Bengal India Jadavpur Univ CSE Dept Kolkata 700032 W Bengal India

A new technique of synthesizing totally symmetric boolean functions is presented that achieves complete robust path-delay fault testability. We show that every consecutive symmetric function can be expressed as a logical composition (e.g., AND, NOR) of two unate symmetric functions, and the resulting composite circuit can be made robustly path-delay fault testable, if the constituent unate functions are synthesized as two-level irredundant circuits. Nonconsecutive symmetric functions can also be synthesized by decomposing them into a set of consecutive symmetric functions. The circuit cost of the proposed design can further be reduced by a novel algebraic factorization technique based on some combinatorial clues. The overall synthesis guarantees complete robust path-delay fault testability and can be completed in linear time. The results shows that the proposed method ensures a significant reduction in hardware, as well as in the number of paths,,which in turn, reduces testing time, as compared to those of the best-known earlier methods.

关键词： delay faults symmetric boolean functions synthesis-for-testability

来源：评论

学校读者我要写书评

暂无评论

Algorithms for the Unit-Cost Stochastic Score Classification Problem

引用

ALGORITHMICA 2022年第10期84卷 3054-3074页

作者： Grammel, Nathaniel Hellerstein, Lisa Kletenik, Devorah Liu, Naifeng Univ Maryland College Pk MD 20742 USA NYU Tandon Sch Engn Brooklyn NY 11201 USA CUNY Brooklyn Coll Brooklyn NY 11210 USA CUNY Grad Ctr New York NY USA

Consider the following Stochastic Score Classification problem. A doctor is assessing a patient's risk of developing a disease and can perform n different binary tests on the patient. The probability that test i is positive is p(i) and the outcomes of the n tests are independent. A patient's score is the total number of positive tests. Possible scores thus range between 0 and n. This range is divided into subranges, corresponding to risk classes (e.g., LOW, MEDIUM, or HIGH risk). Each test has an associated cost. To reduce testing cost, instead of performing all tests and determining an exact score, the doctor can perform tests sequentially and stop testing when it is possible to determine the patient's risk class. The problem is to determine the order in which the doctor should perform the tests, so as to minimize expected testing cost. We address the unit-cost case of the Stochastic Score Classification problem, and provide polynomial-time approximation algorithms for adaptive and non-adaptive versions of the problem. We also pose a number of open questions.

关键词： Approximation algorithms symmetric boolean functions Stochastic probing Sequential testing Adaptivity

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Behavior of Perturbations of symmetric functions

引用

ANNALS OF COMBINATORICS 2014年第3期18卷 397-417页

作者： Castro, Francis N. Medina, Luis A. Univ Puerto Rico Dept Math San Juan PR 00931 USA

In this paper we consider perturbations of symmetric boolean functions sigma(n,k1) + ... + sigma(n,ks) in n-variable and degree k(s). We compute the asymptotic behavior of boolean functions of the type sigma(n,k1) + ... + sigma(n,ks) + F(X-1, ... , X-j) for j fixed. In particular, we characterize all the boolean functions of the type sigma(n,k1) + ... + sigma(n,ks) + F(X-1, ... , X-j) that are asymptotic balanced. We also present an algorithm that computes the asymptotic behavior of a family of boolean functions from one member of the family. Finally, as a byproduct of our results, we provide a relation between the parity of families of sums of binomial coefficients.

关键词： symmetric boolean functions exponential sums recurrences

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：