Search

A constraint satisfaction problem (CSP), \(\textsf {Max-CSP}(\mathcal {F})\) , is specified by a finite set of constraints \(\mathcal {F}\subseteq \lbrace [q]^k \rightarrow \lbrace 0,1\rbrace \rbrace\) for positive integers q and k. An instance of the problem on n variables is given by m applications of constraints from \(\mathcal {F}\) to subsequences of the n variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the (γ ,β)-approximation version of the problem for parameters 0 ≤ β ≤ γ ≤ 1, the goal is to distinguish instances where at least γ fraction of the constraints can be satisfied from instances where at most β fraction of the constraints can be satisfied. In this work, we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family \(\mathcal {F}\) and every β < γ, we show that either a linear sketching algorithm solves the problem in polylogarithmic space or the problem is not solvable by any sketching algorithm in \(o(\sqrt {n})\) space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of q=k=2, where we get a dichotomy, and the case when the satisfying assignments of the constraints of \(\mathcal {F}\) support a distribution on \([q]^k\) with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables q = 2, binary constraints k =2, and singleton families \(|\mathcal {F}|=1\) and only considered the setting where constraints are placed on literals rather than variables. Our positive results show wide applicability of bias-based algorithms used previously by [47] and [41], which we extend to include richer norm estimation algorithms, by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [56], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. In particular, previous works used Fourier analysis over the Boolean cube to initiate their results and the results seemed particularly tailored to functions on Boolean literals (i.e., with negations). Our techniques surprisingly allow us to get to general q-ary CSPs without negations by appealing to the same Fourier analytic starting point over Boolean hypercubes. [ABSTRACT FROM AUTHOR]

Linear codes play a crucial role in various fields of engineering and mathematics, including data storage, communication, cryptography, and combinatorics. Minimal linear codes, a subset of linear codes, are particularly essential for designing effective secret sharing schemes. In this paper, we introduce several classes of minimal binary linear codes by carefully selecting appropriate Boolean functions. These functions belong to a renowned class of Boolean functions, namely, the general Maiorana–McFarland class. We employ a method first proposed by Ding et al. (IEEE Trans Inf Theory 64(10):6536–6545, 2018) to construct minimal codes violating the Ashikhmin–Barg bound (wide minimal codes) by using Krawtchouk polynomials. The lengths, dimensions, and weight distributions of the obtained codes are determined using the Walsh spectrum distribution of the chosen Boolean functions. Our findings demonstrate that a vast majority of the newly constructed codes are wide minimal. Furthermore, our proposed codes exhibit a significantly larger minimum distance, in some cases, compared to some existing similar constructions. Finally, we address this method, based on Krawtchouk polynomials, more generally, and highlight certain generic properties related to it. These general results offer insights into the scope of this approach. [ABSTRACT FROM AUTHOR]

A neuron with binary inputs and a binary output represents a Boolean function. Our goal is to extract this Boolean function into a tractable representation that will facilitate the explanation and formal verification of a neuron's behavior. Unfortunately, extracting a neuron's Boolean function is in general an NP-hard problem. However, it was recently shown that prime implicants of this Boolean function can be enumerated efficiently, with only polynomial time delay. Building on this result, we first propose a best-first search algorithm that is able to incrementally tighten the inner and outer bounds of a neuron's Boolean function. Second, we show that these bounds correspond to truncated prime-implicant covers of the Boolean function. Next, we show how these bounds can be propagated in an elementary class of neural networks. Finally, we provide case studies that highlight our ability to bound the behavior of neurons. [ABSTRACT FROM AUTHOR]

Determining the weight distribution of all Reed-Muller codes is a huge and exciting problem that has been around since the sixties. Some progress has been made very recently, but we are still far from a solution. In this paper, we addressed the subproblem of determining as many codeword weights as possible in Reed-Muller codes of any lengths and any orders, which is decisive for determining their weight spectra (i.e., the lists of all possible weights in these codes). New approaches seem necessary for both the main problem and the subproblem. We first studied the difficulties and the limits of the approach, which consisted of using the usual primary and secondary constructions of Boolean functions for the purpose of determining as many weights as possible in Reed-Muller codes. We then introduced a way, different from the usual constructions, to generate Boolean functions in n variables having an algebraic degree bounded from above, without any restriction on n, and whose Hamming weights can be determined. This provided weights in Reed-Muller codes of any lengths 2n and any orders, allowing us to reach potentially new values in the weight spectra of Reed-Muller codes (as we illustrate with all Reed-Muller codes of lengths up to 221), with the related codewords being given with their supports and their algebraic normal forms being mathematically derived. [ABSTRACT FROM AUTHOR]

