• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Preprints
  • Complexity of the variable-free fragment of the weak Grzegorczyk logic
  • 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 7, 2026
Biologists Discover 'Molecular Fingerprint' of Preeclampsia
Researchers at HSE University employed a new method to model hypoxia in placental cells during pregnancies complicated by preeclampsia and identified molecular markers of tissue hypoxia. Since hypoxia is one of the key mechanisms underlying preeclampsia, these findings are important for a more accurate and timely diagnosis of the disease and for the development of effective treatment methods. The paper has been published in Placenta.
September 7, 2026
‘Speech, Facial Expressions, and Gestures Cannot Lie
Would you like to know whether a speaker’s trembling voice or an accidental gesture can give them away? At HSE University in Nizhny Novgorod, researchers are developing an algorithm that analyses speech, facial expressions, and gestures, and determines whether information is truthful with 92% accuracy. The project has applications ranging from forensic examination and bank recruitment to fundamental research. Anna Khomenko, head of the research group and Senior Research Fellow at the Centre for Language and Brain at the HSE Faculty of Humanities in Nizhny Novgorod, explains how students and researchers are working together to create a corpus of video recordings, train a classifier, and prepare to introduce computer vision technology.
September 4, 2026
Time to Showcase Your Research: Applications Are Now Open for Student Research Paper Competition 2026
Taking part in the Student Research Paper Competition (SRPC) gives you an opportunity to present your research to experts, receive an independent assessment, and determine the future direction of your work. The competition is open to students graduating in 2026 not only from HSE University but from universities in Russia and abroad. Papers may be submitted in Russian and English, and in some fields also in French, German, and Spanish.

 

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

?

Complexity of the variable-free fragment of the weak Grzegorczyk logic

