55 citations · 55 across the 2 of their papers we have counts for
2 papers
cs.CC2010
A Separation of NP and coNP in Multiparty Communication Complexity
Dmytro Gavinsky, Alexander A. Sherstov
We prove that NP differs from coNP and coNP is not a subset of MA in the number-on-forehead model of multiparty communication complexity for up to k = (1-ε)log(n) players, where ε>…
cs.CC2008★ 55 cited
Communication Lower Bounds Using Dual Polynomials
Alexander A. Sherstov
Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n…