A functionally complete Boolean operator is sufficient for computational circuits of arbitrary complexity. We connected YES (buffer) with NOT (inverter) and two NOT four-way junction (4J) DNA gates to obtain IMPLY and NAND Boolean functions, respectively, each of which represents a functionally complete gate. The results show a technological path towards creating a DNA computational circuit of arbitrary complexity based on singleton NOT or a combination of NOT and YES gates, which is not possible in electronic computers. We, therefore, concluded that DNA-based circuits and molecular computation may offer opportunities unforeseen in electronics. [ABSTRACT FROM AUTHOR]

In design of secure cryptosystems and CDMA communications, the negabent functions play a significant role. The generalized Boolean functions have been extensively studied by Schmidt and established several important results in this setup. In this paper, several characteristics of the generalized nega-Hadamard transform (GNT) of generalized Boolean functions like inverse of GNT, generalized nega-cross correlation, generalized nega-Parseval's identity, relationship between GNT and generalized nega-cross correlation have analyzed. We studied the GNT for the derivative of this setup of functions and established the connection of generalized Walsh-Hadamard transform and GNT of derivatives of these functions. Also, the GNT of composition of vectorial Boolean function and generalized Boolean function is presented. Further, the generalized nega-convolution theorem for generalized Boolean function is obtained. [ABSTRACT FROM AUTHOR]

In computer science, a binary decision diagram is a data structure that is used to represent a Boolean function and to consider a compressed representation of relations. This paper considers the notation of T.B.T (total binary truth table), and introduces a novel concept of binary decision (hyper)tree and binary decision (hyper)diagram, directly and in as little time as possible, unlike previous methods. This study proves that every T.B.T corresponds to a binary decision (hyper)tree via minimum Boolean expression and presents some conditions on any given T.B.T for isomorphic binary decision (hyper)trees. Finally, for faster calculations and more complex functions, we offer an algorithm and so Python programming codes such that for any given T.B.T, it introduces a binary decision (hyper)tree. [ABSTRACT FROM AUTHOR]

In this article, we investigate meandric systems having one shallow side: the arch configuration on that side has depth at most two. This class of meandric systems was introduced and extensively examined by I. P. Goulden, A. Nica, and D. Puder [Int. Math. Res. Not. IMRN 2020 (2020), 983-1034]. Shallow arch configurations are in bijection with the set of interval partitions. We study meandric systems by using moment-cumulant transforms for noncrossing and interval partitions, corresponding to the notions of free and Boolean independence, respectively, in non-commutative probability. We obtain formulas for the generating series of different classes of meandric systems with one shallow side by explicitly enumerating the simpler, irreducible objects. In addition, we propose random matrix models for the corresponding meandric polynomials, which can be described in the language of quantum information theory, in particular that of quantum channels. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Donghua University (English Edition) is the property of Journal of Donghua University Editorial Board and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Memristors are considered promising energy-effcient artificial intelligence hardware, which can eliminate the von Neumann bottleneck by parallel in-memory computing. The common imperfection-enabled memristors are plagued with critical variability issues impeding their commercialization. Reported approaches to reduce the variability usually sacrifice other performances, e.g., small on/off ratios and high operation currents. Here, we demonstrate an unconventional Ag-doped nonimperfection diffusion channel-enabled memristor in van der Waals indium phosphorus sulfide, which can combine ultralow variabilities with desirable metrics. We achieve operation voltage, resistance, and on/off ratio variations down to 3.8, 2.3, and 6.9% at their extreme values of 0.2 V, 1011 ohms, and 108, respectively. Meanwhile, the operation current can be pushed from 1 A to 1 pA at the scalability limit of 6 nm after Ag doping. Fourteen Boolean logic functions and convolutional image processing are successfully implemented by the memristors, manifesting the potential for logic-in-memory devices and effcient non-von Neumann accelerators. [ABSTRACT FROM AUTHOR]

