Skip to main content
pyao's user avatar
pyao's user avatar
pyao's user avatar
pyao
  • Member for 13 years, 8 months
  • Last seen more than a month ago
awarded
awarded
comment
Limitations of techniques in communication complexity
The partition bound subsumes all other bounds except those from information theory. arxiv.org/pdf/0910.4266v2.pdf. The internal information theory subsumes all the bounds except the partition bound arxiv.org/abs/1204.1505. The external information complexity is same as communication complexity up to a log factor. (I forget the reference for this one, but I think you get deduce it using the technique from boazbarak.org/Papers/directsum.pdf)
awarded
awarded
comment
Best sources for communication complexity
A more recent reference by Lee and Shraibman, also covers the methods to prove lower bound on quantum communication complexity research.rutgers.edu/~troyjlee/survey_plain.pdf
awarded
awarded
revised
Loading…
Loading…
comment
What is the largest gap between rank and approximate rank?
Thanks. but my question is if there is superexponential gap for $rank(A)$ and $rank^{\alpha}(A)$, where $\alpha>1$ but not $\alpha\neq\infty$.
comment
how to cover a set in a grid with as few rectangles as possible
will the problem be easier when allowing overlap? About the rectangle, yes, the black squares are covered by two rectangles
awarded
revised
Loading…
Loading…
awarded
comment
Is there an oracle that separates two complexity classes known to be equal?
OK, here "the same" means they are shown to be same, but may use completely different definitions, like $IP=PSPACE$.
comment
Is there an oracle that separates two complexity classes known to be equal?
Then it means $P\ne NP$, otherwise, how can an oracle separate them?