73 citations · 222 across the 11 of their papers we have counts for
11 papers
Topological measures in weighted hypergraphs
Ekaterina Vasilyeva, Liubov Tupikina, Daniil Musatov +3
Higher-order interactions introduce an additional structural dimension to complex networks, requiring consistent generalizations of classical topological measures. In hypergraphs,…
Structural Complexity of Rational Interactive Proofs
Daniil Musatov, Georgii Potapov
This is the full version of a paper submitted to the Computability in Europe (CiE 2023) conference, with all proofs omitted there. In 2012 P. D. Azar and S. Micali introduced a new…
Why are there six degrees of separation in a social network?
Ivan Samoylenko, David Aleja, Eva Primo +11
A wealth of evidence shows that real world networks are endowed with the small-world property i.e., that the maximal distance between any two of their nodes scales logarithmically…
Vector Centrality in Hypergraphs
Kirill Kovalenko, Miguel Romance, Ekaterina Vasilyeva +9
Identifying the most influential nodes in networked systems is of vital importance to optimize their function and control. Several scalar metrics have been proposed to that effect,…
Predicting transitions in cooperation levels from network connectivity
A. Zhuk, I. Sendiña-Nadal, I. Leyva +4
Networks determine our social circles and the way we cooperate with others. We know that topological features like hubs and degree assortativity affect cooperation, and we know tha…
D-dimensional oscillators in simplicial structures: odd and even dimensions display different synchronization scenarios
X. Dai, K. Kovalenko, M. Molodyk +8
From biology to social science, the functioning of a wide range of systems is the result of elementary interactions which involve more than two constituents, so that their descript…
Growing scale-free simplices
K. Kovalenko, I. Sendiña-Nadal, N. Khalil +6
The past two decades have seen significant successes in our understanding of complex networked systems, from the mapping of real-world social, biological and technological networks…
Space-Bounded Kolmogorov Extractors
Daniil Musatov
An extractor is a function that receives some randomness and either "improves" it or produces "new" randomness. There are statistical and algorithmical specifications of this notio…
Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization
Daniil Musatov
Many theorems about Kolmogorov complexity rely on existence of combinatorial objects with specific properties. Usually the probabilistic method gives such objects with better param…
Variations on Muchnik's Conditional Complexity Theorem
Daniil Musatov, Andrei Romashchenko, Alexander Shen
Muchnik's theorem about simple conditional descriptions states that for all strings and there exists a short program transforming to that has the least possible…
Extractors and an efficient variant of Muchnik's theorem
Daniil Musatov
Muchnik's theorem about simple conditional descriprion states that for all words and there exists a short program transforming to that has the least possible le…