A special class of monotone Boolean functions coming from shadow minimization theory of finite set-systems – KK-MBF functions – is considered. These functions are a descriptive model for systems of compatible groups of constraints, however, the class of all functions is unambiguously complex and it is sensible to study relatively simple subclasses of functions such as KK-MBF. Zeros of KK-MBF functions correspond to initial segments of lexicographic order on hypercube layers. This property is used to simplify the recognition. Lexicographic order applies priorities over constraints which is applicable property of practices. Query-based algorithms for KK-MBF functions are investigated in terms of their complexities. [ABSTRACT FROM AUTHOR]

Vectorial Boolean functions and codes are closely related and interconnected. On the one hand, various requirements of binary linear codes are needed for their theoretical interests but, more importantly, for their practical applications (such as few-weight codes or minimal codes for secret sharing, locally recoverable codes for storage, etc.). On the other hand, various criteria and tables have been introduced to analyse the security of S-boxes that are related to vectorial Boolean functions, such as the Differential Distribution Table (DDT), the Boomerang Connectivity Table (BCT), and the Differential-Linear Connectivity Table (DLCT). In previous years, two new tables have been proposed for which the literature was pretty abundant: the c-DDT to extend the DDT and the c-BCT to extend the BCT. In the same vein, we propose extended concepts to study further the security of vectorial Boolean functions, especially the c-Walsh transform, the c-autocorrelation, and the c-differential-linear uniformity and its accompanying table, the c-Differential-Linear Connectivity Table (c-DLCT). We study the properties of these novel functions at their optimal level concerning these concepts and describe the c-DLCT of the crucial inverse vectorial (Boolean) function case. Finally, we draw new ideas for future research toward linear code designs. [ABSTRACT FROM AUTHOR]

In this article, we provide some new limiting laws related to the free multiplicative law of large numbers and involving free and Boolean additive convolutions. Some examples of these limiting laws are presented within the framework of non-commutative probability theory. [ABSTRACT FROM AUTHOR]

Aaronson defined Forrelation (2010) as a measure of correlation between a Boolean function f and the Walsh–Hadamard transform of another function g . In a recent work, we have studied different cryptographically important spectra of Boolean functions through the lens of Forrelation. In this paper, we explore a similar kind of correlation in terms of nega-Hadamard transform. We call it nega-Forrelation and obtain a more efficient sampling strategy for nega-Hadamard transform compared to the existing results. Moreover, we present an efficient sampling strategy for nega-crosscorrelation (and consequently nega-autocorrelation) spectra too, by tweaking the nega-Forrelation technique. Finally, we connect the hidden shift finding algorithm for bent functions (Rötteler, 2010) with the Forrelation algorithm and extend it for the negabent functions. [ABSTRACT FROM AUTHOR]

A Boolean function f on n variables is said to be a bent function if the absolute value of all its Walsh coefficients is 2 n / 2 . Our main result is a new asymptotic lower bound on the number of Boolean bent functions. It is based on a modification of the Maiorana–McFarland family of bent functions and recent progress in the estimation of the number of transversals in latin squares and hypercubes. By-products of our proofs are the asymptotics of the logarithm of the numbers of partitions of the Boolean hypercube into 2-dimensional affine and linear subspaces. [ABSTRACT FROM AUTHOR]

The Patterson–Wiedemann (PW) construction, which is defined for an odd number n of variables with n being the product of two distinct prime numbers p and q, can be interpreted as idempotent functions which are represented by the (d, r)-interleaved sequences formed by all-zero and all-one columns, where r = (2 p - 1) (2 q - 1) and d = (2 n - 1) r . We here study a modified form of the PW construction, which only requires 2 n - 1 (= d r) be a composite number, by relaxing the constraint on the values of d and r. We first elaborate on the case n = 15 and consider the functions corresponding to the (217, 151)-interleaved sequences. Taking into account those satisfying f (α) = f (α 2 k) for all α ∈ F 2 n in this scenario, where k is a fixed divisor of n, we obtain Boolean functions with nonlinearity 16268 exceeding the bent concatenation bound. Then we extend our study for the case n = 11 and obtain Boolean functions with nonlinearity 996 represented by the (89, 23)-interleaved sequences, which equals the best known nonlinearity result. In the process, we show that there is the possibility to exceed the best known nonlinearities using the functions corresponding to those interleaved sequences. [ABSTRACT FROM AUTHOR]

