首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
布尔函数线性等价的分析与应用   总被引:3,自引:0,他引:3  
孟庆树  张焕国 《计算机学报》2004,27(11):1528-1532
对于g(x) =f(xA +b) +l·x +c ,给定f(x) ,g(x) ,如何求取等价关系A ,b ,l,c是一个有用的问题 .该文利用Walsh谱和自相关函数谱作为工具 ,给出的算法 1可以求取g(x) =f(xA)型的等价关系 .针对g(x) =f(xA +b)+l·x +c类型的等价关系 ,当b已知时 ,基于Fuller Millan算法给出的算法 2比Fuller Millan算法至少要快k - 1倍 ,其中k为函数绝对自相关函数谱含有的谱类个数 .应用于AES的S 盒的 8个布尔函数间等价关系的求取 ,算法 2比Fuller Millan算法提高速度近 2 0倍 .应用于IP (IsomorphismofPolynomials)问题的分析 ,指出Patarin所给参数的IP问题是可解的 ,因此基于IP问题的密码体制是不安全的 .  相似文献   

2.
该文针对传统表决算法通信复杂性高的问题,提出了将现有的 ECC( Error Correcting Codes)用于表决问题的算法,极大地减少了通信复杂性,取得了与传统表决算法同样的效果,从而实现NMR(N Modular Redundant)系统通信复杂性的优化。  相似文献   

3.
Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC1 . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires depth. This would separate AC1 from NC1. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dkO(d 2(k log k)1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds. Received: July 30, 1999.  相似文献   

4.
半bent函数是一类非线性度几乎最优且平衡的布尔函数,它弥补了bent函数的一些不足,如变元个数可以是奇数,具有平衡性.半bent函数可用于对称密码系统的设计和CDMA系统中的正交可变扩频码的构造.本文利用不相交线性码构造了一类新的半bent函数,设输入维度为n,当n=2k+1时,将F2^n划分为2^k+1个[n,k]线性码和1个[n,k+1]线性码,通过从该码集中选取合适线性码作支撑集来构造新的半bent函数.另一方面,多输出布尔函数(向量值函数)在应用中的效率更高,因此其使用场景更为广泛.本文同时利用不相交线性码构造了(n,n-k)平衡的多输出布尔函数,其中n/3相似文献   

5.
We investigate the computational power of threshold—AND circuits versus threshold—XOR circuits. In contrast to the observation that small weight threshold—AND circuits can be simulated by small weight threshold—XOR circuit, we present a function with small size unbounded weight threshold—AND circuits for which all threshold—XOR circuits have exponentially many nodes. This answers the basic question of separating subsets of the hypercube by hypersurfaces induced by sparse real polynomials. We prove our main result by a new lower bound argument for threshold circuits. Finally we show that unbounded weight threshold gates cannot simulate alternation: There are -functions which need exponential size threshold—AND circuits. Received: August 8, 1996.  相似文献   

6.
The paper by Roman Smolensky is a nice example of the art of studying mathematical structures that are, on the one hand, motivated by real computational problems but are, on the other hand, not obviously related.Dedicated to the memory of Roman Smolensky  相似文献   

7.
Define the MOD m -degree of a boolean functionF to be the smallest degree of any polynomialP, over the ring of integers modulom, such that for all 0–1 assignments , iff . We obtain the unexpected result that the MOD m -degree of the OR ofN variables is , wherer is the number of distinct prime factors ofm. This is optimal in the case of representation by symmetric polynomials. The MOD n function is 0 if the number of input ones is a multiple ofn and is one otherwise. We show that the MOD m -degree of both the MOD n and functions isN (1) exactly when there is a prime dividingn but notm. The MOD m -degree of the MOD m function is 1; we show that the MOD m -degree of isN (1) ifm is not a power of a prime,O(1) otherwise. A corollary is that there exists an oracle relative to which the MOD m P classes (such as P) have this structure: MOD m P is closed under complementation and union iffm is a prime power, and MOD n P is a subset of MOD m P iff all primes dividingn also dividem.  相似文献   

8.
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 circuits of size 3n for function.  相似文献   

9.
Theory of groups and methods of combinatorial analysis are used to obtain some classes of equiprobable Boolean functions with no zero Fourier coefficients. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 95–111, November–December 2006.  相似文献   

10.
The combinational complexity of a system of partial derivatives in the basis of linear functions is established for a Boolean function of n variables that is realized by a Zhegalkin polynomial. An algorithm whose complexity equals 3n – 2n modulo 2 additions is proposed for computation of all partial derivatives of such a function from the coefficients of its Zhegalkin polynomial.  相似文献   

11.
Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.  相似文献   

12.
In the k-Restricted-Focus-of-Attention (k-RFA) model, only k of the n attributes of each example are revealed to the learner, although the set of visible attributes in each example is determined by the learner. While thek -RFA model is a natural extension of the PAC model, there are also significant differences. For example, it was previously known that learnability in this model is not characterized by the VC-dimension and that many PAC learning algorithms are not applicable in the k-RFA setting.In this paper we further explore the relationship between the PAC and k -RFA models, with several interesting results. First, we develop an information-theoretic characterization of k-RFA learnability upon which we build a general tool for proving hardness results. We then apply this and other new techniques for studying RFA learning to two particularly expressive function classes,k -decision-lists (k-DL) and k-TOP, the class of thresholds of parity functions in which each parity function takes at most k inputs. Among other results, we prove a hardness result for k-RFA learnability of k-DL,k n-2 . In sharp contrast, an (n-1)-RFA algorithm for learning (n-1)-DL is presented. Similarly, we prove that 1-DL is learnable if and only if at least half of the inputs are visible in each instance. In addition, we show that there is a uniform-distribution k-RFA learning algorithm for the class of k -DL. For k-TOP we show weak learnability by ak -RFA algorithm (with efficient time and sample complexity for constant k) and strong uniform-distribution k-RFA learnability of k-TOP with efficient sample complexity for constant k. Finally, by combining some of our k-DL and k-TOP results, we show that, unlike the PAC model, weak learning does not imply strong learning in the k -RFA model.  相似文献   

13.
We estimate Fourier coefficients of a Boolean function which has recently been introduced in the study of read-once branching programs. Our bound implies that this function has rather “flat” Fourier spectrum and thus implies several lower bounds on some of its complexity measures.  相似文献   

14.
多输出布尔函数可由多个单输出布尔函数表示,在分组密码中有着广泛的应用.多输出k-旋转对称布尔函数(k-RSBF)是多输出旋转对称布尔函数(RSBF)的扩展.本文首先研究多输出旋转对称函数和多输出k-旋转对称函数的轨道分布情况,给出了计算两类函数中长度相同轨道个数的方法.其次研究了平衡多输出k-旋转对称布尔函数的存在性,给出了在选择合适的k的前提下,n=pr、n=2pr和n=2r时,平衡(n,m)k-RSBF的构造方法.之后研究弹性多输出k-旋转对称布尔函数的存在性,分别给出了r≥3,n=2r,2≤m≤2r-r,k=2时1阶弹性(n,m)k-RSBF的构造方法,以及p为奇素数,r≥2,n=pr,2≤m≤p-1,k=p时1阶弹性(n,m)k-RSBF的构造方法.最后我们还对两种方法得到的1阶弹性多输出k-旋转对称布尔函数进行仿真测试.  相似文献   

15.
Analysis of affinely equivalent Boolean functions   总被引:1,自引:0,他引:1  
By some basic transforms and invariant theory, we give two results: 1) an algorithm, which can be used to judge if two Boolean functions are affinely equivalent and to obtain the equivalence relationship if they are equivalent. This is useful in studying Boolean functions and in engineering. For example, we classify all 8-variable homogeneous bent functions of degree 3 into two classes; 2) Reed-Muller codes R(4,6)/R(1,6), R(3,7)/R(1,7) are classified efficiently.  相似文献   

