О нижних оценках сложности схем в базисе антицепных функций

О. В. Подольская

?

О нижних оценках сложности схем в базисе антицепных функций

Вестник Московского университета. Серия 1: Математика. Механика. 2013. Т. 2. С. 17–23.

Подольская О. В.

Антицепной функцией называется характеристическая функция антицепи в булевом кубе. Множество всех антицепных функций образует бесконечный полный базис. В работе изучается сложность реализации булевых функций схемами в этом базисе. Доказаны нижние оценки порядка $\sqrt n$ для сложности реализации линейной функции, функции голосования и почти всех функций от $n$ переменных.

Приоритетные направления: математика

Язык: русский

Ключевые слова: линейная функция Boolean circuits antichain function linear function majority function булевы схемы антицепная функция функция голосования

On static manifolds with boundary admitting a nowhere-vanishing static potential

Медведев В. О., / Series arXiv "math". 2026.

We study complete static manifolds with boundary admitting a nowhere-vanishing static potential. Our main result shows that, under a natural lower bound relating the scalar curvature and the boundary mean curvature, a simple static manifold with boundary must in fact have positive scalar curvature, negative boundary mean curvature, and be compact; we also obtain explicit ...

Добавлено: 19 сентября 2026 г.

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 г.

The Exact Circuit Complexity of Boolean Functions in an Infinite Basis

V. V. Kochergin, A. V. Mikhailovich, Mathematical notes 2025 Vol. 117 No. 4 P. 579–594

Добавлено: 28 февраля 2026 г.

Homogeneous maximizers of the Blaschke-Santalo-type functionals

Колесников А. В., / Series arXiv "math". 2025.

Добавлено: 13 февраля 2026 г.

Точное значение схемной сложности булевых функций в одном бесконечном базисе

Кочергин В. В., Михайлович А. В., Математические заметки 2025 Т. 117 № 4 С. 523–542

Для каждой булевой функции установлено точное значение сложности реализации логическими схемами в бесконечном базисе, состоящем из отрицания и всех монотонных булевых функций. Под сложностью функции понимается минимально возможное число элементов базиса, достаточное для построения схемы для данной функции. ...

Добавлено: 8 апреля 2025 г.

Multiparty Karchmer-Wigderson Games and Threshold Circuits

Alexander Kozachinskiy, Vladimir Podolskii, Theory of Computing 2022 Vol. 18 No. 15 P. 1–33

Добавлено: 10 декабря 2022 г.

Алгоритмы синтеза схем-заплаток для решения ресурсо-ориентированной функциональной коррекции схем из функциональных элементов

Высоцкий Л. И., Жуков В. В., Шуплецов М. С., В кн.: Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС-2018)Вып. 1.: М.: ИППМ РАН, 2018. С. 30–37.

При обнаружении ошибок или изменении спецификации проектируемой сверхбольшой интегральной схемы (СБИС) на поздних этапах маршрута проектирования откат на более ранние этапы проектирования и их повторное выполнение очень часто становится непрактичным в силу существенных временных затрат. Для целей сокращения времени проектирования в современные маршруты проектирования интегрируют специальные этапы функциональной коррекции схемы (англ. Engineering Change Order, ECO). В основе указанного подхода лежит анализ уже спроектированной схемы и построение небольшой подсхемы-заплатки, внедрение которой в уже синтезированную ...

Добавлено: 10 ноября 2020 г.

О поведении функции Шеннона для задержки схем в модели, где задержка соединений определяется типами соединяемых элементов

Данилов Б. Р., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2014 Т. 3 № 31 С. 78–100

Актуальность и цели Проблема синтеза дискретных управляющих систем является одной из основных проблем математической кибернетики. В общем виде она состоит в построении для заданной дискретной функции ее оптимальной (в том или ином смысле) структурной реализации в рассматриваемом классе управляющих систем. Теоретические результаты, полученные при решении указанной проблемы, находят применение в различных прикладных областях, к числу которых ...

Добавлено: 2 декабря 2019 г.

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

Данилов Б. Р., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2015 Т. 4 № 36 С. 58–77

Добавлено: 2 декабря 2019 г.

Асимптотические оценки функции Шеннона в одной модели глубины схем из функциональных элементов с емкостными параметрами выходов элементов

Данилов Б. Р., Ложкин С. А., Прикладная математика и информатика 2018 № 59 С. 40–49

В работе предлагается метод синтеза усилительных схем из функциональных элементов (УСФЭ), позволяющий установить асимптотику функции Шеннона для обобщённой глубины УСФЭ – то есть глубины самой «плохой» функции алгебры логики, зависящей от заданных переменных – в специальном базисе (модели глубины), где глубина элемента определяется как его типом, так и степенью ветвления выхода в схеме. Асимптотическое поведение ...

Добавлено: 2 декабря 2019 г.

Synthesis of asymptotically size-optimal Boolean circuits protected from functionality inference

Lozhkin S. A., Shupletsov M. S., Danilov B.R., Математические вопросы криптографии 2017 Vol. 8 No. 2 P. 87–96

Предлагаются методы синтеза асимптотически оптимальных по сложности схем из функциональных элементов, которые реализуют произвольные функции алгебры логики от заданного числа переменных и обладают заданным уровнем защищенности от раскрытия их функциональности при сокрытии определенного числа локальных соединений. Эти методы опираются на особенности структуры схем из функциональных элементов в произвольном базисе, построенных с использованием методов обобщенного разложения ...

Добавлено: 1 декабря 2019 г.