19 citations · 33 across the 15 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2014
Tighter Relations Between Sensitivity and Other Complexity Measures
Andris Ambainis, Mohammad Bavarian, Yihan Gao +3
Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulate…
cs.CC2013★ 1 cited
New upper bound on block sensitivity and certificate complexity in terms of sensitivity
Andris Ambainis, Yihan Gao, Jieming Mao +2
Sensitivity \cite{CD82,CDR86} and block sensitivity \cite{Nisan91} are two important complexity measures of Boolean functions. A longstanding open problem in decision tree complexi…