63 citations · 168 across the 57 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.CC2013
Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity
Xiaoming Sun, Marcos Villagra
There are three different types of nondeterminism in quantum communication: i) $\nqp$-communication, ii) $\qma$-communication, and iii) $\qcma$-communication. In this \redout{paper…
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…