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

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

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



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






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


Известия Российской академии наук. Серия математическая, 2003, том 67, выпуск 1, страницы 159–176
DOI: https://doi.org/10.4213/im422
(Mi im422)
 

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

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

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

Математический институт им. В. А. Стеклова РАН
Список литературы:
Аннотация: С точностью до логарифмического множителя определяется коммуникационная сложность вычисления произвольной, зависящей лишь от $|x\cap y|$, функции $f(x,y)$, $x,y\subseteq [n]$, с допустимой вероятностью ошибки, отделенной от 1/2. Более точно, для предиката $D$ на множестве $\{0,1,\dots,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 наименований.
Поступило в редакцию: 29.04.2002
Англоязычная версия:
Izvestiya: Mathematics, 2003, Volume 67, Issue 1, Pages 145–159
DOI: https://doi.org/10.1070/IM2003v067n01ABEH000422
Реферативные базы данных:
Тип публикации: Статья
УДК: 510.52
MSC: 03D15, 68Q15, 81P68
Образец цитирования: А. А. Разборов, “О квантовой коммуникационной сложности симметрических предикатов”, Изв. РАН. Сер. матем., 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/im422}
\crossref{https://doi.org/10.4213/im422}
\mathscinet{http://mathscinet.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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000185513200008}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33748500069}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/im422
  • https://doi.org/10.4213/im422
  • https://www.mathnet.ru/rus/im/v67/i1/p159
  • Эта публикация цитируется в следующих 102 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Статистика просмотров:
    Страница аннотации:884
    PDF русской версии:252
    PDF английской версии:19
    Список литературы:40
    Первая страница:3
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024