### ?

## Good covers are algorithmically unrecognizable

Cornell University
,
2012.

Dmitry Tonkonog, Tancer M.

A good cover in R^d is a collection of open contractible sets in R^d such that the intersection of any subcollection is either contractible or empty. Motivated by an analogy with convex sets, intersection patterns of good covers were studied intensively. Our main result is that intersection patterns of good covers are algorithmically unrecognizable.
More precisely, the intersection pattern of a good cover can be stored in a simplicial complex called nerve which records which subfamilies of the good cover intersect. A simplicial complex is topologically d-representable if it is isomorphic to the nerve of a good cover in R^d. We prove that it is algorithmically undecidable whether a given simplicial complex is topologically d-representable for any fixed d \geq 5. The result remains also valid if we replace good covers with acyclic covers or with covers by open d-balls.
As an auxiliary result we prove that if a simplicial complex is PL embeddable into R^d, then it is topologically d-representable. We also supply this result with showing that if a "sufficiently fine" subdivision of a k-dimensional complex is d-representable and k \leq (2d-3)/3, then the complex is PL embeddable into R^d.

Language:
English

Sadovnikov A., Ermak T., Yakovlev P., , in : Proceedings of the 26th Conference of Open Innovations Assosiation FRUCT. : IEEE, 2020. P. 646-651.

In this paper, we describe the development of a novel statistical potential for the prediction of antibody-antigen complexes (docking), which play key role in in silico immunotherapy discovery. The developed statistical potential is then used to improve the accuracy of an existing docking algorithm. We also present a new dataset for the development and comparison ...

Added: September 24, 2021

Yakovlev E., Епифанов В. Ю., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2018 № 2(46) С. 47-55

The objects of research are two-dimensional compact polyhedra with an Euclidean cell decomposition, which are pseudomanifolds with boundary. The goal is to create new effective algorithms for computing the bases of absolute and relative homology groups modulo 2. Proposed a reduction procedure to a similar problem for polyhedra of lesser dimensionality, containing fewer number of cells. We ...

Added: October 4, 2018

Klimenkova O., Shchur L., Journal of Physics: Conference Series 2021 Vol. 1740 No. 012030 P. 1-5

We propose a novel algorithm for the construction of the sparse, nonetheless, the massive and rigid structure. The generated structures possess two significant properties reminiscent of the metallic foams. Firstly, the weight of the structures can be as low as the percent of the bulk one. Secondly, the structures are mechanically rigid. The structures are ...

Added: January 22, 2021

Gnatenko A., Zakharov V., Proceedings of the Institute for System Programming of the RAS 2018 Vol. 30 No. 3 P. 303-324

The syntax and semantics of the new temporal logic LP-CTL * designed for the formal specification of the behavior of sequential responsive programs, modeled by automata-transducers (transducers) over semigroups, are developed. An algorithm is developed for verifying the feasibility of the formulas of the proposed temporal logic on models represented by finite transducers working on ...

Added: June 14, 2018

Ivanov I., Ivanov O., Uvaysov S. U. et al., , in : 2016 International Siberian Conference on Control and Communications (SIBCON). Proceedings. : M. : HSE, 2016.

In this paper the algorithm for battery charge control of renewable energy sources - wind turbine and solar panel. Every operating block is also described with specifying the dependencies. The principle of the charging current limitation that prevents battery failure as a result of a strong internal resistance increase while preliminary deep discharge is considered. ...

Added: September 12, 2016

Bogataya S., Bogatyi S., Кудрявцева Е. А., Математический сборник 2012 Т. 203 № 4 С. 103-118

We prove that the bound from the theorem on ‘economic’ maps is best possible. Namely, for m > n + d we construct a map from an n-dimensional simplex to an m-dimensional Euclidean space for which (and for any close map) there exists a d-dimensional plane whose preimage has cardinality not less than the upper ...

Added: October 30, 2012

Antonina A. Arkhipova, Ivanov S., Zhuravitskii S. et al., Nanophotonics 2022 Vol. 11 No. 16 P. 3653-3661

We report the experimental observation of the periodic switching of topological edge states between two dimerized fs-laser written waveguide arrays. Switching occurs due to the overlap of the modal fields of the edge states from topological forbidden gap, when they are simultaneously present in two arrays brought into close proximity. We found that the phenomenon ...

Added: October 17, 2022

Zhalinsky A. E., Российский криминологический взгляд 2008 № 4 С. 193-197

1. Description of the problem. Instrumental analysis makes it possible to find the arguments of adjudication on the bounders and structure of corpus delicti, its correlation to criminal and filling-up legislation. 2. Initial theses. Corpus delicti is regarded as that expressed in criminal law doctrine result of reorganization of orders of criminal law into other ...

Added: October 14, 2012

Lazarev A. A., Carballo L., Vakhania N. et al., , in : IFAC Proceedings Volumes 14th IFAC Symposium on Information Control Problems in Manufacturing, Bucharest, 23-25 May 2012. : Бухарест : IFAC Technical Committee, 2012. P. 381-386.

We present an approach based on a two-stage ltration of the set of feasible solutions for the multiprocessor job-shop scheduling problem. On the rst stage we use extensive dominance relations, whereas on the second stage we use lower bounds. We show that several lower bounds can eciently be obtained and implemented. ...

Added: February 12, 2013

Фотеева А. В., Феофилова А. Е., Ростова Н. Б. et al., Медико-фармацевтический журнал "Пульс" 2022 Т. 24 № 4 С. 38-43

Abstract. The modern regulatory requirements for pharmaceutical development, stricter of requirements of
medicinal products (MP) quality standards, the experience of manufacturers and development companies in terms of MP pharmaceutical development revealed need to create solutions that minimize the risk of medicinal product quality deviations, guaranteeing the release of effective and safe MP with the planned quality. The aim of these study is to ...

