• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Polynomial Threshold Functions for Decision Lists
  • 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
October 7, 2026
‘Our Team Consists of True Leaders in Their Respective Academic Disciplines
The HSE International Centre of Decision Choice and Analysis studies a wide range of methods for analysing decision-making and possible scenarios for the development of natural, socio-economic, and political phenomena using various mathematical models. The application of advanced mathematical methods to forecasting helps to prevent negative outcomes and avoid erroneous decisions. The HSE News Service spoke to the centre’s director, Prof. Fuad Aleskerov, about its work.
October 6, 2026
International N5 Symposium ‘Neural Networks and Nonlinearity in Nizhny Novgorod Brings Together Scientists from Russia and Serbia
The International N5 Symposium ‘Neural Networks and Nonlinearity in Nizhny Novgorod’ was held at the Nizhny Novgorod House of Scientists from September 23 to 26. The event was organised by HSE University–Nizhny Novgorod and the Nizhny Novgorod House of Scientists, with the participation of Sberbank and the Institute of Physics Belgrade. The symposium was held for the second time: the first conference took place in 2025 and attracted considerable interest from the academic community.
October 5, 2026
‘The Climate Transition Is Not Necessarily a Limitation for Business
Linara Khadimullina works in the field of low-carbon development. In an interview with the Young Scientists of HSE project, she spoke about why nature is not just a beautiful backdrop, her research on the role of sustainable corporate governance in reducing greenhouse gas emissions, and growing plants as a source of inspiration.

 

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

?

Polynomial Threshold Functions for Decision Lists

Ch. 52. P. 52:1–52:12.
Vladimir Podolskii, Nikolay V. Proskurin
Language: English
DOI
Text on another site
Keywords: Threshold functiondecision listHamming ball
Publication based on the results of:
Mathematical methods inthe studies of definitional complexity, computational complexity and formal language (2023)

In book

33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, Volume 248
Saarbrücken, Вадерн: Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022.
Similar publications
On the Decision Tree Complexity of Threshold Functions
Chistopolskaia A., Podolskii V. V., Theory of Computing Systems 2022
In this paper we study decision tree models with various types of queries. For a given function it is usually not hard to determine the complexity in the standard decision tree model (each query evaluates a variable). However in more general settings showing tight lower bounds is substantially harder. Threshold functions often have non-trivial complexity ...
Added: September 13, 2022
On the Decision Tree Complexity of Threshold Functions
Chistopolskaia A., Podolskii V. V., , in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, ProceedingsVol. 12159.: Springer, 2020. P. 198–210.
In this paper we study decision tree models with various types of queries. For a given function it is usually not hard to determine the complexity in the standard decision tree model (each query evaluates a variable). However in more general settings showing tight lower bounds is substantially harder. Threshold functions often have non-trivial complexity ...
Added: September 7, 2020
On the Number of Irreducible Points in Polyhedra
Chirkov A., Zolotykh N., Graphs and Combinatorics 2016 Vol. 32 No. 5 P. 1789–1803
An integer point in a polyhedron is called irreducible iff it is not the midpoint of two other integer points in the polyhedron. We prove that the number of irreducible integer points in n-dimensional polytope P is at most O(m⌊n2⌋logn−1γ), where n is fixed and P is given by a system of m linear inequalities with integer coefficients not exceeding (by absolute value) γ. This bound ...
Added: February 16, 2016
  • 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