Periodic symmetric functions, serial addition, and multiplicationwith neural networks

This paper investigates threshold based neural networks for periodic symmetric Boolean functions and some related operations. It is shown that any n-input variable periodic symmetric Boolean function can be implemented with a feedforward linear threshold-based neural network with size of O(log n) and depth also of O(log n), both measured in terms of neurons. The maximum weight and fan-in values are in the order of O(n). Under the same assumptions on weight and fan-in values, an asymptotic bound of O(log n) for both size and depth of the network is also derived for symmetric Boolean functions that can be decomposed into a constant number of periodic symmetric Boolean subfunctions. Based on this results neural networks for serial binary addition and multiplication of n-bit operands are also proposed. It is shown that the serial addition can be computed with polynomially bounded weights and a maximum fan-in in the order of O(log n) in O(n/log n) serial cycles. Finally, it is shown that the serial multiplication can be computed in O(n) serial cycles with O(log n) size neural gate network, and with O(n log n) latches.     

Learning intersections and thresholds of halfspaces

We give the first polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution on the Boolean hypercube to within any constant error parameter. We also give the first quasipolynomial time algorithm for learning any Boolean function of a polylog number of polynomial-weight halfspaces under any distribution on the Boolean hypercube. As special cases of these results we obtain algorithms for learning intersections and thresholds of halfspaces. Our uniform distribution learning algorithms involve a novel non-geometric approach to learning halfspaces; we use Fourier techniques together with a careful analysis of the noise sensitivity of functions of halfspaces. Our algorithms for learning under any distribution use techniques from real approximation theory to construct low-degree polynomial threshold functions. Finally, we also observe that any function of a constant number of polynomial-weight halfspaces can be learned in polynomial time in the model of exact learning from membership and equivalence queries.     

Quantum one-way permutation over the finite field of two elements

In quantum cryptography, a one-way permutation is a bounded unitary operator \(U:\mathcal {H} \rightarrow \mathcal {H}\) on a Hilbert space \(\mathcal {H}\) that is easy to compute on every input, but hard to invert given the image of a random input. Levin (Probl Inf Transm 39(1):92–103, 2003) has conjectured that the unitary transformation \(g(a,x)=(a,f(x)+ax)\), where f is any length-preserving function and \(a,x \in \hbox {GF}_{{2}^{\Vert x\Vert }}\), is an information-theoretically secure operator within a polynomial factor. Here, we show that Levin’s one-way permutation is provably secure because its output values are four maximally entangled two-qubit states, and whose probability of factoring them approaches zero faster than the multiplicative inverse of any positive polynomial poly(x) over the Boolean ring of all subsets of x. Our results demonstrate through well-known theorems that existence of classical one-way functions implies existence of a universal quantum one-way permutation that cannot be inverted in subexponential time in the worst case.     

Ordered Boolean List (OBL): reducing the footprint for evaluating Boolean expressions

An Expanded Boolean Expression (EBE) does not contain any XOR or EQUAL operators. The occurrence of each variable is a different literal. We provide a linear time algorithm that converts an EBE of n literals into a logically equivalent Ordered Boolean List (OBL) and show how to use the OBL to evaluate the EBE in n steps and O(log log n) space, if the values of the literals are each read once in the order prescribed by the OBL. (An evaluation workspace of 5 bits suffices for all EBEs of up to six billion literals.) The primary application is the SIMD architecture, where the same EBE is evaluated in parallel for different input vectors when rendering solid models on the GPU directly from their Constructive Solid Geometry (CSG) representation. We compare OBL to the Reduced Ordered Binary Decision Diagram (ROBDD) and suggest possible applications of OBL to logic verification and to circuit design.     

布尔函数和伪布尔函数多项式表示的快速实现算法

