Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
189
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.