• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Сложность линейных функций и функции голосования в базисе антицепных функций
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 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
  • More
Subject
News
September 11, 2026
How to Assess Students Knowledge in the Age of AI
A researcher at HSE University has proposed a flowchart to help lecturers decide how to assess students who use artificial intelligence. It shows where the use of AI should be restricted and where it can be incorporated into the learning process. The article has been published in IT Professional.
September 9, 2026
‘Balkan Hospitality Opens Doors: Studying Dialects on the Verge of Extinction
You cannot study spoken dialects from books. Instead, you need to go to a village, seek out its elders, and earn the trust of local residents before you can record hours of spontaneous stories. This is how Natalia Muravleva, Associate Professor at the Faculty of Humanities, conducts her research. Her internship in Serbia continued her long-standing study of dialects spoken by Macedonian settlers. In this interview, she discusses how diaspora cultural centres help researchers reach informants, why native speakers need to be interviewed only in their own language (otherwise, as she puts it, they may 'break'), and how a single field season helped her finalise her monograph. She also shares warm memories of autumn in Belgrade and of colleagues with whom grammar can be discussed in three languages at once.
September 9, 2026
Scientists Train Neural Network to Generate Process Plans from 3D Models
Researchers at the HSE FCS AI and Digital Science Institute have developed CAD2TechSpec, a framework that converts 3D models of mechanical parts into machining process plans—step-by-step instructions for machine tools. The solution aims to reduce the time required for the design and preparation of technical process documentation in mechanical engineering, aircraft manufacturing, and other high-tech industries. The study findings have been published in PeerJ Computer Science.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Сложность линейных функций и функции голосования в базисе антицепных функций

Вестник Московского университета. Серия 1: Математика. Механика. 2016. № 2. С. 51–52.
Podolskaya O.
Language: Russian
Keywords: линейная функцияфункция голосованиясложность булевых функций
Similar publications
Немонотонная сложность как обобщение инверсионной сложности
Mikhailovich A., Kochergin V., XXI век: итоги прошлого и проблемы настоящего плюс 2017 № 4(38) С. 98–105
The problem of the effective realization of Boolean functions and multi-valued logic functions by circuits in some infinite bases is considered. The bases consist of all monotone functions and finite number of non-monotone functions. The measure of the realization efficiency is non-monotone complexity. That is the number of non-monotone elements in the circuit (we assume ...
Added: September 28, 2017
Об оценках функций Шеннона сложности схем в некоторых бесконечных базисах
Podolskaya O., В кн.: Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.).: М.: Изд-во механико-математического факультета МГУ, 2016. С. 150–152.
В работе изучается сложность реализации булевых функций схемами из функциональных элементов в двух бесконечных полных базисах. Первый базис состоит из линейных и антицепных функций от любого числа переменных. В этом базисе установлена верхняя оценка сложности реализации произвольной булевой функции от n переменных порядка (logn)*n^{1/2}. Также в этом базисе доказана нижняя оценка порядка n^{1/2} наибольшей сложности ...
Added: March 14, 2017
Сложность реализации симметрических булевых функций схемами в базисе антицепных функций
Podolskaya O., Дискретная математика 2015 Т. 27 № 3 С. 95–107
Изучается сложность реализации булевых функций схемами из функциональных элементов в бесконечном базисе, состоящем из всех характеристических функций антицепей на булевом кубе. Установлено точное значение сложности реализации произвольной симметрической функции схемами в этом базисе. В частности, для функций четности и голосования от $n$ переменных при всех натуральных $n\geq1$ получены точные значения сложности: $\lfloor \frac{n+1}{2} \rfloor$ и ...
Added: March 14, 2017
Нижняя оценка мощности области определения универсальных функций для класса линейных булевых функций
Vyalyi M., Вороненко А. А., Дискретная математика 2016 Т. 28 № 4 С. 50–57
Доказана нетривиальная нижняя оценка (2+1/6)n для мощности области определения универсальной функции для класса линейных булевых функций, где n — число переменных. ...
Added: January 13, 2017
О сложности схем в базисах, содержащих монотонные элементы с нулевыми весами
Kochergin V., Mikhailovich A., Прикладная дискретная математика 2015 № 4 С. 24–31
Complexity of realization of Boolean functions and Boolean function systems over a basis which consist of all monotone functions and finite number of non-monotone funcitons is investigated. The weight of any monotone function from the basis equal 0. The weight of non-monotone function is positive. A. A. Markov studied special case of such basis. The ...
Added: December 8, 2015
Some Extension of Inversion Complexity of Boolean Functions
A.V. Mikhailovich, V. V. Kochergin, / Series math "arxiv.org". 2015.
The minimum number on NOT gates in a Boolean circuits computing a Boolean function f is called inversion complexity of f. In 1957, A.A. Markov determined inversion complexity of every Boolean function. In the paper we consider circuits over arbitrary basis that consist of all monotone functions (with zero weight) and finite nonempty set of nonmonotone functions (with ...
Added: June 15, 2015
О нижних оценках сложности схем в базисе антицепных функций
Podolskaya O., Вестник Московского университета. Серия 1: Математика. Механика 2013 Т. 2 С. 17–23
The antichain function is a characteristic function of antichain on the Boolean cube. The set of antichain functions is an infinite complete basis. We study computational complexity of Boolean functions over antichain functional basis. In this paper we prove $\sqrt{n}$ asymptotic lower bound on the computational complexity of the linear function, the majority function and ...
Added: May 30, 2015
Статичное равновесие Курно – Нэша и рефлексивные игры олигополии: случай линейных функций спроса и издержек
Dusushe O. M., Экономический журнал Высшей школы экономики 2006 Т. 10 № 1 С. 3–32
В классе линейных функций спроса и издержек фирм исследуется проблема статичного равновесия Курно с использованием некооперативных статических и стратегических рефлексивных игр различных порядков. В статье вводятся: концепция конкурентоспособности фирмы в равновесии Курно для n фирм; определение предположительных вариаций как первых производных от функций постоянной прибыли Штакельберга; и понятие последовательно-группового порядка в игре n персон. Анализируются ...
Added: October 19, 2012
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit