ECCC - Reports tagged with Decision Tree Complexity, Fractional Block Sensitivity, Sensitivity, Approximate Degree

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > KEYWORD > DECISION TREE COMPLEXITY, FRACTIONAL BLOCK SENSITIVITY, SENSITIVITY, APPROXIMATE DEGREE:

Reports tagged with Decision Tree Complexity, Fractional Block Sensitivity, Sensitivity, Approximate Degree:

TR13-168 | 29th November 2013
Raghav Kulkarni, Avishay Tal

On Fractional Block Sensitivity

Revisions: 1 , Comments: 1

In this paper we study the fractional block sensitivityof Boolean functions. Recently, Tal (ITCS, 2013) and
Gilmer, Saks, and Srinivasan (CCC, 2013) independently introduced this complexity measure, denoted by $fbs(f)$, and showed
that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by $RC(f)$, which ... more >>>

ISSN 1433-8092 | Imprint