• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Статьи
  • The arctic rank of a Boolean matrix
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Приоритетные направления
  • бизнес-информатика
  • государственное и муниципальное управление
  • гуманитарные науки
  • инженерные науки
  • компьютерно-математическое
  • математика
  • менеджмент
  • право
  • социология
  • экономика
по году
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • еще
Тематика
Новости
16 сентября 2026 г.
Ученые НИУ ВШЭ - Санкт-Петербург разработали новые соединения для борьбы с раком
Ученые Лаборатории био- и хемоинформатики НИУ ВШЭ — Санкт-Петербург совместно с коллегами из Университета Цзинань (Китай) и Санкт-Петербургского государственного технологического института разработали малые молекулы, преодолевающие химическую защиту раковых клеток. В отличие от классических ингибиторов, которые только блокируют активность белка, новые соединения удаляют его целиком. Работа ведется при поддержке Российского научного фонда.
14 сентября 2026 г.
Когда картинка мешает понять: ученые НИУ ВШЭ выяснили, что сложным идеям не всегда нужны иллюстрации
Иллюстрации помогают запоминать конкретные действия, но не всегда облегчают понимание абстрактных идей. Исследователи НИУ ВШЭ и Университета Гумбольдта сравнили, как люди усваивают тексты разного уровня абстрактности. Выяснилось, что участники лучше запоминали иллюстрации и выполняли задания после чтения мультимедийного текста об асанах йоги, чем после чтения абстрактного текста о равновесии Нэша. Результаты помогут эффективнее подбирать иллюстрации для учебных и информационных материалов. Исследование опубликовано в журнале Learning and Instruction.
11 сентября 2026 г.
Научная экспедиция на Хайнань: ученые ВШЭ организовали конференцию по статистическому ИИ в Китае
С 24 по 28 августа 2026 года в городе Санья на острове Хайнань (Китай) прошла международная конференция Statistical AI («Статистический искусственный интеллект»). Мероприятие собрало ведущих специалистов в области статистики, машинного обучения и прикладного ИИ. Среди организаторов конференции — Алексей Наумов, директор Института искусственного интеллекта и цифровых наук ФКН НИУ ВШЭ, и Сергей Самсонов, заведующий Международной лабораторией стохастических алгоритмов и анализа многомерных данных.

 

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации
  • Книги
  • Статьи
  • Главы в книгах
  • Препринты
  • Верификация публикаций
  • Расширенный поиск
  • Правила использования материалов
  • Наука в ВШЭ

?

The arctic rank of a Boolean matrix

Journal of Algebra. 2015. Vol. 433. P. 168–182.
Beasley L., Guterman A., Шитов Я. Н.

Among different rank functions on tropical matrices, there is one known as tropical rank which is a lower bound for any other. Here we introduce a new concept (for being opposed to tropical rank, it is called arctic) which gives an upper bound for other ranks. Our definition is based on the perimeter notion previously studied for rank-one matrices. We study the arithmetic behavior of the arctic rank and compare it with that of other rank functions. Finally, we provide an algorithm computing the arctic rank. We show that no algorithm is likely to find the arctic rank in polynomial time by proving that computing the perimeter of a matrix is an NP-hard problem.

