RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Изв. РАН. Сер. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Изв. РАН. Сер. матем., 2003, том 67, выпуск 1, страницы 159–176 (Mi izv422)  

Эта публикация цитируется в 50 научных статьях (всего в 50 статьях)

О квантовой коммуникационной сложности симметрических предикатов

А. А. Разборов

Математический институт им. В. А. Стеклова РАН

Аннотация: С точностью до логарифмического множителя определяется коммуникационная сложность вычисления произвольной, зависящей лишь от $|x\cap y|$, функции $f(x,y)$, $x,y\subseteq [n]$, с допустимой вероятностью ошибки, отделенной от 1/2. Более точно, для предиката $D$ на множестве $\{0,1,…,n\}$ полагаем
\begin{align*} \ell_0(D)&\overset{\mathrm{def}}{=}\max\{\ell\mid 1\leqslant\ell\leqslant n/2\land D(\ell)\not\equiv D(\ell-1)\},
\ell_1(D)&\overset{\mathrm{def}}{=}\max\{n-\ell\mid n/2\leqslant\ell<n\land D(\ell) \not\equiv D(\ell+1)\}. \end{align*}
Тогда квантовая коммуникационная сложность функции $f_D(x,y)=D(|x\cap y|)$ в этой модели равна (с точностью до логарифмического множителя) величине $\sqrt{n\ell_0(D)}+\ell_1(D)$. В частности, сложность предиката, называемого дизъюнктность, оказывается равной $\Omega(\sqrt n )$. Полученный результат выполняется как в модели с предварительным зацеплением, так и в модели без такого зацепления.
Библиография: 26 наименований.

DOI: https://doi.org/10.4213/im422

Полный текст: PDF файл (1573 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Izvestiya: Mathematics, 2003, 67:1, 145–159

Реферативные базы данных:

Тип публикации: Статья
УДК: 510.52
MSC: 03D15, 68Q15, 81P68
Поступило в редакцию: 29.04.2002

Образец цитирования: А. А. Разборов, “О квантовой коммуникационной сложности симметрических предикатов”, Изв. РАН. Сер. матем., 67:1 (2003), 159–176; Izv. Math., 67:1 (2003), 145–159

Цитирование в формате AMSBIB
\RBibitem{Raz03}
\by А.~А.~Разборов
\paper О~квантовой коммуникационной сложности симметрических предикатов
\jour Изв. РАН. Сер. матем.
\yr 2003
\vol 67
\issue 1
\pages 159--176
\mathnet{http://mi.mathnet.ru/izv422}
\crossref{https://doi.org/10.4213/im422}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1957920}
\zmath{https://zbmath.org/?q=an:1088.68052}
\transl
\jour Izv. Math.
\yr 2003
\vol 67
\issue 1
\pages 145--159
\crossref{https://doi.org/10.1070/IM2003v067n01ABEH000422}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000185513200008}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33748500069}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/izv422
  • https://doi.org/10.4213/im422
  • http://mi.mathnet.ru/rus/izv/v67/i1/p159

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Ambainis A., Schulman L.J., Ta-Shma A., Vazirani U., Wigderson A., “The quantum communication complexity of sampling”, SIAM J. Comput., 32:6 (2003), 1570–1585  crossref  mathscinet  zmath  isi  elib  scopus
    2. Buhrman H., Rohrig H., “Distributed quantum computing”, Mathematical foundations of computer science, Lecture Notes in Comput. Sci., 2747, Springer, Berlin, 2003, 1–20  crossref  mathscinet  zmath  isi  elib
    3. Aaronson S., Ambainis A., “Quantum search of spatial regions (extended abstract)”, 44th Annual IEEE Symposium on Foundations of Computer Science, Proceedings, Annual IEEE Symposium on Foundations of Computer Science, 2003, 200–209  mathscinet  isi
    4. Klauck H., “Quantum and approximate privacy”, Theory Comput. Syst., 37:1 (2004), 221–246  crossref  mathscinet  zmath  isi  elib  scopus
    5. Lowe B., Piwinger B., Rasch T., “Classical and New Paradigms of Computation and Their Complexity Hierarchies - Papers of the Conference “Foundations of the Formal Sciences III” - Preface”, Classical and New Paradigms of Computation and their Complexity Hierarchies, Trends in Logic - Studia Logica Library, 23, 2004, VII  mathscinet  isi
    6. Zhang Shengyu, “Promised and distributed quantum search”, Computing and combinatorics, Lecture Notes in Comput. Sci., 3595, Springer, Berlin, 2005, 430–439  crossref  mathscinet  zmath  isi  elib
    7. Huang Wei, Shi Yaoyun, Zhang Shengyu, Zhu Yufan, “The communication complexity of the Hamming distance problem”, Inform. Process. Lett., 99:4 (2006), 149–153  crossref  mathscinet  zmath  isi  elib  scopus
    8. Nayak A., Salzman J., “Limits on the ability of quantum states to convey classical messages”, J. ACM, 53:1 (2006), 184–206  crossref  mathscinet  zmath  isi  elib  scopus
    9. Klauck H., Nayak A., Ta-Shma A., Zuckerman D., “Interaction in quantum communication”, IEEE Trans. Inform. Theory, 53:6 (2007), 1970–1982  crossref  mathscinet  zmath  isi  scopus
    10. Iwama K., Nishimura H., Raymond R., Yamashita Sh., “Unbounded-error one-way classical and quantum communication complexity”, Automata, Languages and Programming, Proceedings, Lecture Notes in Computer Science, 4596, 2007, 110–121  crossref  mathscinet  zmath  isi
    11. Shi Yaoyun, Zhu Yufan, “Tensor norms and the classical communication complexity of nonlocal quantum measurement”, SIAM J. Comput., 38:3 (2008), 753–766  crossref  mathscinet  zmath  isi  scopus
    12. Sherstov A.A., “The Pattern Matrix Method for Lower Bounds on Quantum Communication”, STOC'08: Proceedings of the 2008 Acm International Symposium on Theory of Computing, 2008, 85–94  mathscinet  zmath  isi
    13. Aaronson S., Wigderson A., “Algebrization: A New Barrier in Complexity Theory”, STOC'08: Proceedings of the 2008 Acm International Symposium on Theory of Computing, 2008, 731–740  mathscinet  zmath  isi
    14. Montanaro A., Nishimura H., Raymond R., “Unbounded-Error Quantum Query Complexity”, Algorithms and Computation, Proceedings, Lecture Notes in Computer Science, 5369, 2008, 919–930  crossref  mathscinet  zmath  isi  scopus
    15. Aaronson S., “The Polynomial Method in Quantum and Classical Computing”, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Annual IEEE Symposium on Foundations of Computer Science, 2008, 3–3  crossref  zmath  isi  scopus
    16. Sherstov A.A., “The Unbounded-Error Communication Complexity of Symmetric Functions”, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Annual IEEE Symposium on Foundations of Computer Science, 2008, 384–393  crossref  mathscinet  isi  scopus
    17. David M., Pitassi T., Viola E., “Improved Separations between Nondeterministic and Randomized Multiparty Communication”, Approximation Randomization and Combinatorial Optimization: Algorithms and Techniques, Proceedings, Lecture Notes in Computer Science, 5171, 2008, 371–384  crossref  mathscinet  zmath  isi  scopus
    18. Lee T., Shraibman A., “Disjointness is hard in the multi-party number-on-the-forehead model”, Twenty-Third Annual IEEE Conference on Computational Complexity, Proceedings, Annual IEEE Conference on Computational Complexity, 2008, 81–91  crossref  mathscinet  isi  scopus
    19. Sherstov A.A., “Approximate inclusion-exclusion for arbitrary symmetric functions”, Twenty-Third Annual IEEE Conference on Computational Complexity, Proceedings, Annual IEEE Conference on Computational Complexity, 2008, 112–123  crossref  mathscinet  isi  scopus
    20. Tani S., Nakanishi M., Yamashita Sh., “Multi-party quantum communication complexity with routed messages”, Computing and Combinatorics, Proceedings, Lecture Notes in Computer Science, 5092, 2008, 180–190  crossref  mathscinet  zmath  isi  scopus
    21. François Le Gall, “Exponential Separation of Quantum and Classical Online Space Complexity”, Theory Comput. Syst., 45:2 (2009), 188–202  crossref  mathscinet  zmath  isi  elib  scopus
    22. Linial N., Shraibman A., “Lower bounds in communication complexity based on factorization norms”, Random Structures Algorithms, 34:3 (2009), 368–394  crossref  mathscinet  zmath  isi  scopus
    23. Sherstov A. A., “Separating $\mathsf{AC}^0$ from depth-2 majority circuits”, SIAM J. Comput., 38:6 (2009), 2113–2129  crossref  mathscinet  zmath  isi  elib  scopus
    24. Lee Troy, Shraibman Adi, “Disjointness is hard in the multiparty number-on-the-forehead model”, Comput. Complexity, 18:2 (2009), 309–336  crossref  mathscinet  zmath  isi  elib  scopus
    25. Tani S., Nakanishi M., Yamashita Sh., “Multi-party quantum communication complexity with routed messages”, IEICE Transactions on Information and Systems, E92D:2 (2009), 191–199  crossref  adsnasa  isi  scopus
    26. Zhang Zhiqiang, Shi Yaoyun, “Communication complexities of symmetric XOR functions”, Quantum Inf. Comput., 9:3-4 (2009), 255–263  mathscinet  zmath  isi
    27. Shi Yaoyun, Zhu Yufan, “Quantum communication complexity of block-composed functions”, Quantum Inf. Comput., 9:5-6 (2009), 444–460  mathscinet  zmath  isi
    28. Zhang Sh., “On the Tightness of the Buhrman-Cleve-Wigderson Simulation”, Algorithms and Computation, Proceedings, Lecture Notes in Computer Science, 5878, 2009, 434–440  crossref  mathscinet  zmath  adsnasa  isi  scopus
    29. Lee T., Schechtman G., Shraibman A., “Lower bounds on quantum multiparty communication complexity”, Proceedings of the 24th Annual IEEE Conference on Computational Complexity, Annual IEEE Conference on Computational Complexity, 2009, 254–262  crossref  mathscinet  isi  scopus
    30. Lee T., Shraibman A., “An approximation algorithm for approximation rank”, Proceedings of the 24th Annual IEEE Conference on Computational Complexity, Annual IEEE Conference on Computational Complexity, 2009, 351–357  crossref  mathscinet  isi  scopus
    31. Kaplan M., Laplante S., “Kolmogorov Complexity and Combinatorial Methods in Communication Complexity”, Theory and Applications of Models of Computation, Lecture Notes in Computer Science, 5532, 2009, 261–270  crossref  mathscinet  zmath  isi  scopus
    32. Buhrman H., Cleve R., Massar S., de Wolf R., “Nonlocality and communication complexity”, Reviews of Modern Physics, 82:1 (2010), 665–698  crossref  adsnasa  isi  scopus
    33. Sherstov A.A., “On quantum-classical equivalence for composed communication problems”, Quantum Information & Computation, 10:5-6 (2010), 435–455  mathscinet  zmath  isi  elib
    34. Klivans A.R., Sherstov A.A., “Lower Bounds for Agnostic Learning via Approximate Rank”, Computational Complexity, 19:4 (2010), 581–604  crossref  mathscinet  zmath  isi  elib  scopus
    35. Marc Kaplan, Sophie Laplante, “Kolmogorov complexity and combinatorial methods in communication complexity”, Theoretical Computer Science, 2010  crossref  mathscinet  isi  scopus
    36. Lee T., Zhang Sh., “Composition Theorems in Communication Complexity”, Automata, Languages and Programming, Lecture Notes in Computer Science, 6198, no. I, 2010, 475–489  crossref  mathscinet  zmath  isi  scopus
    37. Ashley Montanaro, Harumichi Nishimura, Rudy Raymond, “Unbounded-error quantum query complexity”, Theoretical Computer Science, 2011  crossref  mathscinet  isi  scopus
    38. Alexander A. Sherstov, “The unbounded-error communication complexity of symmetric functions”, Combinatorica, 2011  crossref  mathscinet  isi  scopus
    39. Alexander A. Sherstov, “The Pattern Matrix Method”, SIAM J. Comput, 40:6 (2011), 1969  crossref  mathscinet  zmath  isi  scopus
    40. Paul Beame, Trinh Huynh, “Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremathAC^0$”, SIAM J. Comput, 41:3 (2012), 484  crossref  mathscinet  zmath  isi  scopus
    41. Briet J., Buhrman H., Lee T., Vidick T., “Multipartite Entanglement in Xor Games”, Quantum Inform. Comput., 13:3-4 (2013), 334–360  mathscinet  isi
    42. Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen, “The NOF Multiparty Communication Complexity of Composed Functions”, comput. complex, 2014  crossref  mathscinet  scopus
    43. Sherstov A.A., “Communication Complexity Theory: Thirty-Five Years of Set Disjointness”, Mathematical Foundations of Computer Science 2014, Pt I, Lecture Notes in Computer Science, 8634, eds. CsuhajVarju E., Dietzfelbinger M., Esik Z., Springer-Verlag Berlin, 2014, 24–43  crossref  mathscinet  zmath  isi  scopus
    44. Braverman M., Garg A., Ko Y.K., Mao J., Touchette D., “Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness”, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) (Berkeley, CA, USA), IEEE, 2015, 773–791  crossref  mathscinet  isi  scopus
    45. Montanaro A., “the Quantum Complexity of Approximating the Frequency Moments”, Quantum Inform. Comput., 16:13-14 (2016), 1169–1190  mathscinet  isi  elib
    46. Lee T., Leonardos N., Saks M., Wang F., “Hellinger volume and number-on-the-forehead communication complexity”, J. Comput. Syst. Sci., 82:6 (2016), 1064–1074  crossref  mathscinet  zmath  isi  scopus
    47. Goos M., Lovett Sh., Meka R., Watson T., Zuckerman D., “Rectangles Are Nonnegative Juntas”, SIAM J. Comput., 45:5 (2016), 1835–1869  crossref  mathscinet  zmath  isi  scopus
    48. Sherstov A.A., “The Multiparty Communication Complexity of Set Disjointness”, SIAM J. Comput., 45:4, SI (2016), 1450–1489  crossref  mathscinet  zmath  isi  scopus
    49. Gruska J., Qiu D., Zheng Sh., “Generalizations of the distributed Deutsch–Jozsa promise problem”, Math. Struct. Comput. Sci., 27:3 (2017), 311–331  crossref  mathscinet  zmath  isi  scopus
    50. Kothari P.K., Meka R., Raghavendra P., “Approximating Rectangles By Juntas and Weakly-Exponential Lower Bounds For Lp Relaxations of Csps”, Stoc'17: Proceedings of the 49Th Annual Acm Sigact Symposium on Theory of Computing, Annual Acm Symposium on Theory of Computing, eds. Hatami H., McKenzie P., King V., Assoc Computing Machinery, 2017, 590–603  crossref  isi
  • Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Просмотров:
    Эта страница:453
    Полный текст:102
    Литература:19
    Первая стр.:3

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018