16.
    
Communication complexity of two-party (multiparty) protocols has established itself as a successful method for proving lower bounds on the complexity of concrete problems for numerous computing models. While the relations between communication complexity and oblivious, semilective computations are usually transparent and the main difficulty is reduced to proving nontrivial lower bounds on the communication complexity of given computing problems, the situation essentially changes, if one considers non-oblivious or multilective computations. The known lower bound proofs for such computations are far from being transparent and the crucial ideas of these proofs are often hidden behind some nontrivial combinatorial analysis. The aim of this paper is to create a general framework for the use of two-party communication protocols for lower bound proofs on multilective computations. The result of this creation is not only a transparent presentation of some known lower bounds on the complexity of multilective computations on distinct computing models, but also the derivation of new nontrivial lower bounds on multilective VLSI circuits and multilective planar Boolean circuits. In the case of VLSI circuits we obtain a generalization of Thompson's lower bounds on AT2 complexity for multilective circuits. The Ω(n2) lower bound on the number of gates of any k-multilective planar Boolean circuit computing a specific Boolean function of n variables is established for . Another advantage of this framework is that it provides lower bounds for a lot of concrete functions. This contrasts to the typical papers devoted to lower bound proofs, where one establishes a lower bound for one or a few specific functions.https://doi.org/10.1051/ita:1999113  相似文献   

17.
本文讨论了向量值函数代数免疫度的定义,给出了向量值函数的代数免疫度与其非线性度之间的关系,研究了布尔函数的重量与其代数免疫度之间的关系,利用该关系,给出了达到最大代数免疫度的平衡布尔函数个数的一个下界。  相似文献   

18.
Basic identities of Boolean algebra are considered, and their categorical analogs are proved.  相似文献   

19.
A new approach to the decomposition of Boolean functions of n variables is considered; the functions being decomposed can be represented in various forms. The approach is based on the method of q-partitions of minterms and on the introduced concept of a decomposition clone. The theorem on simple separating decomposition of full and partial functions is formulated. The approach proposed is illustrated by examples.  相似文献   

20.
Qing Zhou 《Computing》2001,67(2):167-181
In this paper we introduce the notion of relative computability for continuous real valued functions. It combines the notion of relative recursiveness for number theoretic functions with the theory of computability for continuous real valued functions. Most of the space is devoted to investigating the degrees of unsolvability of those mathematical operations which lead from the computable to the noncomputable. The paper concludes with Theorem 5, which asserts that the derivatives of computable C 1 functions on compact intervals are at most semi-computable. Received May 15, 2000  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号