Search

This article presents an alternative automation algorithm for pneumatic sequences that enables the solution of complex sequential problems without the need to organize detection phases into groups. By not using groups to organize movements in detection phases, two benefits can be achieved: firstly, all the drawbacks associated with using groups are eliminated, such as design complexity, difficulty in debugging, increased cost, and difficulty in optimizing the circuit; secondly, it enables the use of logical functions to define each motion in pneumatic actuators. This opens up the possibility to solve logical functions using Boolean algebra techniques, and even their generalization into an algorithm that can be programmed in any language. To validate the proposed algorithm, MATLAB pseudocode is presented. This pseudocode allows obtaining the logical functions needed to build the ladder diagram of any sequence involving up to four double-acting cylinders with any number of phases in a work cycle. [ABSTRACT FROM AUTHOR]

In this work, we study quantum versions of attribute-based encryption schemes. Attribute-based encryption enables fine-grained access control of encrypted data using authorization policies. The secret key of a user and the ciphertext are dependent upon attributes, and the decryption of a ciphertext is possible only if the set of attributes of the user key matches the attributes of the ciphertext. Most of the existing classical attribute-based schemes are based on the hardness of the bilinear Diffie–Hellman problem, which has been proven to be vulnerable against Shor's algorithm. No efficient quantum attribute-based encryption scheme has been reported till date. In this backdrop, we propose quantum attribute-based encryption schemes exploiting quantum key distribution and quantum error-correcting codes. Attribute-based scheme is a special case of a more general functional encryption scheme whose quantum version we consider next hence giving this work a unifying framework. We present two constructions of quantum functional encryption schemes. The first construction generalizes the traditional notion of functional encryption and can handle multiple functions. The second construction utilizes the quantum query complexities of different Boolean functions. As applications, we present a quantum progressive functional encryption scheme to suitably encrypt an image to be shared among data users with hierarchical relations between them and outline a connection between quantum functional encryption schemes and obfuscated quantum states. In this work, we use weak measurements, which help us to expand our horizon to include encryption schemes in the dishonest model and quantum communication in the presence of an adversary. Our methods are unconditional and do not depend on the known difficulty of problems like lattice-based problems. Finally, we discuss various advantages of our methods and results. [ABSTRACT FROM AUTHOR]

Among several approaches to tackle the problem of energy consumption in modern computing systems, two solutions are currently investigated: one consists of artificial neural networks (ANNs) based on photonic technologies, the other is a different paradigm compared to ANNs and it is based on random networks of non-linear nanoscale junctions resulting from the assembling of nanoparticles or nanowires as substrates for neuromorphic computing. These networks show the presence of emergent complexity and collective phenomena in analogy with biological neural networks characterized by self-organization, redundancy, and non-linearity. Starting from this background, we propose and formalize a generalization of the perceptron model to describe a classification device based on a network of interacting units where the input weights are non-linearly dependent. We show that this model, called "receptron", provides substantial advantages compared to the perceptron as, for example, the solution of non-linearly separable Boolean functions with a single device. The receptron model is used as a starting point for the implementation of an all-optical device that exploits the non-linearity of optical speckle fields produced by a solid scatterer. By encoding these speckle fields we generated a large variety of target Boolean functions. We demonstrate that by properly setting the model parameters, different classes of functions with different multiplicity can be solved efficiently. The optical implementation of the receptron scheme opens the way for the fabrication of a completely new class of optical devices for neuromorphic data processing based on a very simple hardware. [ABSTRACT FROM AUTHOR]

Affine equivalence of Boolean functions has various applications in computer science and modern cryptography, such as circuit design and S-boxes. Existing methods for detecting affine equivalence of Boolean functions work in some cases but not when the truth table of a Boolean function is sparse. To improve previous methods and overcome this limitation, we propose a method by transforming the Boolean function to a function with the property that its function values at the orthonormal basis are all equal to 1 or 0, which narrows down the search space of affine transformations. Our first algorithm has the advantage of getting a smaller search space than previous methods and is especially useful for sparse functions. Specifically, when the Boolean functions are sparse, the search space can be reduced exponentially in average and experiments show the efficiency of our first algorithm. We then present another algorithm to transform one circuit into its equivalent affine circuit by synthesizing a reversible circuit and inserting it in front of the original circuit. To our knowledge, this is the first work to automatically synthesize an affine equivalent circuit for any given circuit and the first to do this by combining reversible circuit and non-reversible circuit. [ABSTRACT FROM AUTHOR]

Cohesive powers of computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let $\omega $ , $\zeta $ , and $\eta $ denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of $\omega $. If $\mathcal {L}$ is a computable copy of $\omega $ that is computably isomorphic to the usual presentation of $\omega $ , then every cohesive power of $\mathcal {L}$ has order-type $\omega + \zeta \eta $. However, there are computable copies of $\omega $ , necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to $\omega + \zeta \eta $. For example, we show that there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \eta $. Our most general result is that if $X \subseteq \mathbb {N} \setminus \{0\}$ is a Boolean combination of $\Sigma _2$ sets, thought of as a set of finite order-types, then there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$ , where $\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$ denotes the shuffle of the order-types in X and the order-type $\omega + \zeta \eta + \omega ^*$. Furthermore, if X is finite and non-empty, then there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \boldsymbol {\sigma }(X)$. [ABSTRACT FROM AUTHOR]

