On equivalence between known families of quadratic APN functions

This paper is dedicated to a question whether the currently known families of quadratic APN polynomials are pairwise different up to CCZ-equivalence. We reduce the list of these families to those CCZ-inequivalent to each other. In particular, we prove that the families of APN trinomials (constructed by Budaghyan and Carlet in 2008) and multinomials (constructed by Bracken et al. 2008) are contained in the APN hexanomial family introduced by Budaghyan and Carlet in 2008. We also prove that a generalization of these trinomial and multinomial families given by Duan et al. (2014) is contained in the family of hexanomials as well.     

On equivalence between known polynomial APN functions and power APN functions

Constructions and equivalence of APN functions play a significant role in the research of cryptographic functions. On finite fields of characteristic 2, 6 families of power APN functions and 14 families of polynomial APN functions have been constructed in the literature. However, the study on the equivalence among the aforementioned APN functions is rather limited to the equivalence in the power APN functions. Meanwhile, the theoretical analysis on the equivalence between the polynomial APN functions and the power APN functions, as well as the equivalence in the polynomial APN functions themselves, is far less studied. In this paper, we give the theoretical analysis on the inequivalence in 8 known families of polynomial APN functions and power APN functions.     

Almost perfect nonlinear families which are not equivalent to permutations

An important problem on almost perfect nonlinear (APN) functions is the existence of APN permutations on even-degree extensions of ${\mathbb{F}}_2$ larger than 6. Browning et al. (2010) gave the first known example of an APN permutation on the degree-6 extension of ${\mathbb{F}}_2$. The APN permutation is CCZ-equivalent to the previously known quadratic Kim κ-function (Browning et al. (2009)). Aside from the computer based CCZ-inequivalence results on known APN functions on even-degree extensions of ${\mathbb{F}}_2$ with extension degrees less than 12, no theoretical CCZ-inequivalence result on infinite families is known. In this paper, we show that Gold and Kasami APN functions are not CCZ-equivalent to permutations on infinitely many even-degree extensions of ${\mathbb{F}}_2$. In the Gold case, we show that Gold APN functions are not equivalent to permutations on any even-degree extension of ${\mathbb{F}}_2$, whereas in the Kasami case we are able to prove inequivalence results for every doubly-even-degree extension of ${\mathbb{F}}_2$.     

On the boolean partial derivatives and their composition

The main goal of this work is to introduce the relation between the partial boolean derivatives of an n-variable boolean function and their directional boolean derivatives.     

On homogeneous rotation symmetric bent functions

In this paper, we present partial results towards the conjectured nonexistence of homogeneous rotation symmetric bent functions having degree > 2.     

On the probability of union in the n-space

In this paper, our sets are orthants in $R^n$ and $N$, the number of them, is large ($N>n$). We introduce the modified inclusion–exclusion formula in order to efficiently calculate the probability of a union of such events. The new formula works in the bivariate case, and can also be used in $R^n,n\ge 3$ with a condition on the projected sets onto lower dimensional spaces. Numerical examples are presented.     

On the boomerang uniformity of permutations of low Carlitz rank

Finding permutation polynomials with low differential and boomerang uniformity is an important topic in S-box designs of many block ciphers. For example, AES chooses the inverse function as its S-box, which is differentially 4-uniform and boomerang 6-uniform. Also there has been considerable research on many non-quadratic permutations which are modifications of the inverse function. In this paper, we give a novel approach which shows that plenty of existing modifications of the inverse function are in fact affine equivalent to permutations of low Carlitz rank, and those modifications cannot be APN. We also present the complete list of permutations of Carlitz rank 3 having the boomerang uniformity six, and give the complete classification of the differential uniformities of permutations of Carlitz rank 3. As an application, we provide all the involutions of Carlitz rank 3 having the boomerang uniformity six.     

An equivalence for weighted integrals of an analytic function and ist derivative

In this paper we introduce the class of differentiable weights ω in the unit disc ?? such that where L is a positive constant. The main result in this paper asserts that if ω is one of these weights, then the equivalence holds for all 0 < p < ∞, 0 < q ≤ ∞and f an analytic function in ??. Our results improve others due to Aleman, Siskakis, and Stevi?. We also prove two results on harmonic conjugate functions. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the complexity of constrained VC-classes

Sauer's lemma is extended to classes H_N of binary-valued functions h on [n]={1,…,n} which have a margin less than or equal to N on all x∈[n] with h(x)=1, where the margin μ_h(x) of h at x∈[n] is defined as the largest non-negative integer a such that h is constant on the interval I_a(x)=[x-a,x+a]⊆[n]. Estimates are obtained for the cardinality of classes of binary-valued functions with a margin of at least N on a positive sample S⊆[n].     

Juntas in the ℓ1‐grid and Lipschitz maps between discrete tori

