5 citations · 12 across the 9 of their papers we have counts for
Showing 2009Show all
3 papers · 1 filter
cs.CC2009
The intersection of two halfspaces has high threshold degree
Alexander A. Sherstov
The threshold degree of a Boolean function f:{0,1}^n->{-1,+1} is the least degree of a real polynomial p such that f(x)=sgn p(x). We construct two halfspaces on {0,1}^n whose inter…
cs.CC2009
The Pattern Matrix Method (Journal Version)
Alexander A. Sherstov
We develop a novel and powerful technique for communication lower bounds, the pattern matrix method. Specifically, fix an arbitrary function f:{0,1}^n->{0,1} and let A_f be the mat…
cs.CC2009
On Quantum-Classical Equivalence for Composed Communication Problems
Alexander A. Sherstov
An open problem in communication complexity proposed by several authors is to prove that for every Boolean function f, the task of computing f(x AND y) has polynomially related cla…