English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Boolean functions are important primitives in different domains ofcryptology, complexity and coding theory. In this paper, we connect the toolsfrom cryptology and complexity theory in the domain of Boolean functions withlow polynomial degree and high sensitivity. It is well known that thepolynomial degree of of a Boolean function and its resiliency are directlyconnected. Using this connection we analyze the polynomial degree-sensitivityvalues through the lens of resiliency, demonstrating existence andnon-existence results of functions with low polynomial degree and highsensitivity on small number of variables (upto 10). In this process, borrowingan idea from complexity theory, we show that one can implement resilientBoolean functions on a large number of variables with linear size andlogarithmic depth. Finally, we extend the notion of sensitivity to higher orderand note that the existing construction idea of Nisan and Szegedy (1994) canprovide only constant higher order sensitivity when aiming for polynomialdegree of $n-\omega(1)$. In this direction, we present a construction with low($n-\omega(1)$) polynomial degree and super-constant $\omega(1)$ ordersensitivity exploiting Maiorana-McFarland constructions, that we borrow fromconstruction of resilient functions. The questions we raise identify novelcombinatorial problems in the domain of Boolean functions.

On Boolean Functions with Low Polynomial Degree and Higher Order Sensitivity