Goldreich's pseudorandom generator is a well-known building block for many theoretical cryptographic constructions from multi-party computation to indistinguishability obfuscation. Its unique efficiency comes from the use of random local functions: each bit of the output is computed by applying some fixed public n-variable Boolean function f to a random public size-n tuple of distinct input bits. The characteristics that a Boolean function f must have to ensure pseudorandomness is a puzzling issue. It has been studied in several works and particularly by Applebaum and Lovett (STOC 2016) who showed that resiliency and algebraic immunity are key parameters in this purpose. In this paper, we propose the first study on Boolean functions that reach together maximal algebraic immunity and high resiliency. (1) We assess the possible consequences of the asymptotic existence of such optimal functions. We show how they allow to build functions reaching all possible algebraic immunity-resiliency trade-offs (respecting the algebraic immunity and Siegenthaler bounds). We provide a new bound on the minimal number of variables n, and thus on the minimal locality, necessary to ensure a secure Goldreich's pseudorandom generator. Our results come with a granularity level depending on the strength of our assumptions, from none to the conjectured asymptotic existence of optimal functions. (2) We extensively analyze the possible existence and the properties of such optimal functions. Our results show two different trends. On the one hand, we were able to show some impossibility results concerning existing families of Boolean functions that are known to be optimal with respect to their algebraic immunity, starting by the promising XOR-MAJ functions. We show that they do not reach optimality and could be beaten by optimal functions if our conjecture is verified. On the other hand, we prove the existence of optimal functions in low number of variables by experimentally exhibiting some of them up to 12 variables. This directly provides better candidates for Goldreich's pseudorandom generator than the existing XOR-MAJ candidates for polynomial stretches from 2 to 6. [ABSTRACT FROM AUTHOR]