Added: May 13, 2022

Scherbakova A., / НИУ ВШЭ. Series WP BRP "Linguistics". 2020.

Added: December 2, 2020

Penzar D., Krivozubov M., Spirin S., BMC Bioinformatics 2018 Vol. 19 No. 374 P. 1-14

Background. Many algorithms and programs are available for phylogenetic reconstruction of families of proteins. Methods used widely at present use either a number of distance-based principles or character-based principles of maximum parsimony or maximum likelihood.
Results. We developed a novel program, named PQ, for reconstructing protein and nucleic acid phylogenies following a new character-based principle. Being ...

Added: October 26, 2018

Beaudou L., Ghazi K., Kahn G. et al., Journal of Computational Science 2018 Vol. 25 P. 446-455

Let P be a poset and S be a set of elements. A well-known method for representing P is called a bit-vector encoding and consists in associating to each element of P a subset of S such that the order relation between two elements coincides with their subsets inclusion. The size of this encoding is ...

Added: April 11, 2019

Potapova T. A., Молотков С. Н., Письма в Журнал экспериментальной и теоретической физики 2013 Т. 97 № 6 С. 384-391

The symmetry nature of the appearance of specific surface (edge) states at the boundaries of low_dimension structures with the symmetry of ribbons (borders) invariant with respect to time reversal is discussed. Symmetry reasons for the stability of such states against the elastic scattering from nonmagnetic impurities have been revealed. ...

Added: October 11, 2013

Aminev D., Журков А. П., Козырев А. А. et al., Труды Научно-исследовательского института радио 2014 № 4 С. 11-17

The problem of providing the testability of the direction-finding equipment position (DFEP) is considered. Structural circuits RDF systems and DFEP is presented. Enlarged and more detailed schemes of algorithms and algorithm of control joints DFEP is given. ...

Added: December 12, 2015

Pavolotsky A. V., В кн. : Информатика. Учебник для 9 класса. Ч. 2.: М. : Баласс, 2012. Гл. 1. С. 8-87.

В качестве продолжения линии "Алгоритмизация и программирование" в главе рассматриваются основы систем счисления, символьный и строковый типы данных, многомерные массивы, принципы рекурсивного программирования, работа с файлами и со случайными числами. ...

Added: March 14, 2013

Гнатенко А. Р., Zakharov V., В кн. : Дискретные модели в теории управляющих систем: Х Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды. : МГУ, МАКС Пресс, 2018. С. 131-133.

The expressive power of a new variant of temporal logic LP-CTL * is studied. In this logic, two classes of LP-1-LTL and LP-n-LTL formulas were distinguished and it was shown that the LP-1-LTL fragment more expressive than the known temporal logic of linear time LTL, and the LP-n-LTL fragment has the same expressive possibilities as ...

Added: June 14, 2018

Aleskerov F. T., Shvydun S., , in : Studies in Computational Intelligence. * 1. Vol. 812: Complex Networks and Their Applications VII.: Springer, 2019. P. 94-103.

We propose a model that evaluates how much a network has changed over time in terms of its structure and a set of central elements. The difference of structure is evaluated in terms of node-to-node influence using known nodes correspondence models. To analyze the changes in nodes centralities we adapt an idea of interval orders ...

Added: December 4, 2018

Голяев Ю. Д., Иванов М. А., Колбас Ю. Ю. et al., Системотехника: Системные проблемы надежности, качества и информационных технологий 2016 № 11

The methods of increasing the accuracy of inertial measurement units (IMU) on Zeeman laser gyros and quartz accelerometers are considered. Design solutions for the rigid installation of the IMU components with the exact reference of the measurement axes and also for IMU maintainability are presented. The principles of quasifourmode Zeeman laser gyro, mathematical algorithms, providing ...

Added: March 14, 2017

Trubochkina N. K., Кондратьев Н. В., Мир техники кино 2015 Т. 37 № 3 С. 6-16

A new approach in the development of three-dimensional movies without glasses, but rather, the technique of fantastic graphics and media worlds creating with the help of mathematics and computer software, as the basis for the subsequent encoding a lenticular screen, is proposed. A parametric fractals calculation model, taking into account the position of the virtual ...

Added: October 23, 2015

Stepanov E., Buttazzo G., Pratelli A. et al., Berlin : Springer, 2009

Recently much attention has been devoted to the optimization of transportation networks in a given geographic area. One assumes the distributions of population and of services/workplaces (i.e. the network's sources and sinks) are known, as well as the costs of movement with/without the network, and the cost of constructing/maintaining it. Both the long-term optimization and ...

Added: December 12, 2018

Gavrilovich M., Bulletin of Symbolic Logic 2018

We introduce a simple formal syntax and use it to rewrite in a concise, uniform and intuitive way several standard denitions in topology which are usually expressed in words. The denitions include compact, discrete, connected, and totally disconnected spaces, dense image, induced topology, closed subsets, and some of the separation axioms. The syntax is of ...

Added: October 19, 2018

A. N. Krenke, R. B. Sandlersky, A. S. Baybar et al., Известия РАН. Серия биологическая. 2023 Vol. 50 No. 1 P. S85-S99

Four main models of the appearance of boundaries (in a particular case, integrity), arising from the theory of nonlinear dynamic systems, are considered briefly. On the basis of Kotelnikov’s fundamental sampling theorem and, accordingly, general information theory, the character of a distinguished boundary as a function of the sampling frequency in a spatial series with a ...

Added: December 2, 2022

Безруков В. А., В кн. : Языки в современном мире: материалы VIII международной конференции. : М. : КДУ, 2009. С. 111-117.

Added: December 14, 2014