We show that if , then is ‐close to a junta depending upon at most coordinates, where denotes the edge‐boundary of in the ‐grid. This bound is sharp up to the value of the absolute constant in the exponent. This result can be seen as a generalisation of the Junta theorem for the discrete cube, from [6], or as a characterisation of large subsets of the ‐grid whose edge‐boundary is small. We use it to prove a result on the structure of Lipschitz functions between two discrete tori; this can be seen as a discrete, quantitative analogue of a recent result of Austin [1]. We also prove a refined version of our junta theorem, which is sharp in a wider range of cases. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 253–279, 2016     

Nilpotency,solvability and the twisting function of finite groups II

Let G be a finite group and m a natural number. The twisting function with m variables on G is defined by \({\tau_m(x_1,\ldots, x_m) :=(x_1^{x_2}, \ldots, x_{m-1}^{x_m}, x_m^{x_1})}\) and has been introduced and studied by the third author in [5]. In the current paper, we extend and sharpen results from Kaplan (see [5]) on solvability and nilpotency (see Theorems 1.2 and 1.1). Furthermore, for groups G such that \({\tau_2}\) is a permutation on the cartesian product G ², we investigate the order of this permutation and its connection to properties of G.     

On the complexity of monotone dualization and generating minimal hypergraph transversals

In 1994 Fredman and Khachiyan established the remarkable result that the duality of a pair of monotone Boolean functions, in disjunctive normal forms, can be tested in quasi-polynomial time, thus putting the problem, most likely, somewhere between polynomiality and coNP-completeness. We strengthen this result by showing that the duality testing problem can in fact be solved in polylogarithmic time using a quasi-polynomial number of processors (in the PRAM model). While our decomposition technique can be thought of as a generalization of that of Fredman and Khachiyan, it yields stronger bounds on the sequential complexity of the problem in the case when the sizes of f and g are significantly different, and also allows for generating all minimal transversals of a given hypergraph using only polynomial space.     

On the unitary equivalence of absolutely continuous parts of self-adjoint extensions

The classical Weyl-von Neumann theorem states that for any self-adjoint operator A₀ in a separable Hilbert space H there exists a (non-unique) Hilbert-Schmidt operator C=C^? such that the perturbed operator A₀+C has purely point spectrum. We are interesting whether this result remains valid for non-additive perturbations by considering the set ExtA of self-adjoint extensions of a given densely defined symmetric operator A in H and some fixed . We show that the ac-parts and of and A₀ are unitarily equivalent provided that the resolvent difference is compact and the Weyl function M(⋅) of the pair {A,A₀} admits weak boundary limits M(t):=w-lim_y→+0M(t+iy) for a.e. t∈R. This result generalizes the classical Kato-Rosenblum theorem. Moreover, it demonstrates that for such pairs {A,A₀} the Weyl-von Neumann theorem is in general not true in the class ExtA.     

The Boolean functions computed by random Boolean formulas or how to grow the right function

We characterize growth processes (probabilistic amplification) by their initial conditions to derive conditions under which results such as Valiant's 24 hold. We completely characterize growth processes that use linear connectives and generalize Savický's 19 analysis to characterize growth processes that use monotone connectives. Additionally, we obtain explicit bounds on the convergence rates of several growth processes, including the growth process studied in Savický. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

New results on the equivalence between zero-one programming and continuous concave programming

In this work, we study continuous reformulations of zero-one concave programming problems. We introduce new concave penalty functions and we prove, using general equivalence results here derived, that the obtained continuous problems are equivalent to the original combinatorial problem.     

On covering graphs by complete bipartite subgraphs

We prove that, if a graph with e edges contains m vertex-disjoint edges, then m²/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.     

Arithmetic equivalence for function fields, the Goss zeta function and a generalisation

A theorem of Tate and Turner says that global function fields have the same zeta function if and only if the Jacobians of the corresponding curves are isogenous. In this note, we investigate what happens if we replace the usual (characteristic zero) zeta function by the positive characteristic zeta function introduced by Goss. We prove that for function fields whose characteristic exceeds their degree, equality of the Goss zeta function is the same as Gaßmann equivalence (a purely group theoretical property), but this statement can fail if the degree exceeds the characteristic. We introduce a ‘Teichmüller lift’ of the Goss zeta function and show that equality of such is always the same as Gaßmann equivalence.     

Covering Sequences of Boolean Functions and Their Cryptographic Significance

We introduce the notion of covering sequence of a Boolean function, related to the derivatives of the function. We give complete characterizations of balancedness, correlation immunity and resiliency of Boolean functions by means of their covering sequences. By considering particular covering sequences, we define subclasses of (correlation-immune) resilient functions. We derive upper bounds on their algebraic degrees and on their nonlinearities. We give constructions of resilient functions belonging to these classes. We show that they achieve the best known trade-off between order of resiliency, nonlinearity and algebraic degree.