Recently, several interesting constructions of vectorial Boolean functions with the maximum number of bent components (MNBC functions, for short) were proposed. However, many of them have component functions from the completed Maiorana-McFarland class M # . Moreover, no examples of MNBC functions containing component functions provably outside M # are known. In this paper, we classify all MNBC functions in six variables. Based on the analysis of the obtained equivalence classes, we propose several infinite families of MNBC functions with component functions outside the M # class. In particular, two of our new constructions are solutions to the open problem [Bapić et al (eds) Proceedings of the twelfth international workshop on coding and cryptography, 2022, Item 1., p. 9]. [ABSTRACT FROM AUTHOR]

Legal text retrieval serves as a key component in a wide range of legal text processing tasks such as legal question answering, legal case entailment, and statute law retrieval. The performance of legal text retrieval depends, to a large extent, on the representation of text, both query and legal documents. Based on good representations, a legal text retrieval model can effectively match the query to its relevant documents. Because legal documents often contain long articles and only some parts are relevant to queries, it is quite a challenge for existing models to represent such documents. In this paper, we study the use of attentive neural network-based text representation for statute law document retrieval. We propose a general approach using deep neural networks with attention mechanisms. Based on it, we develop two hierarchical architectures with sparse attention to represent long sentences and articles, and we name them Attentive CNN and Paraformer. The methods are evaluated on datasets of different sizes and characteristics in English, Japanese, and Vietnamese. Experimental results show that: (i) Attentive neural methods substantially outperform non-neural methods in terms of retrieval performance across datasets and languages; (ii) Pretrained transformer-based models achieve better accuracy on small datasets at the cost of high computational complexity while lighter weight Attentive CNN achieves better accuracy on large datasets; and (iii) Our proposed Paraformer outperforms state-of-the-art methods on COLIEE dataset, achieving the highest recall and F2 scores in the top-N retrieval task. [ABSTRACT FROM AUTHOR]

We prove that if a Boolean function essentially depends on at least two variables, then it cannot be implemented by a circuit that consists of unreliable gates with at most two inputs each and is self-correcting with respect to at least some faults of an arbitrary number of gates. In view of the previous results, it suffices to establish this fact for linear functions. [ABSTRACT FROM AUTHOR]

