Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

On the weightwise nonlinearity of weightwise perfectly balanced functions Gini, Agnese ; Meaux, Pierrick in Discrete Applied Mathematics (2022), 322 In this article we perform a general study on the criterion of weightwise nonlinearity for the functions which are weightwise perfectly balanced (WPB). First, we investigate the minimal value this ... [more ▼] In this article we perform a general study on the criterion of weightwise nonlinearity for the functions which are weightwise perfectly balanced (WPB). First, we investigate the minimal value this criterion can take over WPB functions, deriving theoretic bounds, and exhibiting the first values. We emphasize the link between this minimum and weightwise affine functions, and we prove that for n≥8 no n-variable WPB function can have this property. Then, we focus on the distribution and the maximum of this criterion over the set of WPB functions. We provide theoretic bounds on the latter and algorithms to either compute or estimate the former, together with the results of our experimental studies for n up to 8. Finally, we present two new constructions of WPB functions obtained by modifying the support of linear functions for each set of fixed Hamming weight. This provides a large corpus of WPB function with proven weightwise nonlinearity, and we compare the weightwise nonlinearity of these constructions to the average value, and to the parameters of former constructions in 8 and 16 variables. [less ▲] Detailed reference viewed: 68 (11 UL)On the algebraic immunity of direct sum constructions Meaux, Pierrick in Discrete Applied Mathematics (2022), 320 In this paper, we study sufficient conditions to improve the lower bound on the algebraic immunity of a direct sum of Boolean functions. We exhibit three properties on the component functions such that ... [more ▼] In this paper, we study sufficient conditions to improve the lower bound on the algebraic immunity of a direct sum of Boolean functions. We exhibit three properties on the component functions such that satisfying one of them is sufficient to ensure that the algebraic immunity of their direct sum exceeds the maximum of their algebraic immunities. These properties can be checked while computing the algebraic immunity and they allow to determine better the security provided by functions central in different cryptographic constructions such as stream ciphers, pseudorandom generators, and weak pseudorandom functions. We provide examples for each property and determine the exact algebraic immunity of candidate constructions. [less ▲] Detailed reference viewed: 28 (1 UL)Set-reconstructibility of Post classes Couceiro, Miguel ; Lehtonen, Erkko ; Schölzel, Karsten in Discrete Applied Mathematics (2015), 187 Detailed reference viewed: 106 (5 UL)Influence and interaction indexes for pseudo-Boolean functions: a unified least squares approach Marichal, Jean-Luc ; Mathonet, Pierre in Discrete Applied Mathematics (2014), 179 The Banzhaf power and interaction indexes for a pseudo-Boolean function (or a cooperative game) appear naturally as leading coefficients in the standard least squares approximation of the function by a ... [more ▼] The Banzhaf power and interaction indexes for a pseudo-Boolean function (or a cooperative game) appear naturally as leading coefficients in the standard least squares approximation of the function by a pseudo-Boolean function of a specified degree. We first observe that this property still holds if we consider approximations by pseudo-Boolean functions depending only on specified variables. We then show that the Banzhaf influence index can also be obtained from the latter approximation problem. Considering certain weighted versions of this approximation problem, we introduce a class of weighted Banzhaf influence indexes, analyze their most important properties, and point out similarities between the weighted Banzhaf influence index and the corresponding weighted Banzhaf interaction index. We also discuss the issue of reconstructing a pseudo-Boolean function from prescribed influences and point out very different behaviors in the weighted and non-weighted cases. [less ▲] Detailed reference viewed: 190 (7 UL)Pivotal decompositions of functions Marichal, Jean-Luc ; Teheux, Bruno in Discrete Applied Mathematics (2014), 174 We extend the well-known Shannon decomposition of Boolean functions to more general classes of functions. Such decompositions, which we call pivotal decompositions, express the fact that every unary ... [more ▼] We extend the well-known Shannon decomposition of Boolean functions to more general classes of functions. Such decompositions, which we call pivotal decompositions, express the fact that every unary section of a function only depends upon its values at two given elements. Pivotal decompositions appear to hold for various function classes, such as the class of lattice polynomial functions or the class of multilinear polynomial functions. We also define function classes characterized by pivotal decompositions and function classes characterized by their unary members and investigate links between these two concepts. [less ▲] Detailed reference viewed: 202 (11 UL)Locally monotone Boolean and pseudo-Boolean functions Couceiro, Miguel ; Marichal, Jean-Luc ; Waldhauser, Tamás in Discrete Applied Mathematics (2012), 160(12), 1651-1660 We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on ... [more ▼] We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on tuples which differ in less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions. Local monotonicities are shown to be tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions are shown to have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classification of p-locally monotone functions, as well as of functions having p-permutable derivatives, in terms of certain forbidden "sections", i.e., functions which can be obtained by substituting constants for variables. This description is made explicit in the special case when p=2. [less ▲] Detailed reference viewed: 139 (4 UL)The arity gap of order-preserving functions and extensions of pseudo-Boolean functions Couceiro, Miguel ; Lehtonen, Erkko ; Waldhauser, Tamás in Discrete Applied Mathematics (2012), 160(4-5), 383-390 The aim of this paper is to classify order-preserving functions according to their arity gap. Noteworthy examples of order-preserving functions are the so-called aggregation functions. We first explicitly ... [more ▼] The aim of this paper is to classify order-preserving functions according to their arity gap. Noteworthy examples of order-preserving functions are the so-called aggregation functions. We first explicitly classify the Lovász extensions of pseudo-Boolean functions according to their arity gap. Then we consider the class of order-preserving functions between partially ordered sets, and establish a similar explicit classification for this function class. [less ▲] Detailed reference viewed: 129 (4 UL)Weighted lattice polynomials of independent random variables Marichal, Jean-Luc in Discrete Applied Mathematics (2008), 156(5), 685-694 We give the cumulative distribution functions, the expected values, and the moments of weighted lattice polynomials when regarded as real functions of independent random variables. Since weighted lattice ... [more ▼] We give the cumulative distribution functions, the expected values, and the moments of weighted lattice polynomials when regarded as real functions of independent random variables. Since weighted lattice polynomial functions include ordinary lattice polynomial functions and, particularly, order statistics, our results encompass the corresponding formulas for these particular functions. We also provide an application to the reliability analysis of coherent systems. [less ▲] Detailed reference viewed: 93 (4 UL)Approximations of Lovász extensions and their induced interaction index Marichal, Jean-Luc ; Mathonet, Pierre in Discrete Applied Mathematics (2008), 156(1), 11-24 The Lovász extension of a pseudo-Boolean function f : {0,1}^n --> R is defined on each simplex of the standard triangulation of [0,1]^n as the unique affine function \hat f : [0,1]^n --> R that ... [more ▼] The Lovász extension of a pseudo-Boolean function f : {0,1}^n --> R is defined on each simplex of the standard triangulation of [0,1]^n as the unique affine function \hat f : [0,1]^n --> R that interpolates f at the n+1 vertices of the simplex. Its degree is that of the unique multilinear polynomial that expresses f. In this paper we investigate the least squares approximation problem of an arbitrary Lovász extension \hat f by Lovász extensions of (at most) a specified degree. We derive explicit expressions of these approximations. The corresponding approximation problem for pseudo-Boolean functions was investigated by Hammer and Holzman and then solved explicitly by Grabisch, Marichal, and Roubens, giving rise to an alternative definition of Banzhaf interaction index. Similarly we introduce a new interaction index from approximations of \hat f and we present some of its properties. It turns out that its corresponding power index identifies with the power index introduced by Grabisch and Labreuche. [less ▲] Detailed reference viewed: 97 (1 UL)Axiomatic characterizations of generalized values Marichal, Jean-Luc ; ; in Discrete Applied Mathematics (2007), 155(1), 26-43 In the framework of cooperative game theory, the concept of generalized value, which is an extension of that of value, has been recently proposed to measure the overall influence of coalitions in games ... [more ▼] In the framework of cooperative game theory, the concept of generalized value, which is an extension of that of value, has been recently proposed to measure the overall influence of coalitions in games. Axiomatizations of two classes of generalized values, namely probabilistic generalized values and generalized semivalues, which extend probabilistic values and semivalues, respectively, are first proposed. The axioms we utilize are based on natural extensions of axioms involved in the axiomatizations of values. In the second half of the paper, special instances of generalized semivalues are also axiomatized. [less ▲] Detailed reference viewed: 112 (3 UL)The influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making Marichal, Jean-Luc in Discrete Applied Mathematics (2000), 107(1-3), 139-164 The power of players in a collective decision process is a central issue in game theory. For this reason, the concept of influence of players on a simple game has been introduced. More generally, the ... [more ▼] The power of players in a collective decision process is a central issue in game theory. For this reason, the concept of influence of players on a simple game has been introduced. More generally, the influence of variables on Boolean functions has been defined and studied. We extend this concept to pseudo-Boolean functions, thus making it possible to appraise the degree of influence of any coalition of players in cooperative games. In the case of monotone games, we also point out the links with the concept of interaction among players. Although they do not have the same meaning at all, both influence and interaction functions coincide on singletons with the so-called Banzhaf power index. We also define the influence of variables on continuous extensions of pseudo-Boolean functions. In particular, the Lovász extension, also called discrete Choquet integral, is used in multicriteria decision making problems as an aggregation operator. In such problems, the degree of influence of decision criteria on the aggregation process can then be quite relevant information. We give the explicit form of this influence for the Choquet integral and its classical particular cases. [less ▲] Detailed reference viewed: 134 (12 UL) |
||