Читая некоторые недавние темы о квантовых вычислениях ( здесь , здесь и здесь ), я вспоминаю интересный вопрос о мощности некоторой машины, сохраняющей ℓpℓp\ell_p норму. Для людей, работающих в области теории сложности, которые идут на квантовую сложность, хорошим вступительным текстом является...
Это продолжение моего предыдущего вопроса о нижних границах связи для частичных булевых функций . Может ли кто-нибудь предложить какую-либо ссылку на нижние границы для недетерминированного многопартийного общения? Я просматривал статьи в этой области, но все, кажется, демонстрируют разделение...
Насколько я знаю, нижняя граница нормы факторизации, данная Линиалом и Шрайбманом, является по существу единственной нижней границей, известной для сложности квантовой связи (или, по крайней мере, она включает все остальные). Есть ли доказательства того, что эта граница была жесткой? Граница...