3.8k citations · 7.4k across the 34 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2015★ 1 cited
A communication game related to the sensitivity conjecture
Justin Gilmer, Michal Koucký, Michael Saks
One of the major outstanding foundational problems about boolean functions is the sensitivity conjecture, which (in one of its many forms) asserts that the degree of a boolean func…
cs.CC2013★ 3 cited
Composition limits and separating examples for some Boolean function complexity measures
Justin Gilmer, Michael Saks, Srikanth Srinivasan
Block sensitivity (), certificate complexity () and fractional certificate complexity () are three fundamental combinatorial measures of complexity of a boolea…