All reports by Author Siddhesh Chaubal:

__
TR22-059
| 27th April 2022
__

Siddhesh Chaubal, Anna Gal#### Diameter versus Certificate Complexity of Boolean Functions

__
TR20-134
| 9th September 2020
__

Siddhesh Chaubal, Anna Gal#### Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions

__
TR18-205
| 3rd December 2018
__

Siddhesh Chaubal, Anna Gal#### New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

Siddhesh Chaubal, Anna Gal

In this paper, we introduce a measure of Boolean functions we call diameter, that captures the relationship between certificate complexity and several other measures of Boolean functions. Our measure can be viewed as a variation on alternating number, but while alternating number can be exponentially larger than certificate complexity, we ... more >>>

Siddhesh Chaubal, Anna Gal

Nisan and Szegedy conjectured that block sensitivity is at most

polynomial in sensitivity for any Boolean function.

Until a recent breakthrough of Huang, the conjecture had been

wide open in the general case,

and was proved only for a few special classes

of Boolean functions.

Huang's result implies that block ...
more >>>

Siddhesh Chaubal, Anna Gal

Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a ... more >>>