Proofs of sharp phase transition and noise sensitivity in percolation have been significantly simplified by the use of randomized algorithms, via the OSSS inequality (proved by O'Donnell et al. and the Schramm–Steif inequality for the Fourier‐Walsh coefficients of functions defined on the Boolean hypercube. In this article, we prove intrinsic versions of the OSSS and Schramm–Steif inequalities for functionals of a general Poisson process, and apply these new estimates to deduce sufficient conditions—expressed in terms of randomized stopping sets—yielding sharp phase transitions, quantitative noise sensitivity, exceptional times and bounds on critical windows for monotonic Boolean Poisson functions. Our analysis is based on a new general definition of "stopping set", not requiring any topological property for the underlying measurable space, as well as on the new concept of a "continuous‐time decision tree", for which we establish several fundamental properties. We apply our findings to the k$$ k $$‐percolation of the Poisson Boolean model and to the Poisson‐based confetti percolation with bounded random grains. In these two models, we reduce the proof of sharp phase transitions for percolation, and of noise sensitivity for crossing events, to the construction of suitable randomized stopping sets and the computation of one‐arm probabilities at criticality. This enables us to settle an open problem suggested by Ahlberg et al. (a special case of which was conjectured earlier by Ahlberg et al. on noise sensitivity of crossing events for the planar Poisson Boolean model with random balls whose radius distribution has finite (2+α)$$ \left(2+\alpha \right) $$‐moments and also show the same for planar confetti percolation model with bounded random balls. We also prove that critical probability is 1/2$$ 1/2 $$ for the planar confetti percolation model with bounded, π/2$$ \pi /2 $$‐rotation invariant and reflection invariant random grains. Such a result was conjectured by Benjamini and Schramm in the case of fixed balls and proved by Müller, Hirsch and Ghosh and Roy in the case of balls, boxes and random boxes, respectively; our results contain all previous findings as special cases. [ABSTRACT FROM AUTHOR]

Secret sharing schemes are ideally suited to save highly sensitive information in distributed systems. On the other hand, Zigzag-Decodable (ZD) codes are employed in wireless distributed platforms for encoding data using only bit-wise shift and XOR operations. Recently, Vandermonde-based ZD codes have been utilized in secret sharing schemes to achieve high computational efficiency such that sharing and recovering of secrets can be realized by lightweight operations. However, the storage overhead of using these ZD codes remains a problem which is addressed in the present paper. Here, a ramp secret sharing scheme is proposed based on an efficient ZD code with less storage overhead in comparison with existing literature. The novelty of the proposed scheme lies in the careful selection of the number of positions to shift the bits of the secret such that security and zigzag decodability are guaranteed simultaneously. In addition to prove gaining these features, we show that the scheme improves speed of recovery. [ABSTRACT FROM AUTHOR]

High-speed allosteric hammerhead ribozymes can be engineered to distinguish well between a perfectly matching effector and the nucleic acid sequences with a few mismatches under physiologically relevant conditions. Such ribozymes can be designed to control the expression of exogenous mRNAs and can be used to develop new gene therapies, including anticancer treatments. The in vivo selection of such ribozymes is a complicated and lengthy procedure with no guarantee of success. Thus, in silico selection of high-speed ribozymes can be employed using secondary RNA structure computation based on the partition function of the RNA folding in combination with random search algorithms. This approach has already been proven very accurate in designing allosteric hammerhead ribozymes. Herein, we present two programs for the computational design of allosteric ribozymes sensing randomized oligonucleotides based on the extended version of the hammerhead ribozyme. A Generator for High-speed Oligonucleotide Sensing allosteric ribozymes with NOT logic function (GHOST-NOT) and a Generator for High-speed Oligonucleotide Sensing allosteric ribozymes with YES logic function (GHOST-YES) for computational design of high-speed allosteric ribozymes are described. The allosteric hammerhead ribozymes had a high self-cleavage rate of about 1.8 per minute and were very selective in sensing an effector sequence. [ABSTRACT FROM AUTHOR]

We prove that any Boolean function in n variables can be modeled by a testable Boolean circuit with two additional inputs in the basis "conjunction, oblique conjunction, disjunction, negation" so that the circuit admits a complete diagnostic test of the length at most 2n + 3 with respect to stuck-at faults of the type 1 at gate outputs. [ABSTRACT FROM AUTHOR]

We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. These are also counting CSP problems where every constraint has arity 3 and every variable is read-thrice. For every problem of the form Holant (f | = 3) , where f is any integer (or equivalently, rational)-valued ternary symmetric constraint function on Boolean variables, we prove that it is either P-time computable or #P-hard, depending on an explicit criterion of f. The constraint function can take both positive and negative values, allowing for cancellations. In addition, we discover a new phenomenon: there is a set F with the property that for every f ∈ F the problem Holant (f | = 3) is planar P-time computable but #P-hard in general, yet its planar tractability is by a combination of a holographic transformation by [ 1 1 1 − 1 ] to FKT together with an independent global argument. [ABSTRACT FROM AUTHOR]

Given a convex function Φ : [ 0 , 1 ] → R and the mean E f (X) = a ∈ [ 0 , 1 ] , which Boolean function f maximizes the Φ -stability E [ Φ (T ρ f (X)) ] of f? Here X is a random vector uniformly distributed on the discrete cube { - 1 , 1 } n and T ρ is the Bonami–Beckner operator. Special cases of this problem include the (symmetric and asymmetric) α -stability problems and the "Most Informative Boolean Function" problem. In this paper, we provide several upper bounds for the maximal Φ -stability. When specializing Φ to some particular forms, by these upper bounds, we partially resolve Mossel and O'Donnell's conjecture on α -stability with α > 2 , Li and Médard's conjecture on α -stability with 1 < α < 2 , and Courtade and Kumar's conjecture on the "Most Informative Boolean Function" which corresponds to a conjecture on α -stability with α = 1 . Our proofs are based on discrete Fourier analysis, optimization theory, and improvements of the Friedgut–Kalai–Naor (FKN) theorem. Our improvements of the FKN theorem are sharp or asymptotically sharp for certain cases. [ABSTRACT FROM AUTHOR]

Binary decision diagram (BDD) is used for technology-independent optimization, performed as the first stage in the synthesis of logic circuits in the design of application-specific integrated circuits (ASICs). BDD is an acyclic graph defining a Boolean function or a system of Boolean functions. Each vertex of this graph is associated with the complete or reduced Shannon expansion formula. Binary decision diagrams with mutually inverse subfunctions (cofactors) are considered. We have developed algorithms for finding algebraic representations of cofactors of the same BDD level in the form of a disjunction or conjunction of other inverse or non-inverse cofactors of the same BDD level. The algorithms allow reducing the number of literals by replacing the Shannon expansion formulas of a system of Boolean functions. It is proposed to use the developed algorithms for an additional logic optimization of the constructed BDD representations of systems of Boolean functions. The experimental results of application of the corresponding programs in synthesizing the logic circuits in the design library of custom VLSI CMOS circuits are presented. [ABSTRACT FROM AUTHOR]

The problems of synthesis of combinational circuits of code converters designed to reduce the length of words from a given set of encoded binary words is considered. The encoding assumes that different binary words will be encoded by different binary codes of shorter length. Code converters of this type are designed to reduce the length of binary words transmitted in digital systems over data buses when the bit depth of the transmitted words exceeds the bit depth of the data bus. For example, 18-bit or 17-bit words need to be transmitted over a 16-bit data bus. Each such word can be transmitted in two cycles of operation of a digital system; however, this approach reduces the overall performance of the system. One of the approaches to solve such problems is the development of combinational circuits that convert long binary encoded words into shorter ones. The proposed methods for solving the problem of synthesizing circuits of code converters are based on the compilation and logical minimization of such forms of systems of incompletely specified Boolean functions as disjunctive normal forms (DNFs) and binary decision diagrams called BDD representations. Using BDDs to minimize representations of k-valued functions that depend on Boolean variables is also proposed. Technology-independent logical minimization of functional descriptions of the designed code converters is proposed to be performed by programs for minimizing the systems of Boolean functions in the DNF class and programs for joint minimization of BDD representations of systems of completely specified Boolean functions. Minimization of functional descriptions is aimed at reducing the hardware complexity of combinational circuits in the basis of library elements or FPGA elements implementing code converters of the class in question. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to propose and explore a general framework within which a wide variety of model construction techniques from contemporary set theory can be subsumed. Taking our inspiration from presheaf constructions in category theory and Boolean ultrapowers, we will show that generic extensions, ultrapowers, extenders and generic ultrapowers can be construed as examples of a single model construction technique. In particular, we will show that Łoś's theorem can be construed as a specific case of Cohen's truth lemma, and we isolate the weakest conditions a filter must satisfy in order for the truth lemma to work. [ABSTRACT FROM AUTHOR]

This paper presents a novel method for testing Boolean expressions. It is based on spectral, aka Fourier analysis of Boolean functions which is exploited to generate test inputs. The approach has three important contributions: (i) It generates a relatively small test suite with a high capability of fault detection, (ii) The test suite is prioritized such that expected fault detection time is shorter, (iii) It is entirely mathematical relying on a simple and straightforward formula. The proposed method is formulated and evaluations are performed on both synthetic and real expressions. It is also compared with two common test generation criteria, MC/DC and Minimal MUMCUT. Evaluations show that the test suite generated by the spectral approach is relatively small while expressing the capability of a better and quicker fault detection. The approach presented in this paper provides a useful insight into how spectral/Fourier analysis of Boolean functions can be exploited in software testing. [ABSTRACT FROM AUTHOR]

In this paper, we first introduce a class of quartic Boolean functions. And then, the construction of weightwise perfectly balanced Boolean functions on $ 2^m $ variables are given by modifying the support of the quartic functions, where $ m $ is a positive integer. The algebraic degree, the weightwise nonlinearity, and the algebraic immunity of the newly constructed weightwise perfectly balanced functions are discussed at the end of this paper. [ABSTRACT FROM AUTHOR]

Boolean networks (BNs) are well-studied models of genomic regulation in biology where nodes are genes and their state transition is controlled by Boolean functions. We propose to learn Boolean functions as Boolean formulas in disjunctive normal form (DNFs) by an explainable neural network Mat_DNF and apply it to learning BNs. Directly expressing DNFs as a pair of binary matrices, we learn them using a single layer NN by minimizing a logically inspired non-negative cost function to zero. As a result, every parameter in the network has a clear meaning of representing a conjunction or literal in the learned DNF. Also we can prove that learning DNFs by the proposed approach is equivalent to inferring interpolants in logic between the positive and negative data. We applied our approach to learning three literature-curated BNs and confirmed its effectiveness. We also examine how generalization occurs when learning data is scarce. In doing so, we introduce two new operations that can improve accuracy, or equivalently generalizability for scarce data. The first one is to append a noise vector to the input learning vector. The second one is to continue learning even after learning error becomes zero. The first one is explainable by the second one. These two operations help us choose a learnable DNF, i.e., a root of the cost function, to achieve high generalizability. [ABSTRACT FROM AUTHOR]

Recently, balanced Boolean functions with an even number n of variables achieving very good autocorrelation properties have been obtained for 12 ≤ n ≤ 26 . These functions attain the maximum absolute value in the autocorrelation spectra (without considering the zero point) less than 2 n 2 and are found by using a heuristic search algorithm that is based on the design method of an infinite class of such functions for a higher number of variables. Here, we consider balanced Boolean functions that are closest to the bent functions in terms of the Hamming distance and perform a genetic algorithm efficiently aiming to optimize their cryptographic properties, which provides better absolute indicator values for all of those values of n for the first time. We also observe that among our results, the functions for 16 ≤ n ≤ 26 have nonlinearity greater than 2 n − 1 − 2 n 2 . In the process, our search strategy produces balanced Boolean functions with the best-known nonlinearity for 8 ≤ n ≤ 16 . [ABSTRACT FROM AUTHOR]

Many real-world voting systems consist of voters that occur in just two different types. Indeed, each voting system with a "House" and a "Senate" is of that type. Here we present structural characterizations and an explicit enumeration formula for these so-called bipartite simple games. This formula extends some partial enumerations of simple games related to completeness or the number of minimal winning coalitions. [ABSTRACT FROM AUTHOR]

The influence of a variable is an important concept in the analysis of Boolean functions. The more general notion of influence of a set of variables on a Boolean function has four separate definitions in the literature. In the present work, we introduce a new definition of influence of a set of variables which is based on the auto-correlation function and develop its basic theory. Among the new results that we obtain are generalizations of the Poincar\'e inequality and the edge expansion property of the influence of a single variable. Further, we obtain new characterizations of resilient and bent functions using the notion of influence. We show that the previous definition of influence due to Fischer et al. [Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), Vancouver, BC, Canada, IEEE Computer Society, 2002, pp. 103--112] and Blais [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, M. Mitzenmacher, ed., Bethesda, MD, ACM, 2009, pp. 151--158] is half the value of the auto-correlation based influence that we introduce. Regarding the other prior notions of influence, we make a detailed study of these and show that each of these definitions does not satisfy one or more desirable properties that a notion of influence may be expected to satisfy. [ABSTRACT FROM AUTHOR]

This paper presents power analysis of the seven full adder cells reported as having a low PDP (Power Delay Product), by means of speed, power consumption and area. These full adders were designed upon various logic styles to derive the sum and carry outputs. All these full adders designed using TDK 90 nm Technology and simulated using mentor graphics EDA tool with BSIMv3 (model 49). And the layouts of all these full adders designed in Icstation of Mentor Graphics. [ABSTRACT FROM AUTHOR]

This paper consists of two independent, but related parts. In the first part we show how to use symbolic computation to derive explicit expressions for the first few moments of the number of implicants that a random Boolean function has, or equivalently the number of fixeddimensional subcubes contained in a random subset of the n-dimensional cube. These explicit expressions suggest, but do not prove, that these random variables are always asymptotically normal. The second part presents a full, human-generated proof, of this asymptotic normality, first proved by Urszula Konieczna. [ABSTRACT FROM AUTHOR]

When analyzing the security of block ciphers and stream ciphers, the r - t h order nonlinearity of a Boolean function is crucial. They also have a prominent place in coding theory because the r - t h order nonlinearity of Boolean functions is connected to the covering radius of R M (r , m) , i.e., Reed-Muller code. In this study, we determine the lower bound for the higher-order nonlinearity of the two classes of Boolean functions listed below. f α (u) = t r 1 m (α u d) , where d is the Niho exponent constructed by Dobbertin et al. (J. Comb. Theory Ser. A 113:779–798, 2006). g α (u) = t r 1 m (α u d) , where d = 2 p - 2 . For all u ∈ F 2 m , α ∈ F 2 m ∗ and m = 2 p . [ABSTRACT FROM AUTHOR]

This work surveys mathematical aspects of division property, which is a state-of-the-art technique in cryptanalysis of symmetric-key algorithms, such as authenticated encryption, block ciphers and stream ciphers. It aims to find integral distinguishers and cube attacks, which exploit weaknesses in the algebraic normal forms of the output coordinates of the involved vectorial Boolean functions. Division property can also be used to provide arguments for security of primitives against these attacks. The focus of this work is a formal presentation of the theory behind the division property, including rigorous proofs, which were often omitted in the existing literature. This survey covers the two major variants of division property, namely conventional and perfect division property. In addition, we explore relationships of the technique with classic degree bounds. [ABSTRACT FROM AUTHOR]

Encoding a dictionary into another representation means that all the words can be stored in the dictionary in a more efficient way. In this way, we can complete common operations in dictionaries, such as (1) searching for a word in the dictionary, (2) adding some words to the dictionary, and (3) removing some words from the dictionary, in a shorter time. Binary decision diagrams (BDDs) are one of the most famous representations of such encoding and are widely popular due to their excellent properties. Recently, some people have proposed encoding dictionaries into BDDs and some variants of BDDs and showed that it is feasible. Hence, we further investigate the topic of encoding dictionaries into decision diagrams. Tagged sentential decision diagrams (TSDDs), as one of these variants based on structured decomposition, exploit both the standard and zero-suppressed trimming rules. In this paper, we first introduce how to use Boolean functions to represent dictionary files and then design an algorithm that encodes dictionaries into TSDDs with the help of tries and a decoding algorithm that restores TSDDs to dictionaries. We utilize the help of tries in the encoding algorithm, which greatly accelerates the encoding process. Considering that TSDDs integrate two trimming rules, we believe that using TSDDs to represent dictionaries would be more effective, and the experiments also show this.

The method of Boolean function representation in terms of positional logic algebra in compact operator form is offered. Compared with the known method, it uses position operators with a complexity of no more than two and only one type of equivalent transformations. The method is less labor intensive. It allows parallelizing logic calculations. The corresponding way of Boolean function implementation is developed. It competes with some known ways in terms of hardware complexity, resource intensity, and speed when implemented on an FPGA basis. Possibilities open up for creating effective automating means of representing Boolean functions from a large number of variables, synthesizing the corresponding LCs, and improving modern element bases.

We consider the class of separable k -hypergraphs, which can be viewed as uniform analogs of threshold Boolean functions, and the class of equatable k -hypergraphs. We show that every k -hypergraph is either separable or equatable but not both. We raise several questions asking which classes of equatable (and separable) hypergraphs enjoy certain appealing characterizing properties, which can be viewed as uniform analogs of the 2-summable and 2-monotone Boolean function properties. In particular, we introduce the property of exchangeability , and show that all these questioned characterizations hold for graphs, multipartite k -hypergraphs for all k , paving k -matroids and binary k -matroids for all k , and 3-matroids, which are all equatable if and only if they are exchangeable. We also discuss the complexity of deciding if a hypergraph is separable, and in particular, show that it requires exponential time for paving matroids presented by independence oracles, and can be done in polynomial time for binary matroids presented by such oracles. [ABSTRACT FROM AUTHOR]

A novel image cryptographic scheme is introduced in this paper. The proposed method incorporates two modules: confusion module and diffusion module. A dynamic key, changed for every input image is generated, and employed as a base to produce sub-keys in both confusion and diffusion mechanisms. This dynamics conducted to random-like key-generation, rendered the cryptographic scheme with dynamic encryption structure, and hence only one round is needed to achieve good combination between efficient time-consuming and sufficient security. In the confusion module, pixels' positions are non-linearly first forwardly permuted and then backwardly permuted, without changing their values, aiming to de-correlate the relations among neighboring pixels. In the diffusion module, pixels' values are changed, firstly discrete dynamical system with delay defined by non-linear boolean function is employed, in which each pixel value is non-linearly modified to achieve the mixing effect of pixel value and introduce more the non-linearity property, and then memory reversible two-dimensional cellular automata is performed, in which each pixel value is sequentially modified to further attain high diffusion mechanism. We have conducted the most important experiments to assess the effectiveness of the proposed cryptographic scheme. The obtained results are interesting in terms of security degrees and time-consuming, and point to the advocacy of proposal and its suitability to be a good encryption candidate for constrained environments. [ABSTRACT FROM AUTHOR]

The functional system of Boolean vector functions with the naturally defined superposition operation is considered. It is shown that every closed class of this system admits a finite basis. [ABSTRACT FROM AUTHOR]

The problem of computing the Elementary Flux Modes (EFMs) and Minimal Cut Sets (MCSs) of metabolic network is a fundamental one in metabolic networks. A key insight is that they can be understood as a dual pair of monotone Boolean functions (MBFs). Using this insight, this computation reduces to the question of generating from an oracle a dual pair of MBFs. If one of the two sets (functions) is known, then the other can be computed through a process known as dualization. Fredman and Khachiyan provided two algorithms, which they called simply A and B that can serve as an engine for oracle-based generation or dualization of MBFs. We look at efficiencies available in implementing their algorithm B, which we will refer to as FK-B. Like their algorithm A, FK-B certifies whether two given MBFs in the form of Conjunctive Normal Form and Disjunctive Normal Form are dual or not, and in case of not being dual it returns a conflicting assignment (CA), that is, an assignment that makes one of the given Boolean functions True and the other one False. The FK-B algorithm is a recursive algorithm that searches through the tree of assignments to find a CA. If it does not find any CA, it means that the given Boolean functions are dual. In this article, we propose six techniques applicable to the FK-B and hence to the dualization process. Although these techniques do not reduce the time complexity, they considerably reduce the running time in practice. We evaluate the proposed improvements by applying them to compute the MCSs from the EFMs in the 19 small- and medium-sized models from the BioModels database along with 4 models of biomass synthesis in Escherichia coli that were used in an earlier computational survey Haus et al. (2008). [ABSTRACT FROM AUTHOR]

Recently, a framework for employing the Gowers U 2 norm in the context of (generalized) Boolean functions with cryptographic significance was introduced. In this paper, we first give tight bounds on the Gowers U 2 norm of generalized Boolean functions via the (generalized) sum-of-squares indicator. Secondly, we provide a framework for the generalized signal-to-noise ratio ( ℛ) of generalized (n , m) -functions. We characterize the ℛ in terms of the Gowers U 2 norm. In particular, we present a direct link between the ℛ of a class of generalized Boolean functions and the ℛ of its component Boolean functions. Finally, the expressions of the Gowers U 2 norm of generalized Boolean functions from some well-known secondary constructions (the concatenation and Carlet's construction) are obtained. [ABSTRACT FROM AUTHOR]

Despite the more handy terminology of abstract simplicial complexes , in its core this article is about antitone Boolean functions. Given the maximal faces (=facets) of , our main algorithm, called Facets-To-Faces, outputs in a compressed format. The degree of compression of Facets-To-Faces, which is programmed using the high-level programming language Mathematica, compares favorably to both the hardwired Mathematica command BooleanConvert, and to the hardwired binary decision diagrams provided by Python. A novel way to calculate the face-numbers from the facets is also presented. Both algorithms can be parallelized and are applicable (e.g.) to reliability analysis, combinatorial topology, and frequent-set-mining. [ABSTRACT FROM AUTHOR]

Motivation Boolean networks are simple but efficient mathematical formalism for modelling complex biological systems. However, having only two levels of activation is sometimes not enough to fully capture the dynamics of real-world biological systems. Hence, the need for multi-valued networks (MVNs), a generalization of Boolean networks. Despite the importance of MVNs for modelling biological systems, only limited progress has been made on developing theories, analysis methods, and tools that can support them. In particular, the recent use of trap spaces in Boolean networks made a great impact on the field of systems biology, but there has been no similar concept defined and studied for MVNs to date. Results In this work, we generalize the concept of trap spaces in Boolean networks to that in MVNs. We then develop the theory and the analysis methods for trap spaces in MVNs. In particular, we implement all proposed methods in a Python package called trapmvn. Not only showing the applicability of our approach via a realistic case study, we also evaluate the time efficiency of the method on a large collection of real-world models. The experimental results confirm the time efficiency, which we believe enables more accurate analysis on larger and more complex multi-valued models. Availability and implementation Source code and data are freely available at https://github.com/giang-trinh/trap-mvn. [ABSTRACT FROM AUTHOR]

Boolean expressions are highly involved in control flows of programs and software specifications. Coverage criteria for Boolean expressions aim at producing minimal test suites to detect software faults. There exist various testing criteria, efficiency of which is usually evaluated through mutation analysis. This paper proposes an integer programming-based minimal test suite generation technique relying on mutation analysis. The proposed technique also takes into account the cost of fault detection. The technique is optimal such that the resulting test suite guarantees to detect all the mutants under given fault assumptions, while maximizing the average percentage of fault detection of a test suite. Therefore, the approach presented can also be considered as a reference method to check the efficiency of any common technique. The method is evaluated using four well-known real benchmark sets of Boolean expressions and is also exemplary compared with MCDC criterion. The results show that the test suites generated by the proposed method provide better fault coverage values and faster fault detection. [ABSTRACT FROM AUTHOR]

Boolean satisfiability (SAT) is widely used as a solver engine in electronic design automation (EDA). Typically, SAT is used to determine whether one or more groups of variables can be combined to form a true formula. All solutions SAT (AllSAT) is a variant of the SAT problem. In the fields of formal verification and pattern generation, AllSAT is particularly useful because it efficiently enumerates all possible solutions. In this paper, a semi-tensor product (STP) based AllSAT solver is proposed. The solver can solve instances described in both the conjunctive normal form (CNF) and circuit form. The implementation of our method differs from incremental enumeration because we do not add blocking conditions for existing solutions, but rather compute the matrices to obtain all the solutions in one pass. Additionally, the logical matrices support a variety of logic operations. Results from experiments with MCNC benchmarks using CNF-based and circuit-based forms show that our method can accelerate CPU time by 8.1x (238x maximum) and 19.9x (72x maximum), respectively. [ABSTRACT FROM AUTHOR]

The construction and development of new techniques for a nonlinear multivalued Boolean function is one of the important aspects of modern ciphers. These multivalued Boolean functions need to be defined over various algebraic structures which map multiple inputs on multiple outputs. Modern block ciphers are a combination of linear and nonlinear functions which adds diffusion and confusion capabilities. We have offered an innovative system for the construction of the confusion component of block cipher by using recurrent neural networks. Since the confusion component is a multivalued Boolean function, therefore, we need many to many types of recurrent networks with an equal number of inputs and outputs. With this scheme, we have achieved a standard benchmark nonlinear of 112 with balancednesss having low linear and differential probabilities. We evaluated some common and advanced measures for the eminence of randomness and cryptanalytics to observe the efficiency of the proposed methodology. These outcomes validated the generated nonlinear confusion components are effective for block ciphers and have better cryptographic strength in image encryption with a high signal-to-noise ratio in comparison to state-of-the-art techniques. [ABSTRACT FROM AUTHOR]

A Boolean function in $ n $ variables is 2-rotation symmetric if it is invariant under even powers of $ \rho(x_1, \ldots, x_n) = (x_2, \ldots, x_n, x_1) $, but not under the first power (ordinary rotation symmetry); we call such a function a 2-function. A 2-function is called monomial rotation symmetric (MRS) if it is generated by applying powers of $ \rho^2 $ to a single monomial. If the quartic MRS 2-function in $ 2n $ variables has a monomial $ x_1 x_q x_r x_s $, then we use the notation $ {2-}(1,q,r,s)_{2n} $ for the function. A detailed theory of equivalence of quartic MRS 2-functions in $ 2n $ variables was given in a $ 2020 $ paper by Cusick, Cheon and Dougan. This theory divides naturally into two classes, called $ mf1 $ and $ mf2 $ in the paper. After describing the equivalence classes, the second major problem is giving details of the linear recursions that the Hamming weights for any sequence of functions $ {2-}(1,q,r,s)_{2n} $ (with $ q < r < s, $ say), $ n = s, s+1, \ldots $ can be shown to satisfy. This problem was solved for the $ mf1 $ case only in the $ 2020 $ paper. Using new ideas about 'short' functions, Cusick and Cheon found formulas for the $ mf2 $ weights in a $ 2021 $ sequel to the $ 2020 $ paper. In this paper the actual recursions for the weights in the $ mf2 $ case are determined. [ABSTRACT FROM AUTHOR]

Graph states are present in quantum information and found applications ranging from quantum network protocols (like secret sharing) to measurement based quantum computing. In this paper, we extend the notion of graph states, which can be regarded as pure quantum graph states, or as homogeneous quadratic Boolean functions associated to simple undirected graphs, to quantum states based on mixed graphs (graphs which allow both directed and undirected edges), obtaining mixed quantum states, which are defined by matrices associated to the measurement of homogeneous quadratic Boolean functions in some (ancillary) variables. In our main result, we describe the extended graph state as the sum of terms of a commutative subgroup of the stabilizer group of the corresponding mixed graph with the edges' directions reversed. [ABSTRACT FROM AUTHOR]

Boosted by cryptography and coding theory applications and rich connections to objects from geometry and combinatorics, bent functions and related functions developed into a lively research area. In the mid-seventies, Rothaus initially introduced bent functions in the Boolean case, but later, they extended in the p-ary case where p is any prime. Such an extension brought more rich connections to bent functions. In addition to the theory of Fourier transform, handling p-ary bent functions (where p is an odd prime), analyzing their properties and designing them require using the theory of cyclotomic fields. Such a family is classified into weakly regular bent and regular bent. Compared to the Boolean case, the class of p-ary bent functions inherits a much larger variety of properties. For example, it contains the class of dual-bent functions as a proper subclass, which again includes weakly regular bent functions as a proper subclass. Weakly regular bent functions can also be employed in many domains. In particular, they have been widely used in designing good linear codes for several applications (such as secret sharing and two-party computation), association schemes, and strongly regular graphs. More exploration is still needed despite a lot of interest and attention in this topic to increase our knowledge of bent functions and design them. In particular, only a few constructions of weakly regular bent functions have been presented in the literature. Nice construction methods of these functions have been given by Tang et al (IEEE Trans Inf Theory 62(3):1166–1176, 2016). All the known infinite families of weakly regular bent functions belong to a class (denoted by Tang et al. in the previous reference) R F . This paper is devoted to weakly regular bent functions, and its objective is twofold. First, it aims to generate new infinite families of weakly regular bent functions living outside R F and secondly, to exploit the constructed functions to design new families of p-ary linear codes and investigate their use for some standard application after studying this minimality based on their weight distributions. More specifically, we present several classes of weakly regular bent functions obtained from monomial bent functions by modifying the values of some known weakly regular bent functions on some subsets of the finite field F p n (n is a positive integer). Our weakly regular bent functions are of degree either p or p + 1 2 . We also explicitly determine their corresponding dual functions. Finally, we exploit our constructions to derive four new classes of linear codes with three to seven weights. We also show that two of them lead to minimal codes, which are more appropriate for several concrete applications. [ABSTRACT FROM AUTHOR]

• Physical behaviors of memristive systems can be related to the bio-physical dynamics of biological neural elements. • Spiking behaviors subject to input stimuli of LIF neurons made of memristive elements can be extrapolated to develop on-chip learning algorithms. • Rate coding is a viable alternative to temporal or population coding for in-hardware SNNs. • It is possible to perform a non-linear functions like XOR using a single neuron in SNNs. • A hybrid approach relying on ANN like gradient calculation can be used to learn in SNNs. Neuromorphic computing is a novel computing paradigm that aims to mimic the behavior of biological neural networks for efficiently solving complex problems. While CMOS based neurons and synapses have been developed, they are limited in their ability to demonstrate bio-realistic dynamics. This, coupled with the fact that a huge number of these individual devices are required to build neurons and synapses, limits the scaling and power efficiency of such systems. A viable answer to this problem is neuromemristive systems that are based on memristor devices. These devices exhibit physical behaviors that can be related to the bio-physical dynamics of synapses and neurons. In this paper, a rate-coded all memristive "spiking neural network" (SNN) is presented. The proposed SNN is built with an active memristor neuron based on vanadium dioxide (VO 2) coupled with a non-volatile memristor synapse. The results are validated by first simulating spiking versions of two Boolean functions viz., AND and XOR gates in SPICE. With features extracted from the small neural nets, a large-scale 3-layer spiking neural network is then simulated in Python which yields a validation accuracy of 87% on the MNIST dataset of handwritten digits. One of the prime features of this work is the realization of the XOR function using a single neuron which is not possible without the use of 2-layers of neurons in traditional neural networks. Another significant contribution is the utilization of a gradient-based learning approach for online training of a large-scale SNN. For this, we use the inherent activation function (Sigmoid/ReLU) of the proposed neuron design. [ABSTRACT FROM AUTHOR]

Boolean models are a well-established framework to model developmental gene regulatory networks (DGRNs) for acquisition of cellular identities. During the reconstruction of Boolean DGRNs, even if the network structure is given, there is generally a large number of combinations of Boolean functions that will reproduce the different cell fates (biological attractors). Here we leverage the developmental landscape to enable model selection on such ensembles using the relative stability of the attractors. First we show that previously proposed measures of relative stability are strongly correlated and we stress the usefulness of the one that captures best the cell state transitions via the mean first passage time (MFPT) as it also allows the construction of a cellular lineage tree. A property of great computational importance is the insensitivity of the different stability measures to changes in noise intensities. That allows us to use stochastic approaches to estimate the MFPT and thereby scale up the computations to large networks. Given this methodology, we revisit different Boolean models of Arabidopsis thaliana root development, showing that a most recent one does not respect the biologically expected hierarchy of cell states based on relative stabilities. We therefore developed an iterative greedy algorithm that searches for models which satisfy the expected hierarchy of cell states and found that its application to the root development model yields many models that meet this expectation. Our methodology thus provides new tools that can enable reconstruction of more realistic and accurate Boolean models of DGRNs. [ABSTRACT FROM AUTHOR]

Motivation From a systematic perspective, it is crucial to infer and analyze gene regulatory network (GRN) from high-throughput single-cell RNA sequencing data. However, most existing GRN inference methods mainly focus on the network topology, only few of them consider how to explicitly describe the updated logic rules of regulation in GRNs to obtain their dynamics. Moreover, some inference methods also fail to deal with the over-fitting problem caused by the noise in time series data. Results In this article, we propose a novel embedded Boolean threshold network method called LogBTF, which effectively infers GRN by integrating regularized logistic regression and Boolean threshold function. First, the continuous gene expression values are converted into Boolean values and the elastic net regression model is adopted to fit the binarized time series data. Then, the estimated regression coefficients are applied to represent the unknown Boolean threshold function of the candidate Boolean threshold network as the dynamical equations. To overcome the multi-collinearity and over-fitting problems, a new and effective approach is designed to optimize the network topology by adding a perturbation design matrix to the input data and thereafter setting sufficiently small elements of the output coefficient vector to zeros. In addition, the cross-validation procedure is implemented into the Boolean threshold network model framework to strengthen the inference capability. Finally, extensive experiments on one simulated Boolean value dataset, dozens of simulation datasets, and three real single-cell RNA sequencing datasets demonstrate that the LogBTF method can infer GRNs from time series data more accurately than some other alternative methods for GRN inference. Availability and implementation The source data and code are available at https://github.com/zpliulab/LogBTF. [ABSTRACT FROM AUTHOR]

Various systematic modifications of vectorial Boolean functions have been used for finding new previously unknown classes of S-boxes with good or even optimal differential uniformity and nonlinearity. In this paper, a new general modification method is given that preserves the bijectivity property of the function in case the inverse of the function admits a linear structure. A previously known construction of such a modification based on bijective Gold functions in odd dimension is a special case of the new method. [ABSTRACT FROM AUTHOR]

To date, we know only a few handcrafted quantified Boolean formulas (QBFs) that are hard for central QBF resolution systems such as Q-Res and QU-Res, and only one specific QBF family to separate Q-Res and QU-Res. Here we provide a general method to construct hard formulas for Q-Res and QU-Res. The construction uses simple propositional formulas (e.g. minimally unsatisfiable formulas) in combination with easy QBF gadgets (Sb 2 formulas without constant winning strategies). This leads to a host of new hard formulas, including new classes of hard random QBFs. We further present generic constructions for formulas separating Q-Res and QU-Res, and for separating Q-Res and LD-Q-Res. [ABSTRACT FROM AUTHOR]

The problem of computing the set of prime implicants to represent a Boolean function is a classical problem that is still considered a running problem for research because all known approaches have limitations. The article reviews existing methods for computing prime implicants and highlights their limitations, particularly for multi-output functions and limited scalability due to the growth in memory required to complete the computation. Then it proposes a recursive ternary-based minimization algorithm to compute the prime implicants of multioutput Boolean functions. The algorithm is based on the concept of Programmable Logic Array (PLA) tables, which provide a structured and efficient representation of Boolean functions. The algorithm takes advantage of the ternary logic system to efficiently compute the prime implicants while maintaining scalability for large and complex functions, which has significant implications for digital circuit design and optimization. [ABSTRACT FROM AUTHOR]