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

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

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



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






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


Изв. РАН. Сер. матем., статья будет опубликована в одном из ближайших номеров (Mi izv9113)  

Веса точных пороговых функций

L. Babaia, K. A. Hansenb, В. В. Подольскийc, X. Sund

a University of Chicago, USA
b University of Aarhus, Denmark
c Математический центр мирового уровня «Математический институт им. В.А. Стеклова Российской академии наук» (МЦМУ МИАН)
d Tsinghua University, China

Аннотация: We consider Boolean exact threshold functions de ned by linear equations, and in general degree $d$ polynomials. We give upper and lower bounds on the maximum magnitude (absolute value) of the coecients required to represent such functions. These bounds are very close. In the linear case in particular they are almost matching. This quantity is the same as the maximum magnitude of integer coecients of linear equations required to express every possible intersection of a hyperplane in $\mathbb R^n$ and the Boolean cube $\{0,1\}^n$, or in the general case intersections of hypersurfaces of degree $d$ in $\mathbb R^n$ and the Boolean cube $\{0,1\}^n$. In the process we construct new families of ill-conditioned matrices. We further stratify the problem (in the linear case) in terms of the dimension $k$ of the ane subspace spanned by the solutions, and give upper and lower bounds in this case as well. Our bounds here in terms of $k$ leave a substantial gap, a challenge for future work.

Ключевые слова: Сложность вычислений, булевы функции, пороговые функции, полиномиальные пороговые функции, анти-адамаровы матрицы


Англоязычная версия:
DOI: https://doi.org/10.1070/IM9113

Тип публикации: Статья
Поступило в редакцию: 02.10.2020
Исправленный вариант: 02.03.2021

Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/izv9113

    ОТПРАВИТЬ: 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
  • Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Просмотров:
    Эта страница:30
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021