Robustness of modern information confidentiality algorithm depends on its individual components. Modern block ciphers highly depend on two components namely confusion and diffusion. These two main characteristics in any modern cipher are achieved by substitution and permutation boxes. In this article, a decision-making algorithm is utilized for the selection of optimum substitution box (S-box), which plays a significant role in the field of information confidentiality. For this purpose, an interval-based Pythagorean fuzzy technique for order of preference by similarity to the ideal solution (IVPF–TOPSIS) method is introduced to get the desired nonlinear confusion component of block cipher namely S-box. In this manner, we performed cryptographic analyses of standard S-boxes namely nonlinearity (NL), strict avalanche criterion (SAC), bit-independent criterion (BIC), absolute indicator (ABI), the sum of square and absolute indicator (SSAI), algebraic degree (AD), algebraic immunity (AI), transparency order (TO), composite algebraic immunity (CAI), robustness (RB), signal to noise ratio (SNR), confusion coefficient of variance (CCV). With these cryptographic characteristics, we have used interval-valued based Pythagorean fuzzy TOPSIS multi-criteria decision-making technique to classify standard S-boxes suitable for construction of modern block ciphers. [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. [ABSTRACT FROM AUTHOR]

This is a survey of unconditional pseudorandom generators (PRGs). A PRG uses a short, truly random seed to generate a long, "pseudorandom" sequence of bits. To be more specific, for each restricted model of computation (e.g., bounded-depth circuits or read-once branching programs), we would like to design a PRG that "fools" the model, meaning that every function computable in the model behaves approximately the same when we plug in pseudorandom bits from the PRG as it does when we plug in truly random bits. In this survey, we discuss four major paradigms for designing PRGs: • We present several PRGs based on k -wise uniform generators, small-bias generators, and simple combinations thereof, including proofs of Viola's theorem on fooling low-degree polynomials [242] and Braverman's theorem on fooling AC 0 circuits [36]. • We present several PRGs based on "recycling" random bits to take advantage of communication bottlenecks, such as the Impagliazzo-Nisan-Wigderson generator [131]. • We present connections between PRGs and computational hardness, including the Nisan-Wigderson framework for converting a hard Boolean function into a PRG [183]. • We present PRG frameworks based on random restrictions, including the "polarizing random walks" framework [49]. We explain how to use these paradigms to construct PRGs that work unconditionally , with no unproven complexity-theoretic assumptions. The PRG constructions use ingredients such as finite field arithmetic, expander graphs, and randomness extractors. The analyses use techniques such as Fourier analysis, sandwiching approximators, and simplification-under-restrictions lemmas. [ABSTRACT FROM AUTHOR]

Bent functions are Boolean functions in even number of variables that have maximal nonlinearity. They have flat Walsh–Hadamard spectrum and are of interest for their applications in algebra, coding theory and cryptography. A bent function is called self-dual if it coincides with its dual bent function. In current work we study the decomposition of the form f 0 , f 1 , ... , f 2 k - 1 of the vector of values of a self-dual bent function, formed by the concatenation of 2 k Boolean functions f j in n - k variables. We treat the cases k = 1 , 2 . Based on a spectral characterization, we introduce a notion of self-dual near-bent function in odd number of variables and prove that there exists a one-to-one correspondence between the notions of self-duality for even and odd number of variables. As a result the characterization for the decomposition f 0 , f 1 is obtained. For the decomposition f = f 0 , f 1 , f 2 , f 3 we prove that if sign vectors of subfunctions f j are linearly dependent, then all these subfunctions are bent. We prove that for n ⩾ 6 the converse does not hold, that is the obtained condition is sufficient only. These results are also generalized for the case of an arbitrary bent function. Three new iterative constructions of self-dual bent functions are proposed. One of them allows to build a class of self-dual bent functions which cannot be decomposed into the concatenation of four bent functions. Based on the constructions a new iterative lower bound on the cardinality of the set of self-dual bent functions is obtained. [ABSTRACT FROM AUTHOR]

Amid efforts to address energy consumption in modern computing systems, one promising approach takes advantage of random networks of non-linear nanoscale junctions formed by nanoparticles as substrates for neuromorphic computing. These networks exhibit emergent complexity and collective behaviors akin to biological neural networks, characterized by self-organization, redundancy, and non-linearity. Based on this foundation, a generalization of n-inputs devices has been proposed, where the associated weights depend on all the input values. This model, called receptron, has demonstrated its capability to generate Boolean functions as output, representing a significant breakthrough in unconventional computing methods. In this work, we characterize and present two actual implementations of this paradigm. One approach leverages the nanoscale properties of cluster-assembled Au films, while the other utilizes the recently introduced Stochastic Resistor Network (SRN) model. We first provide a concise overview of the electrical properties of these systems, emphasizing the insights gained from the SRN regarding the physical processes within real nanostructured gold films at a coarse-grained scale. Furthermore, we present evidence indicating the minimum complexity level required by the SRN model to achieve a stochastic dynamics adequate to effectively model a novel component for logic systems. To support our argument that these systems are preferable to conventional random search algorithms, we discuss quantitative criteria based on Information-theoretic tools. This suggests a practical means to steer the stochastic dynamics of the system in a controlled way, thus focusing its random exploration where it is most useful.

Boolean functions form the fundamental components of symmetric cryptographic systems, serving as the building blocks. Modifying bent functions makes it feasible to design Boolean functions with desired properties that exhibit high non-linearity. The current study offers a comprehensive analysis of bent functions through its support, culminating in the introduction of an algorithm for the systematic construction of four variable bent functions. This algorithm enables the complete generation of all 896 four-variable bent functions. Furthermore, we introduce a methodology for constructing n-variable bent functions (where n > 4), leveraging both the algorithm and an established secondary technique for bent function construction. Lastly, we examine the estimation of the count of bent functions by utilising certain properties associated with the support of bent functions.

We test the quantumness of IBM's quantum computer IBM Quantum System One in Ehningen, Germany. We generate generalised n-qubit GHZ states and measure Bell inequalities to investigate the n-party entanglement of the GHZ states. The implemented Bell inequalities are derived from non-adaptive measurement-based quantum computation (NMQC), a type of quantum computing that links the successful computation of a non-linear function to the violation of a multipartite Bell-inequality. The goal is to compute a multivariate Boolean function that clearly differentiates non-local correlations from local hidden variables (LHVs). Since it has been shown that LHVs can only compute linear functions, whereas quantum correlations are capable of outputting every possible Boolean function it thus serves as an indicator of multipartite entanglement. Here, we compute various non-linear functions with NMQC on IBM's quantum computer IBM Quantum System One and thereby demonstrate that the presented method can be used to characterize quantum devices. We find a violation for a maximum of seven qubits and compare our results to an existing implementation of NMQC using photons. [ABSTRACT FROM AUTHOR]

The LogRank conjecture of Lovász and Saks (1988) is the most famous open problem in communication complexity theory. The statement is as follows: suppose that two players intend to compute a Boolean function f (x , y) when x is known for the first and y for the second player, and they may send and receive messages encoded with bits, then they can compute f (x , y) with exchanging (log   rank (M f)) c bits, where M f is a Boolean matrix, determined by function f. The problem is widely open and very popular, and it has resisted numerous attacks in the last 35 years. The best upper bound is still exponential in the bound of the conjecture. Unfortunately, we cannot prove the conjecture, but we present a communication protocol with (log   rank (M f)) c bits, which computes a (somewhat) related quantity to f (x , y) . The relation is characterized by the representation of low-degree, multi-linear polynomials modulo composite numbers. Our result may help to settle this long-open conjecture. [ABSTRACT FROM AUTHOR]

There are several goals of the two-dimensional data analysis: one may be interested in searching for groups of similar objects (clustering), another one may be focused on searching for some dependencies between a specified one and other variables (classification, regression, associate rules induction), and finally, some may be interested in serching for well-defined patterns in the data called biclusters. It was already proved that there exists a mathematically proven symmetry between some patterns in the matrix and implicants of data-defined Boolean function. This paper provides the new look for a specific pattern search—the pattern named the δ -shifting pattern. The shifting pattern is interesting, as it accounts for constant fluctuations in data, i.e., it captures situations in which all the values in the pattern move up or down for one dimension, maintaining the range amplitude for all the dimensions. Such a behavior is very common in real data, e.g., in the analysis of gene expression data. In such a domain, a subset of genes might go up or down for a subset of patients or experimental conditions, identifying functionally coherent categories. A δ -shifting pattern meets the necessity of shifting pattern induction together with the bias of the real values acquisition where the original shifts may be disturbed with some outer conditions. Experiments with a real dataset show the potential of our approach at finding biclusters with δ -shifting patterns, providing excellent performance. It was possible to find the 12 × 9 pattern in the 112 × 9 input data with M S R = 0.00653 . The experiments also revealed that δ -shifting patterns are quite difficult to be found by some well-known methods of biclustering, as these are not designed to focus on shifting patterns—results comparable due to M S R had much more variability (in terms of δ) than patterns found with Boolean reasoning. [ABSTRACT FROM AUTHOR]

Stream ciphers usually rely on highly secure Boolean functions to ensure safe communication within unsafe channels. However, discovering secure Boolean functions is a non-trivial optimization problem that has been addressed by many optimization techniques: in particular by evolutionary algorithms. We investigate in this article the employment of Genetic Programming (GP) for evolving Boolean functions with large non-linearity by examining the search space consisting of Walsh transforms. Especially, we build generic Walsh spectra starting from the evolution of Walsh transform coefficients. Then, by leveraging spectral inversion, we build pseudo-Boolean functions from which we are able to determine the corresponding nearest Boolean functions, whose computation involves filling via a random criterion a certain amount of "uncertain" positions in the final truth table. We show that by using a balancedness-preserving strategy, it is possible to exploit those positions to obtain a function that is as balanced as possible. We perform experiments by comparing different types of symbolic representations for the Walsh transform, and we analyze the percentage of uncertain positions. We systematically review the outcomes of these comparisons to highlight the best type of setting for this problem. We evolve Boolean functions from 6 to 16 bits and compare the GP-based evolution with random search to show that evolving Walsh transforms leads to highly non-linear functions that are balanced as well. [ABSTRACT FROM AUTHOR]

Domain insertion engineering is a promising approach to recombine the functions of evolutionarily unrelated proteins. Insertion of light‐switchable receptor domains into a selected effector protein, for instance, can yield allosteric effectors with light‐dependent activity. However, the parameters that determine domain insertion tolerance and allostery are poorly understood. Here, an unbiased screen is used to systematically assess the domain insertion permissibility of several evolutionary unrelated proteins. Training machine learning models on the resulting data allow to dissect features informative for domain insertion tolerance and revealed sequence conservation statistics as the strongest indicators of suitable insertion sites. Finally, extending the experimental pipeline toward the identification of switchable hybrids results in opto‐chemogenetic derivatives of the transcription factor AraC that function as single‐protein Boolean logic gates. The study reveals determinants of domain insertion tolerance and yielded multimodally switchable proteins with unique functional properties. [ABSTRACT FROM AUTHOR]

Boolean functions form the fundamental components of symmetric cryptographic systems, serving as the building blocks. Modifying bent functions makes it feasible to design Boolean functions with desired properties that exhibit high non-linearity. The current study offers a comprehensive analysis of bent functions through its support, culminating in the introduction of an algorithm for the systematic construction of four variable bent functions. This algorithm enables the complete generation of all 896 fourvariable bent functions. Furthermore, we introduce a methodology for constructing n-variable bent functions (where n > 4), leveraging both the algorithm and an established secondary technique for bent function construction. Lastly, we examine the estimation of the count of bent functions by utilising certain properties associated with the support of bent functions. [ABSTRACT FROM AUTHOR]

Extended Boolean functions (EBFs) are one of the most important tools in cryptography and spreading sequence design in communication systems. In this paper, we use EBFs to design new sets of spreading sequences for non-orthogonal multiple access (NOMA), which is an emerging technique capable of supporting massive machine-type communications (mMTC) in 5 G and beyond. In this work, first p-ary complementary sequences are constructed using EBFs and then, these sequences are used to design new sets of non-orthogonal spreading sequence sets having very low coherence and peak to average power ratio (PAPR). The proposed spreading sequence sets are capable of supporting a large number of active devices simultaneously. In fact, for a p-ary spreading sequence set, we theoretically achieve an overloading factor of 2p, where p is an odd prime. Specifically, for p = 3 , we achieve an overloading factor of 6, which cannot be achieved through the existing constructions till date. [ABSTRACT FROM AUTHOR]

The Möbius transform is a linear circuit used to compute the evaluations of a Boolean function over all points on its input domain. The operation is very useful in finding the solution of a system of polynomial equations over GF(2) for obvious reasons. However the operation, although linear, needs exponential number of logic operations (around n · 2n−1 bit xors) for an n-variable Boolean function. As such, the only known hardware circuit to efficiently compute the Möbius Transform requires silicon area that is exponential in n. For Boolean functions whose algebraic degree is bound by some parameter d, recursive definitions of the Möbius Transform exist that requires only O(nd+1) space in software. However converting the mathematical definition of this space-efficient algorithm into a hardware architecture is a non-trivial task, primarily because the recursion calls notionally lead to a depth-first search in a transition graph that requires context switches at each recursion call for which straightforward mapping to hardware is difficult. In this paper we look to overcome these very challenges in an engineering sense. We propose a space efficient sequential hardware circuit for the Möbius Transform that requires only polynomial circuit area (i.e. O(nd+1)) provided the algebraic degree of the Boolean function is limited to d. We show how this circuit can be used as a component to efficiently solve polynomial equations of degree at most d by using fast exhaustive search. We propose three different circuit architectures for this, each of which uses the Möbius Transform circuit as a core component. We show that asymptotically, all the solutions of a system of m polynomials in n unknowns and algebraic degree d over GF(2) can be found using a circuit of silicon area proportional to m · nd+1 and circuit depth proportional to 2 · log2(n − d). In the second part of the paper we introduce a fourth hardware solver that additionally aims to achieve energy efficiency. The main idea is to reduce the solution space to a small enough value by parallel application of Möbius Transform circuits over the first few equations of the system. This is done so that one can check individually whether the vectors of this reduced solution space satisfy each of the remaining equations of the system using lower power consumption. The new circuit has area also bound by m · nd+1 and has circuit depth proportional to d · log2 n. We also show that further optimizations with respect to energy consumption may be obtained by using depth-bound Möbius circuits that exponentially decrease run time at the cost of additional logic area and depth.

We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem. [ABSTRACT FROM AUTHOR]

How gene regulatory networks (GRNs) encode gene expression dynamics and how GRNs evolve are not well understood, although these problems have been studied extensively. We created a digital twin that accurately reproduces expression dynamics of 13 genes that initiate expression in 32-cell ascidian embryos. We first showed that gene expression patterns can be manipulated according to predictions by this digital model. Next, to simulate GRN rewiring, we changed regulatory functions that represented their regulatory mechanisms in the digital twin, and found that in 55 of 100 cases, removal of a single regulator from a conjunctive clause of Boolean functions did not theoretically alter qualitative expression patterns of these genes. In other words, we found that more than half the regulators gave theoretically redundant temporal or spatial information to target genes. We experimentally substantiated that the expression pattern of Nodal was maintained without one of these factors, Zfpm, by changing the upstream regulatory sequence of Nodal. Such robust buffers of regulatory mechanisms may provide a basis of enabling developmental system drift, or rewiring of GRNs without changing expression patterns of downstream genes, during evolution. Author summary: Although regulatory relationships in gene regulatory networks have been studied extensively during the past two decades, it is not fully understood how gene regulatory networks produce gene expression dynamics. One major reason is the difficulty of experimentally determining "regulatory functions" that mathematically describe how individual genes are regulated. Because of simplicity of embryonic structure and compactness of the genome, ascidian embryos provide an ideal system for analyzing dynamics of gene regulatory networks. In 32-cell ascidian embryos, there are only 13 regulatory genes that initiate expression. Regulatory functions for these genes, which are represented as Boolean functions, collectively constitute a digital twin that reproduces gene expression dynamics at single-cell resolution throughout the whole embryo. The digital twin is a powerful tool for exploring mechanisms that are not readily accessible in experiments using real embryos. We found that over half the regulators in regulatory functions are potentially redundant for specifying temporal and spatial gene expression patterns. It is generally believed that regulatory functions have changed frequently during evolution, and our results show that a gene regulatory network in early ascidian embryos has robust buffers, which constitute a basis for developmental system drift. [ABSTRACT FROM AUTHOR]

This work proposes a method for hardware reduction in circuits of Mealy finite state machines (FSMs). The circuits are implemented as networks of interconnected look-up table (LUT) elements. The FSMs with twofold state assignment and encoding of output collections are discussed. The method is based on using two LUT-based cores to implement systems of partial Boolean functions. One of the cores uses only maximum binary codes, while the second core is based on the use of extended state codes. The hardware reduction is based on diminishing the number of transformed maximum binary codes. This leads to FPGA-based FSM circuits with three levels of logic blocks. Each logic block has a single level of LUTs. As a result, partial functions are represented by single-LUT circuits. The article shows a step-by-step procedure for the transition from the initial form of the FSM representation to its logical circuit (a network of programmable look-up table elements, flip-flops, and interconnects). The results of experiments conducted with standard benchmarks show that the proposed approach produces LUT-based FSM circuits with significantly better area characteristics than for circuits produced by such methods as Auto and One-Hot of Vivado, JEDI, and twofold state assignment. Compared to these methods, the number of LUTs is reduced from 9.44% to 69.98%. Additionally, the proposed method leads to the following phenomenon: the maximum operating frequency is slightly improved as compared with FSM circuits based on twofold state assignment (up to 0.6%). The negative effect of these improvements is an increase in power consumption. However, it is extremely insignificant (up to 1.56%). As the values of the FSM's main characteristics grow, there is an increase in the gain from the application of the proposed method. The conditions for applying the proposed method are determined. A generalized architecture consisting of three blocks of partial functions and a method for synthesizing an FSM with this architecture are proposed. A method for selecting one of the seven architectures generated by the generalized architecture is proposed. [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]

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 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]

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]

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]

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.

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]

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]

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]