arXiv , 2022.
Rybakov M., Агаджанян И. А.
Priority areas: mathematics
Language: Russian
Full text
Text on another site
Keywords: вычислительная сложностьмодальная логикаслабая логика Гжегорчика
Publication based on the results of:
Доказательства и модели (2021)
Similar publications
Infinitely many graph manifolds with unique geometrical piece that admit arbitrarily many Anosov flows
Pochinka O., Shmukler V., / Series math.RT "arXiv:1808.06395 [math.RT]". 2026.
Anosov flows have a long and rich history, firstly motivated by the study of geodesic flows in negative curvature surface by Anosov and Sinai. Not every closed manifold admits an Anosov flow for well-known reasons: the fundamental group of a 3-manifold M admitting an Anosov flow must have exponential growth, and M must be universally covered by R3. Nevertheless, there ...
Added: August 31, 2026
New bound on S1× S2-setting Bell locality of a nonseparable Werner state
Loubenets E. R., / Series arxiv.org "quant-ph". 2026. No. 2607.18050.
In many quantum applications it is important to know whether or not a Bell nonlocal two-qudit state exhibits its nonlocality under correlation scenarios with some given numbers S1,S2≥1 of generalized quantum measurements at two sites. In the present article, we find analytically a new general locality condition sufficient for a  nonseparable Werner state with a ...
Added: July 21, 2026
On functional equations for Chow polylogarithms
Bolbachan V., / Series math "arxiv.org". 2024.
Chow polylogarithms are some special functions arising in explicit description of the Beilinson regulator map. The most interesting functional equation for this function reflects its vanishing on the boundary in the Bloch's cycle complex. We show that this functional equation formally follows from more simple ones, namely skew-symmetry, functoriality and multiplicativity. To prove this, we study ...
Added: July 16, 2026
On Goncharov’s conjecture in next to Milnor degree
Bolbachan V., / Series math "arxiv.org". 2024.
Let K be a field of characteristic zero. We prove that its motivic cohomology in degree m−1 and weight m is rationally isomorphic to the cohomology of the polylogarithmic complex. This gives a partial extension of A. Suslin theorem describing the indecomposable K3 of a field. ...
Added: July 16, 2026
Statistical inference based on band-limited kernels: Rational-infinitely divisible distributions and beyond
Panov V., Ryabchenko A., / Series arXiv "stat.ME". 2026. No. 2607.05048.
This paper investigates the problem of statistical inference for a mixture distribution consisting of a discrete and a continuous component, with a particular focus on the class of rational-infinitely divisible distributions. We consider non-parametric estimation of both components of the mixture as well as the quasi-L{é}vy measure, assuming that the mixture belongs to the class ...
Added: July 9, 2026
Modal Products and Around
Shehtman V. B., Gagarin A., , in: Graph Games and Logic Design. Recent Developments and Further Directions. (TREN, volume 66)Vol. 66.: Springer, 2026. Ch. 17 P. 419–450.
The chapter contains an overview of results on products of propositional modal logics and related constructions: semiproducts, Segerberg squares, and others. We focus mainly on axiomatizations, finite model property, and decidability; we also sketch connections with classical and modal predicate logics. In some cases we give ideas of proofs, especially of those using games. ...
Added: June 30, 2026
Strong Approximations for Markov Chains Weakly Converging to Diffusions
Konakov V., Kucher D., Mammen E., / Series arXiv "math". 2026. No. 2606.11142v1.
In this paper, we construct strong approximations for discrete-time Markov chains weakly converging to continuous diffusion processes, as well as for their perturbed counterparts. Under the assumption of bounded coefficients, we construct closely coupled versions of these processes on a shared probability space. In particular, for both non-degenerate and degenerate cases, we maximize the probability ...
Added: June 11, 2026
Universal Comparison Methodology for Hough Transform Approaches
Kazimirov D., Vitalii Gulevskii, Kroshnin A. et al., Mathematics 2026 Article 1136
The Hough transform (HT) is widely used in computer vision, tomography, and neural networks. Numerous algorithms for HT computation have been proposed, making their systematic comparison essential. However, existing comparative methodologies are either non-universal and limited to certain HT formulations, or task-oriented, relying on application-specific criteria that do not fully capture algorithmic properties. This paper ...
Added: May 28, 2026
Bifurcations and Structural Stability of Generic PC-HC Families
Dorovskiy A., / Series arXiv "math". 2026.
In this paper the structural stability of generic families of vector fields of the PC-HC class on the two-dimensional sphere is proved. A classification of these families up to moderate equivalence in neighborhoods of their large bifurcation supports is presented, based on such invariants as the configuration and the characteristic set. The realization lemma is proved. ...
Added: May 14, 2026
On the minimum number of maximal distance-k independent sets in trees
Taletskii D., / Series arXiv "math". 2026.
A vertex subset of a graph is called a \textit{distance-$k$ independent set} if the distance between any two of its distinct vertices is at least $k + 1$. For all $n,k \geq 1$, we determine the minimum possible number of inclusion-wise maximal distance-$k$ independent sets among all $n$-vertex trees. It equals~$n$ if $n \leq k ...
Added: May 1, 2026
On Arithmetic Mirror Symmetry for smooth Fano fourfolds
Ovcharenko M., / Series arXiv "math". 2026.
We introduce an explicit class of tempered Laurent polynomials in the sense of Villegas and Doran--Kerr in n⩽4 variables including all Landau--Ginzburg models for smooth Fano threefolds with very ample anticanonical class. We check that it contains Landau--Ginzburg models for various Fano fourfolds which are complete intersections in smooth toric varieties and Grassmannians of planes, ...
Added: April 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.
We deal with the global in time weak solutions to the 1D compressible Navier-Stokes system of equations for large discontinuous initial data and nonhomogeneous boundary conditions of three standard types. We prove the Lipschitz-type continuous dependence of the solution $(\eta,u,\theta)$, in a norm slightly stronger than $L^{2,\infty}(Q)\times L^2(Q)\times L^2(Q)$,  on the initial data $(\eta^0,u^0,e^0)$ in a ...
Added: April 18, 2026
On the dimension of the space of static potentials on three-manifolds
Medvedev V., / 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 ...
Added: April 3, 2026
Using predefined vector systems to speed up neural network multimillion class classification
Gabdullin N., Androsov I., / Series Computer Science "arxiv.org". 2026.
Label prediction in neural networks (NNs) has O(n) complexity proportional to the number of classes. This holds true for classification using fully connected layers and cosine similarity with some set of class prototypes. In this paper we show that if NN latent space (LS) geometry is known and possesses specific properties, label prediction complexity can ...
Added: April 2, 2026
О СЛОЖНОСТИ ПРОБЛЕМЫ ТОТАЛЬНОЙ ВЫВОДИМОСТИ В НЕУКОРАЧИВАЮЩИХ И КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИКАХ
Dudakov S., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18
In this paper we study the problem of total derivability in context-free, noncontracting, and context-sensitive grammars. Given a grammar and a terminal word, one has to determine whether there exists a derivation of this word which uses each production no less than a given number of times. It is proved that the problem of total ...
Added: March 18, 2026
Homogeneous maximizers of the Blaschke-Santalo-type functionals
Kolesnikov A., / Series arXiv "math". 2025.
We study Blaschke--Santal{ó}-type inequalities for N>=2  sets (functions) and a special class of cost functions. In particular, we prove new results about reduction of the maximization problem for the Blaschke--Santal{ó}-type functional to homogeneous case (functional inequalities on the sphere) and extend the symmetrization argument to the case of  N>2 sets. We also discuss links to the ...
Added: February 13, 2026
Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection
Sorokin K., Beketov M., Онучин А. et al., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.
Community detection in complex networks is a fundamental problem, open to new approaches in various scientific settings. We introduce a novel community detection method, based on Ricci flow on graphs. Our technique iteratively updates edge weights (their metric lengths) according to their (combinatorial) Foster version of Ricci curvature computed from effective resistance distance between the ...
Added: January 15, 2026
О схлопывании вероятностных иерархий. I
Speranski S. O., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Added: December 27, 2025
О кванторной версии модальной логики Белнапа–Данна
Грефенштейн А. В., Speranski S. O., Математический сборник 2024 Т. 215 № 3 С. 37–69
Разрабатывается кванторная версия пропозициональной модальной логики BK из статьи С. П. Одинцова и Х. Вансинга, в основе которой лежит (немодальная) система Белнапа–Данна; мы будем обозначать эту версию через QBK. Сначала с помощью метода канонических моделей будет доказано, что QBK — как и некоторые важные её расширения — сильно полна относительно подходящей семантики возможных миров. Затем мы ...
Added: December 26, 2025
On finding formal power-logarithmic expansions of solutions to q-difference equations
Gaianov N., Parusnikova A., / Cornell University. Серия math "arxiv.org". 2025.
An algebraic q-difference equation is considered. A sufficient condition for the existence of a formal power-logarithmic expansion of a solution to such an equation in the neighborhood of zero is proposed. An example of applying this sufficient condition for constructing a formal expansion of a solution to a certain q-difference analogue of the fifth Painlevé equation ...
Added: December 25, 2025
Ideal of the variety of flexes of plane cubics
Popov V., / Series arXiv "math". 2025. No. 2502.01539.
We prove that the variety of flexes of algebraic curves of degree 3 in the projective plane is an ideal theoretic complete intersection in the product of a two-dimensional and a nine-dimensional projective spaces. ...
Added: December 16, 2025
Некоторые классификации сложности задачи о вершинной 3-раскраске
Дахно Г. С., Malyshev D., Математические заметки 2026 Т. 119 № 3 С. 360–376
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных ...
Added: November 26, 2025
NP-полнота игры “Ханаби” при минимальных параметрах
Onoprienko A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
We study the algorithmic complexity of the cooperative card game Hanabi. The feature of Hanabi is that players see each other’s cards but not their own, and exchange information through hints. Even in the model with one player who has full information about the deck, Hanabi remains NP-hard. We found the minimal parameters ofthe game ...
Added: November 23, 2025
Two Types of Filtrations for wK4 and Its Relatives
Kudinov A., Shapirovsky I., Studia Logica 2025 P. 1–25
We study the finite model property of subframe logics with expressible transitive reflexive closure modality. For m > 0, let Lm be the logic defined by axiom ♦^{m+1}p → ♦p ∨ p. We construct quotient filtrations for the logics Lm, which implies that these logics and their tense counterparts have the finite model property. Then, we construct selective filtrations ...
Added: October 14, 2025
  • 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