Приоритетные направления: математика
Язык: английский
Полный текст
DOI
Текст на другом сайте
Ключевые слова: matrix rankBoolean matrixбулева матрицаранг матрицы
Похожие публикации
Vague stimulating ideas, images and metaphors in scientific thinking: researchers' work with horizons of unclear knowledge
Поддьяков А. Н., / Series Social Science Research Network "Social Science Research Network". 2026. No. 7437658.
Добавлено: 15 сентября 2026 г.
On phase-lock area parquet in a special slow-fast limit of model of Josephson junction.
Глуцюк А. А., / Series arXiv "math". 2026.
Добавлено: 8 сентября 2026 г.
Infinitely many graph manifolds with unique geometrical piece that admit arbitrarily many Anosov flows
Починка О. В., Шмуклер В. И., / Series math.RT "arXiv:1808.06395 [math.RT]". 2026.
Добавлено: 31 августа 2026 г.
New bound on S1× S2-setting Bell locality of a nonseparable Werner state
Лубенец Е. Р., / Series arxiv.org "quant-ph". 2026. No. 2607.18050.
Добавлено: 21 июля 2026 г.
On functional equations for Chow polylogarithms
Болбачан В. С., / Series math "arxiv.org". 2024.
Полилогарифмы Чжоу — это специальные функции, возникающие при явном описании отображения регулятора Бейлинсона. Наиболее интересное функциональное уравнение для этой функции отражает тот факт, что она обращается в нуль на границе в комплексе циклов Блоха. Мы показываем, что это функциональное уравнение формально вытекает из более простых свойств: кососимметричности, функториальности и мультипликативности. Для доказательства этого мы рассматриваем ...
Добавлено: 16 июля 2026 г.
On Goncharov’s conjecture in next to Milnor degree
Болбачан В. С., / Series math "arxiv.org". 2024.
Пусть K поле характеристики ноль. Мы доказываем что его когомологии в степени m-1 и весе m рационально изоморфны когомологиям полилогарифмического комплекса в соответствующей степени. Это дает частичное расширение теоремы Суслина, описывающую неразложимую K теорию K_3 для поля. ...
Добавлено: 16 июля 2026 г.
Statistical inference based on band-limited kernels: Rational-infinitely divisible distributions and beyond
Панов В. А., Рябченко А. П., / Series arXiv "stat.ME". 2026. No. 2607.05048.
Добавлено: 9 июля 2026 г.
Strong Approximations for Markov Chains Weakly Converging to Diffusions
Конаков В. Д., Кучер Д. А., Mammen E., / Series arXiv "math". 2026. No. 2606.11142v1.
Добавлено: 11 июня 2026 г.
Bifurcations and Structural Stability of Generic PC-HC Families
Доровский А. А., / Series arXiv "math". 2026.
Добавлено: 14 мая 2026 г.
On the minimum number of maximal distance-k independent sets in trees
Талецкий Д. С., / Series arXiv "math". 2026.
Добавлено: 1 мая 2026 г.
On Arithmetic Mirror Symmetry for smooth Fano fourfolds
Овчаренко М. А., / Series arXiv "math". 2026.
Добавлено: 30 апреля 2026 г.
On weak solutions to the 1d compressible Navier-Stokes equations: a Lipschitz continuous dependence on data in weaker norms and an error of their homogenization
Zlotnik Alexander, / Series arXiv "math". 2026. No. 2602.03481v1.
Добавлено: 18 апреля 2026 г.
On the dimension of the space of static potentials on three-manifolds
Медведев В. О., / Series arXiv "math". 2026.
We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...
Добавлено: 3 апреля 2026 г.
Using predefined vector systems to speed up neural network multimillion class classification
Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.
Добавлено: 2 апреля 2026 г.
Homogeneous maximizers of the Blaschke-Santalo-type functionals
Колесников А. В., / Series arXiv "math". 2025.
Добавлено: 13 февраля 2026 г.
Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection
Сорокин К. С., Бекетов М. Е., Онучин А. и др., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.
Обнаружение сообществ в сложных сетях — фундаментальная проблема, открытая для новых подходов в различных научных областях. Мы представляем новый метод обнаружения сообществ, основанный на потоке Риччи на графах. Наша техника итеративно обновляет веса ребер (их метрические длины) в соответствии с их (комбинаторной) версией кривизны Риччи Фостера, вычисленной на основе эффективного расстояния сопротивления между узлами. Известно, ...
Добавлено: 15 января 2026 г.
Maximal generalized rank in graphical matrix spaces
Спиридонов И. А., Meshulam R., Гутерман А., Israel Journal of Mathematics 2023 Vol. 256 No. 1 P. 297 – 309
Добавлено: 3 октября 2024 г.
On the determinant of a sparse 0-1 matrix
Шитов Я. Н., Linear Algebra and its Applications 2018 Vol. 554 P. 49–50
Добавлено: 30 января 2019 г.
Линейная алгебра. Основы теории, примеры и задачи.
Логвенков С. А., Самовол В. С., М.: МЦНМО, 2017.
Наряду с разделами линейной алгебры, традиционно включаемыми в подобные учебные издания, в данном учебнике представлены некоторые специальные темы, связанные прежде всего с теорией матриц, в том числе, многочленные матрицы и их преобразования, жордановы матрицы, методы приведения матриц к нормальной жордановой форме и др. В книге также нашли отражение такие вопросы, имеющие важное прикладное значение, как ...
Добавлено: 31 декабря 2017 г.
Rank functions of tropical matrices
Alexander Guterman, Yaroslav Shitov, Linear Algebra and its Applications 2016 Vol. 498 P. 326–348
Добавлено: 10 августа 2015 г.
Studying Non-negative Factorizations with Tools from Linear Algebra over a Semiring
Шитов Я. Н., Communications in Algebra 2015 Vol. 43 No. 10 P. 4359–4366
We develop the technique useful for studying the problem of factoring nonnegative matrices. We illustrate our method, based on the tools from linear algebra over a semiring, by applying it to studying the problem of existence of a rank-three matrix with full nonnegative rank equal to n. ...
Добавлено: 7 июля 2015 г.
Sign patterns of rational matrices with large rank
Шитов Я. Н., European Journal of Combinatorics 2014 Vol. 42 P. 107–111
Добавлено: 23 июня 2014 г.
On Boolean matrices with full factor rank
Шитов Я. Н., Sbornik Mathematics 2013 Vol. 204 No. 11 P. 1691–1699
It is demonstrated that every (0, 1)-matrix of size n×m having Boolean rank n contains a column with at least √n/2 − 1 zero entries. This bound is shown to be asymptotically optimal. As a corollary, it is established that the size of a full-rank Boolean matrix is bounded from above by a function of ...
Добавлено: 20 января 2014 г.
On the complexity of Boolean matrix ranks
Yaroslav Shitov, Linear Algebra and its Applications 2013 Vol. 439 No. 8 P. 2500–2502
We present a reduction which shows that the fooling set number, tropical and determinantal ranks of a Boolean matrix are NP-hard to compute. ...
Добавлено: 11 августа 2013 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика обработки персональных данных
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору