A SUPER-SET OF PATTERSON-WIEDEMANN FUNCTIONS: UPPER BOUNDS AND POSSIBLE NONLINEARITIES

Date

2018-01-01

Author

Kavut, Selcuk
MAİTRA, Subhamoy
Özbudak, Ferruh

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

192
views

0
downloads

Construction of Boolean functions on an odd number of variables with nonlinearity exceeding the bent concatenation bound is one of the most difficult combinatorial problems within the domain of Boolean functions. This problem also has deep implications in coding theory and cryptology. Patterson and Wiedemann demonstrated instances of such functions back in 1983. For more than three decades efforts have been channeled into obtaining such instances. For the first time, in this paper we explore nontrivial upper bounds on nonlinearity for such classes of functions that are invariant not only under several group actions but also for larger sets of functions than what have been considered so far. Further, we present tight upper bounds on the nonlinearity in several cases. To support our claims, we present computational results for functions on n variables, where n is an odd composite integer in the interval [9, 39]. In particular, our results for n = 15 and 21 are of immediate interest given recent research results in this domain. In addition to the upper bounds, we also discover the nonlinearities that can actually be achieved above the bent concatenation bound for such a class of functions. Finally, we obtain all possible values in the absolute Walsh spectra of the functions considered.

Subject Keywords

Covering Radius, First Order Reed-Muller Code, Nonlinearity Bound, Patterson-Wiedemann Type Functions

URI

https://hdl.handle.net/11511/36742

Journal

SIAM JOURNAL ON DISCRETE MATHEMATICS

DOI

https://doi.org/10.1137/17m1144581

Collections

Department of Mathematics, Article

Suggestions

OpenMETU
Core

A semismooth newton method for generalized semi-infinite programming problems Tezel Özturan, Aysun; Karasözen, Bülent; Department of Mathematics (2010) Semi-infinite programming problems is a class of optimization problems in finite dimensional variables which are subject to infinitely many inequality constraints. If the infinite index of inequality constraints depends on the decision variable, then the problem is called generalized semi-infinite programming problem (GSIP). If the infinite index set is fixed, then the problem is called standard semi-infinite programming problem (SIP). In this thesis, convergence of a semismooth Newton method for generalize...
A categorical approach to the maximum theorem Koudenburg, Seerp Roald (2018-08-01) Berge's maximum theorem gives conditions ensuring the continuity of an optimised function as a parameter changes. In this paper we state and prove the maximum theorem in terms of the theory of monoidal topology and the theory of double categories.
Generalized rotation symmetric and dihedral symmetric boolean functions - 9 variable boolean functions with nonlinearity 242 Kavut, Selcuk; Yucel, Melek Diker (2007-12-20) Recently, 9-variable Boolean functions having nonlinearity 241, which is strictly greater than the bent concatenation bound of 240, have been discovered in the class of Rotation Symmetric Boolean Functions (RSBFs) by Kavut, Maitra and Yucel. In this paper, we present several 9-variable Boolean functions having nonlinearity of 242, which we obtain by suitably generalizing the classes of RSBFs and Dihedral Symmetric Boolean Functions (DSBFs). These functions do not have any zero in the Walsh spectrum values, ...
Characterisation and enumeration of a class of semi bent quadratic Boolean functions KOÇAK, Neşe; Koçak, Onur Ozan; Özbudak, Ferruh; SAYGI, ZÜLFÜKAR (2015-01-01) In this paper, we consider semi-bentness of quadratic Boolean functions defined for even n and give the characterisation of these functions. Up to our knowledge, semi-bentness of this class has not been investigated before and we proved that semi-bent functions of this form exist only for 6|n. Furthermore, we present a method for enumeration of semi-bent and bent functions in certain classes. Using this method we find the exact number of semi-bent functions of this form. Moreover, we complete some previous ...
A New Combinatorial Identity for Catalan Numbers Aker, Kursat; Gursoy, Aysin Erkan (2017-10-01) In this article, we prove a conjecture about the equality of two generating functions described in "From Parking Functions to Gelfand Pairs (Aker, Can 2012)" attached to two sets whose cardinalities are given by Catalan numbers: We establish a combinatorial bijection between the two sets on which the two generating functions were based on.

Citation Formats

S. Kavut, S. MAİTRA, and F. Özbudak, “A SUPER-SET OF PATTERSON-WIEDEMANN FUNCTIONS: UPPER BOUNDS AND POSSIBLE NONLINEARITIES,” SIAM JOURNAL ON DISCRETE MATHEMATICS, pp. 106–122, 2018, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/36742.