18 citations · 71 across the 29 of their papers we have counts for
Showing 2014Show 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.IT2014
Simulating Noisy Channel Interaction
Mark Braverman, Jieming Mao
We show that rounds of interaction over the binary symmetric channel with feedback can be simulated with rounds of interaction over a noiseless channel…