?
A combinatorial formula for affine Hall–Littlewood functions via a weighted Brion theorem
Selecta Mathematica, New Series. 2016. Vol. 22. No. 3. P. 1703–1747.
Фейгин Б. Л., Махлин И. Ю.
We present a new combinatorial formula for Hall–Littlewood functions associated with the affine root system of type (Formula presented.), i.e., corresponding to the affine Lie algebra (Formula presented.). Our formula has the form of a sum over the elements of a basis constructed by Feigin, Jimbo, Loktev, Miwa and Mukhin in the corresponding irreducible representation. Our formula can be viewed as a weighted sum of exponentials of integer points in a certain infinite-dimensional convex polyhedron. We derive a weighted version of Brion’s theorem and then apply it to our polyhedron to prove the formula. © 2016 Springer International Publishing
Ключевые слова: Kolmogorov complexitySophisticationLogical depthAlgorithmic sufficient statisticsBusy Beaver function
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Семенов А. Л., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 527 № S С. 7–12
В работе предлагается система определений для основных понятия теории вычислимости, лежащих в основе математики цифрового мира: алгоритм, вычислимость, исчисление, сложность объекта, приближенная к современным представлениям. Рассматриваются иерархии конечного и проблема непротиворечивости. ...
Добавлено: 6 декабря 2025 г.
Семенов А. Л., Шень А., Верещагин Н. К., Theory of Probability and its Applications, USA 2024 Vol. 68 No. 4 P. 582–606
Добавлено: 16 января 2025 г.
Баувенс Б. Ф., Zimand M., Journal of the ACM 2023 Vol. 70 No. 2 Article 9
Добавлено: 22 марта 2023 г.
Добавлено: 23 декабря 2022 г.
Верещагин Н. К., Theoretical Computer Science 2023 Vol. 940 P. 108–122
Добавлено: 19 декабря 2022 г.
Милованов А. С., , in: Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings.: Springer, 2021. Ch. 17 P. 283–295.
Добавлено: 11 августа 2021 г.
Баувенс Б. Ф., Блинников И. А., , 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. 130–141.
Добавлено: 5 февраля 2021 г.
Баувенс Б. Ф., , in: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)Vol. 154: Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. P. 46:1–46:14.
Добавлено: 20 марта 2020 г.
Зиновьев А. В., Korablev N. P., International Journal of Osteoarchaeology 2017 Vol. 27 No. 2 P. 305–311
Добавлено: 6 марта 2020 г.
Shen A., Верещагин Н. К., , in: Computability and Complexity.: Berlin: Springer, 2017. P. 669–737.
Добавлено: 26 октября 2018 г.
Милованов А. С., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 833–848
Добавлено: 17 октября 2018 г.
Пособин Г. И., Shen A., Andreev M., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–24.
Добавлено: 11 октября 2018 г.
Рубцов А. А., , in: Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings.: Cham: Springer, 2018. P. 553–565.
Добавлено: 12 сентября 2018 г.
Милованов А. С., , in: Sailing Routes in the World of Computation.: Springer, 2018. P. 287–296.
Добавлено: 4 сентября 2018 г.
Милованов А. С., , in: Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017)Vol. 10304.: Luxemburg: Springer, 2017. P. 232–244.
Добавлено: 15 октября 2017 г.
Добавлено: 12 октября 2017 г.
Верещагин Н. К., Милованов А. С., , in: 32nd Computational Complexity Conference.: Вадерн: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1–18.
A fundamental notion in Algorithmic Statisticsis that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution. In this paper, we suggest three definitions of a plausible statistical ...
Добавлено: 12 октября 2017 г.
Верещагин Н. К., Баувенс Б. Ф., Makhlin A. и др., Computational Complexity 2018 Vol. 27 No. 1 P. 31–61
Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of ...
Добавлено: 22 апреля 2017 г.
Верещагин Н. К., Милованов А. С., / Series Technical report "Electronic Colloquium on Computational Complexity". 2017. No. TR17-043.
Добавлено: 7 марта 2017 г.
Верещагин Н. К., Shen A., Lecture Notes in Computer Science 2017 Vol. 10010 P. 669–737
Добавлено: 13 февраля 2017 г.
Bienvenu L., Desfontaines D., Shen A., Logical Methods in Computer Science 2016 Vol. 12 No. 2
The halting problem is undecidable --- but can it be solved for "most" inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural framework of optimal machines (considered in algorithmic information theory) using the ...
Добавлено: 7 февраля 2017 г.