布尔函数和伪布尔函数在不同的领域有着广泛的应用,利用多项式表示有利于刻划它们的一些特征属性。论文首先在已知输入都能得到输出的条件下给出了布尔函数多项式表示的快速实现算法,该算法仅用到模2加运算,运算次数少,具有简洁、易于编程实现、准确而快速的特点,而且该算法很易推广为伪布尔函数多项式表示的快速实现算法,只需把模2加运算换成实数加运算即可。接着通过比较说明了伪布尔函数多项式表示的快速实现算法,同时指出任何伪布尔函数都能通过多项式形式表示出来。最后通过实例进一步验证了算法的正确性。     

Generating and approximating nondominated coteries

A coterie, which is used to realize mutual exclusion in a distributed system is a family C of incomparable subsets such that every pair of subsets in C has at least one element in common. Associate with a family of subsets C a positive (i.e., monotone) Boolean function f_c such that f_c(x)=1 if the Boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise. It is known that C is a coterie if and only if f_c is dual-minor, and is a nondominated (ND) coterie if and only if f_c is self-dual. We introduce an operator ρ, which transforms a positive self-dual function into another positive self-dual function, and the concept of almost-self-duality, which is a close approximation to self-duality and can be checked in polynomial time (the complexity of checking positive self-duality is currently unknown). After proving several interesting properties of them, we propose a simple algorithm to check whether a given positive function is self-dual or not. Although this is not a polynomial algorithm, it is practically efficient in most cases. Finally, we present an incrementally polynomial algorithm that generates all positive self-dual functions (ND coteries) by repeatedly applying p operations. Based on this algorithm, all ND coteries of up to seven variables are computed     

Computation of functions on n bits by asynchronous clocking of cellular automata

Can a fixed cellular automaton compute different functions on any n-bit inputs, by providing only the n input bits as data and simulate the function only through the clocking scheme (a/synchronicity)? The perhaps surprising answer is: yes! The elementary cellular automaton with Wolfram number 57, as well as several CAs with 4 input cells are capable to compute those bijective functions on n bits that are equivalent to an even permutation on the domain $\{0,\dots, 2^n-1\}$ { 0 , … , 2 n ? 1 } , at least for n ≤ 10. To distinguish between functions, it suffices to vary the temporal order of updating the n cells in a deterministic way. We also characterize the non-bijective functions so computable, where we now need temporal schemes, which are not fully asynchronous. We start with pattern transformations ${\mathbb F}_2^n\ni v\, \mapsto \, w \in{\mathbb F}_2^n$ F 2 n ? v ? w ∈ F 2 n . The thread of all this is a novel paradigm: the algorithm is neither hard-wired (in the CA), nor in the program or data (initial configuration), but only in the temporal order of firing cells. And temporal order is pattern-universal.     

Unbounded-error quantum query complexity

This work studies the quantum query complexity of Boolean functions in an unbounded-error scenario where it is only required that the query algorithm succeeds with a probability strictly greater than 1/2. We show that, just as in the communication complexity model, the unbounded-error quantum query complexity is exactly half of its classical counterpart for any (partial or total) Boolean function. Moreover, connecting the query and communication complexity results, we show that the “black-box” approach to convert quantum query algorithms into communication protocols by Buhrman-Cleve—Wigderson [STOC’98] is optimal even in the unbounded-error setting.We also study a related setting, called the weakly unbounded-error setting, where the cost of a query algorithm is given by q+log(1/2(p−1/2)), where q is the number of queries made and p>1/2 is the success probability of the algorithm. In contrast to the case of communication complexity, we show a tight multiplicative Θ(logn) separation between quantum and classical query complexity in this setting for a partial Boolean function. The asymptotic equivalence between them is also shown for some well-studied total Boolean functions.     

Boolean functions with long prime implicants

In this short note we introduce a hierarchy of classes of Boolean functions, where each class is defined by the minimum allowed length of prime implicants of the functions in the class. We show that for a given DNF and a given class in the hierarchy, it is possible to test in polynomial time whether the DNF represents a function from the given class. For the first class in the hierarchy we moreover present a polynomial time algorithm which for a given input DNF outputs a shortest logically equivalent DNF, i.e. a shortest DNF representation of the underlying function. This class is therefore a new member of a relatively small family of classes for which the Boolean minimization problem can be solved in polynomial time. For the second class and higher classes in the hierarchy we show that the Boolean minimization problem can be approximated within a constant factor.     

基于k-ary消减的快速最大公约数算法

最大公约数(GCD)算法中,对于输入B和C,利用Sorenson的右移k-ary消减思想提出一个算法用于寻找整数x和y,使得x和y满足Bx-Cy在二进制表示下低比特位部分为0,即Bx-Cy=0(mod 2^e),其中e是常数正整数。利用该算法能够右移较多比特并大规模降低循环次数。再结合模算法,提出了快速GCD算法,其输入规模为n比特时最差复杂度仍然是O(n²),但最好的情况下复杂度能达到O(nlog²n log logn)。实验数据表明,对于20万以上比特规模的输入,快速GCD算法比Binary GCD算法速度快;对100万比特规模的输入,快速GCD算法速度是Binary GCD算法的两倍。     

On the uselessness of quantum queries

Given a prior probability distribution over a set of possible oracle functions, we define a number of queries to be useless for determining some property of the function if the probability that the function has the property is unchanged after the oracle responds to the queries. A familiar example is the parity of a uniformly random Boolean-valued function over {1,2,…,N}, for which N−1 classical queries are useless. We prove that if 2k classical queries are useless for some oracle problem, then k quantum queries are also useless. For such problems, which include classical threshold secret sharing schemes, our result also gives a new way to obtain a lower bound on the quantum query complexity, even in cases where neither the function nor the property to be determined is Boolean.     

多输出弹性k-旋转对称布尔函数的存在性与构造

多输出布尔函数可由多个单输出布尔函数表示,在分组密码中有着广泛的应用.多输出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-旋转对称布尔函数进行仿真测试.     

An Interval Polynomial Interpolation Problem and Its Lagrange Solution

In many practical problems, we need to use interpolation: we know that the value of a quantity is uniquely determined by some other quantity x (i.e., y = f(x)), we have measured several pairs of values (xi, yi), and we want to predict y for a given x. We can only guarantee estimates for y if we have some a priori information about the function f(x). In particular, in some problems, we know that f(x) is a polynomial of known degree d (e.g., that it is linear, or that it is quadratic). For this polynomial interpolation, with interval uncertainty of the input data (xi, yi), we present several reasonable algorithms that compute, for a given x0, guaranteed bounds for f(x0).     

Recognition of interval Boolean functions

Interval functions constitute a special class of Boolean functions for which it is very easy and fast to determine their functional value on a specified input vector. The value of an n-variable interval function specified by interval [a,b] (where a and b are n-bit binary numbers) is true if and only if the input vector viewed as an n-bit number belongs to the interval [a,b]. In this paper we study the problem of deciding whether a given disjunctive normal form represents an interval function and if so then we also want to output the corresponding interval. For general Boolean functions this problem is co-NP-hard. In our article we present a polynomial time algorithm which works for monotone functions. We shall also show that given a Boolean function f belonging to some class which is closed under partial assignment and for which we are able to solve the satisfiability problem in polynomial time, we can also decide whether f is an interval function in polynomial time. We show how to recognize a “renamable” variant of interval functions, i.e., their variable complementation closure. Another studied problem is the problem of finding an interval extension of partially defined Boolean functions. We also study some other properties of interval functions.      

Learning Read-Constant Polynomials of Constant Degree Modulo Composites

Boolean functions that have constant degree polynomial representation over a fixed finite ring form a natural and strict subclass of the complexity class ACC⁰. They are also precisely the functions computable efficiently by programs over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by polynomials of constant degree over arbitrary finite rings from membership queries, with the additional constraint that each variable in the target polynomial appears in a constant number of monomials. Our algorithm extends to superconstant but low degree polynomials and still runs in quasipolynomial time.