---
_id: '1682'
abstract:
- lang: eng
text: 'We study the problem of robust satisfiability of systems of nonlinear equations,
namely, whether for a given continuous function f:K→ ℝn on a finite simplicial
complex K and α > 0, it holds that each function g: K → ℝn such that ||g -
f || ∞ < α, has a root in K. Via a reduction to the extension problem of maps
into a sphere, we particularly show that this problem is decidable in polynomial
time for every fixed n, assuming dimK ≤ 2n - 3. This is a substantial extension
of previous computational applications of topological degree and related concepts
in numerical and interval analysis. Via a reverse reduction, we prove that the
problem is undecidable when dim K > 2n - 2, where the threshold comes from
the stable range in homotopy theory. For the lucidity of our exposition, we focus
on the setting when f is simplexwise linear. Such functions can approximate general
continuous functions, and thus we get approximation schemes and undecidability
of the robust satisfiability in other possible settings.'
article_number: '26'
author:
- first_name: Peter
full_name: Franek, Peter
last_name: Franek
- first_name: Marek
full_name: Krcál, Marek
id: 33E21118-F248-11E8-B48F-1D18A9856A87
last_name: Krcál
citation:
ama: Franek P, Krcál M. Robust satisfiability of systems of equations. Journal
of the ACM. 2015;62(4). doi:10.1145/2751524
apa: Franek, P., & Krcál, M. (2015). Robust satisfiability of systems of equations.
Journal of the ACM. ACM. https://doi.org/10.1145/2751524
chicago: Franek, Peter, and Marek Krcál. “Robust Satisfiability of Systems of Equations.”
Journal of the ACM. ACM, 2015. https://doi.org/10.1145/2751524.
ieee: P. Franek and M. Krcál, “Robust satisfiability of systems of equations,” Journal
of the ACM, vol. 62, no. 4. ACM, 2015.
ista: Franek P, Krcál M. 2015. Robust satisfiability of systems of equations. Journal
of the ACM. 62(4), 26.
mla: Franek, Peter, and Marek Krcál. “Robust Satisfiability of Systems of Equations.”
Journal of the ACM, vol. 62, no. 4, 26, ACM, 2015, doi:10.1145/2751524.
short: P. Franek, M. Krcál, Journal of the ACM 62 (2015).
date_created: 2018-12-11T11:53:27Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2021-01-12T06:52:30Z
day: '01'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1145/2751524
intvolume: ' 62'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1402.0858
month: '08'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '5466'
quality_controlled: '1'
scopus_import: 1
status: public
title: Robust satisfiability of systems of equations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 62
year: '2015'
...
---
_id: '1710'
abstract:
- lang: eng
text: 'We consider the hollow on the half-plane {(x, y) : y ≤ 0} ⊂ ℝ2 defined by
a function u : (-1, 1) → ℝ, u(x) < 0, and a vertical flow of point particles
incident on the hollow. It is assumed that u satisfies the so-called single impact
condition (SIC): each incident particle is elastically reflected by graph(u) and
goes away without hitting the graph of u anymore. We solve the problem: find the
function u minimizing the force of resistance created by the flow. We show that
the graph of the minimizer is formed by two arcs of parabolas symmetric to each
other with respect to the y-axis. Assuming that the resistance of u ≡ 0 equals
1, we show that the minimal resistance equals π/2 - 2arctan(1/2) ≈ 0.6435. This
result completes the previously obtained result [SIAM J. Math. Anal., 46 (2014),
pp. 2730-2742] stating in particular that the minimal resistance of a hollow in
higher dimensions equals 0.5. We additionally consider a similar problem of minimal
resistance, where the hollow in the half-space {(x1,...,xd,y) : y ≤ 0} ⊂ ℝd+1
is defined by a radial function U satisfying the SIC, U(x) = u(|x|), with x =
(x1,...,xd), u(ξ) < 0 for 0 ≤ ξ < 1, and u(ξ) = 0 for ξ ≥ 1, and the flow
is parallel to the y-axis. The minimal resistance is greater than 0.5 (and coincides
with 0.6435 when d = 1) and converges to 0.5 as d → ∞.'
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Alexander
full_name: Plakhov, Alexander
last_name: Plakhov
citation:
ama: Akopyan A, Plakhov A. Minimal resistance of curves under the single impact
assumption. Society for Industrial and Applied Mathematics. 2015;47(4):2754-2769.
doi:10.1137/140993843
apa: Akopyan, A., & Plakhov, A. (2015). Minimal resistance of curves under the
single impact assumption. Society for Industrial and Applied Mathematics.
SIAM. https://doi.org/10.1137/140993843
chicago: Akopyan, Arseniy, and Alexander Plakhov. “Minimal Resistance of Curves
under the Single Impact Assumption.” Society for Industrial and Applied Mathematics.
SIAM, 2015. https://doi.org/10.1137/140993843.
ieee: A. Akopyan and A. Plakhov, “Minimal resistance of curves under the single
impact assumption,” Society for Industrial and Applied Mathematics, vol.
47, no. 4. SIAM, pp. 2754–2769, 2015.
ista: Akopyan A, Plakhov A. 2015. Minimal resistance of curves under the single
impact assumption. Society for Industrial and Applied Mathematics. 47(4), 2754–2769.
mla: Akopyan, Arseniy, and Alexander Plakhov. “Minimal Resistance of Curves under
the Single Impact Assumption.” Society for Industrial and Applied Mathematics,
vol. 47, no. 4, SIAM, 2015, pp. 2754–69, doi:10.1137/140993843.
short: A. Akopyan, A. Plakhov, Society for Industrial and Applied Mathematics 47
(2015) 2754–2769.
date_created: 2018-12-11T11:53:36Z
date_published: 2015-07-14T00:00:00Z
date_updated: 2021-01-12T06:52:41Z
day: '14'
department:
- _id: HeEd
doi: 10.1137/140993843
ec_funded: 1
intvolume: ' 47'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1410.3736
month: '07'
oa: 1
oa_version: Preprint
page: 2754 - 2769
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Society for Industrial and Applied Mathematics
publication_status: published
publisher: SIAM
publist_id: '5423'
quality_controlled: '1'
scopus_import: 1
status: public
title: Minimal resistance of curves under the single impact assumption
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 47
year: '2015'
...
---
_id: '1828'
abstract:
- lang: eng
text: We construct a non-linear Markov process connected with a biological model
of a bacterial genome recombination. The description of invariant measures of
this process gives us the solution of one problem in elementary probability theory.
article_processing_charge: No
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Sergey
full_name: Pirogov, Sergey
last_name: Pirogov
- first_name: Aleksandr
full_name: Rybko, Aleksandr
last_name: Rybko
citation:
ama: Akopyan A, Pirogov S, Rybko A. Invariant measures of genetic recombination
process. Journal of Statistical Physics. 2015;160(1):163-167. doi:10.1007/s10955-015-1238-5
apa: Akopyan, A., Pirogov, S., & Rybko, A. (2015). Invariant measures of genetic
recombination process. Journal of Statistical Physics. Springer. https://doi.org/10.1007/s10955-015-1238-5
chicago: Akopyan, Arseniy, Sergey Pirogov, and Aleksandr Rybko. “Invariant Measures
of Genetic Recombination Process.” Journal of Statistical Physics. Springer,
2015. https://doi.org/10.1007/s10955-015-1238-5.
ieee: A. Akopyan, S. Pirogov, and A. Rybko, “Invariant measures of genetic recombination
process,” Journal of Statistical Physics, vol. 160, no. 1. Springer, pp.
163–167, 2015.
ista: Akopyan A, Pirogov S, Rybko A. 2015. Invariant measures of genetic recombination
process. Journal of Statistical Physics. 160(1), 163–167.
mla: Akopyan, Arseniy, et al. “Invariant Measures of Genetic Recombination Process.”
Journal of Statistical Physics, vol. 160, no. 1, Springer, 2015, pp. 163–67,
doi:10.1007/s10955-015-1238-5.
short: A. Akopyan, S. Pirogov, A. Rybko, Journal of Statistical Physics 160 (2015)
163–167.
date_created: 2018-12-11T11:54:14Z
date_published: 2015-07-01T00:00:00Z
date_updated: 2021-01-12T06:53:28Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s10955-015-1238-5
ec_funded: 1
intvolume: ' 160'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: arxiv.org/abs/1406.5313
month: '07'
oa: 1
oa_version: Preprint
page: 163 - 167
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Journal of Statistical Physics
publication_status: published
publisher: Springer
publist_id: '5276'
quality_controlled: '1'
scopus_import: 1
status: public
title: Invariant measures of genetic recombination process
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 160
year: '2015'
...
---
_id: '1938'
abstract:
- lang: eng
text: 'We numerically investigate the distribution of extrema of ''chaotic'' Laplacian
eigenfunctions on two-dimensional manifolds. Our contribution is two-fold: (a)
we count extrema on grid graphs with a small number of randomly added edges and
show the behavior to coincide with the 1957 prediction of Longuet-Higgins for
the continuous case and (b) we compute the regularity of their spatial distribution
using discrepancy, which is a classical measure from the theory of Monte Carlo
integration. The first part suggests that grid graphs with randomly added edges
should behave like two-dimensional surfaces with ergodic geodesic flow; in the
second part we show that the extrema are more regularly distributed in space than
the grid Z2.'
acknowledgement: "F.P. was supported by the Graduate School of IST Austria. S.S. was
partially supported by CRC1060 of the DFG\r\nThe authors thank Olga Symonova and
Michael Kerber for sharing their implementation of the persistence algorithm. "
author:
- first_name: Florian
full_name: Pausinger, Florian
id: 2A77D7A2-F248-11E8-B48F-1D18A9856A87
last_name: Pausinger
orcid: 0000-0002-8379-3768
- first_name: Stefan
full_name: Steinerberger, Stefan
last_name: Steinerberger
citation:
ama: Pausinger F, Steinerberger S. On the distribution of local extrema in quantum
chaos. Physics Letters, Section A. 2015;379(6):535-541. doi:10.1016/j.physleta.2014.12.010
apa: Pausinger, F., & Steinerberger, S. (2015). On the distribution of local
extrema in quantum chaos. Physics Letters, Section A. Elsevier. https://doi.org/10.1016/j.physleta.2014.12.010
chicago: Pausinger, Florian, and Stefan Steinerberger. “On the Distribution of Local
Extrema in Quantum Chaos.” Physics Letters, Section A. Elsevier, 2015.
https://doi.org/10.1016/j.physleta.2014.12.010.
ieee: F. Pausinger and S. Steinerberger, “On the distribution of local extrema in
quantum chaos,” Physics Letters, Section A, vol. 379, no. 6. Elsevier,
pp. 535–541, 2015.
ista: Pausinger F, Steinerberger S. 2015. On the distribution of local extrema in
quantum chaos. Physics Letters, Section A. 379(6), 535–541.
mla: Pausinger, Florian, and Stefan Steinerberger. “On the Distribution of Local
Extrema in Quantum Chaos.” Physics Letters, Section A, vol. 379, no. 6,
Elsevier, 2015, pp. 535–41, doi:10.1016/j.physleta.2014.12.010.
short: F. Pausinger, S. Steinerberger, Physics Letters, Section A 379 (2015) 535–541.
date_created: 2018-12-11T11:54:49Z
date_published: 2015-03-06T00:00:00Z
date_updated: 2021-01-12T06:54:12Z
day: '06'
department:
- _id: HeEd
doi: 10.1016/j.physleta.2014.12.010
intvolume: ' 379'
issue: '6'
language:
- iso: eng
month: '03'
oa_version: None
page: 535 - 541
publication: Physics Letters, Section A
publication_status: published
publisher: Elsevier
publist_id: '5152'
quality_controlled: '1'
scopus_import: 1
status: public
title: On the distribution of local extrema in quantum chaos
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 379
year: '2015'
...
---
_id: '2035'
abstract:
- lang: eng
text: "Considering a continuous self-map and the induced endomorphism on homology,
we study the eigenvalues and eigenspaces of the latter. Taking a filtration of
representations, we define the persistence of the eigenspaces, effectively introducing
a hierarchical organization of the map. The algorithm that computes this information
for a finite sample is proved to be stable, and to give the correct answer for
a sufficiently dense sample. Results computed with an implementation of the algorithm
provide evidence of its practical utility.\r\n"
acknowledgement: This research is partially supported by the Toposys project FP7-ICT-318493-STREP,
by ESF under the ACAT Research Network Programme, by the Russian Government under
mega project 11.G34.31.0053, and by the Polish National Science Center under Grant
No. N201 419639.
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Grzegorz
full_name: Jablonski, Grzegorz
id: 4483EF78-F248-11E8-B48F-1D18A9856A87
last_name: Jablonski
orcid: 0000-0002-3536-9866
- first_name: Marian
full_name: Mrozek, Marian
last_name: Mrozek
citation:
ama: Edelsbrunner H, Jablonski G, Mrozek M. The persistent homology of a self-map.
Foundations of Computational Mathematics. 2015;15(5):1213-1244. doi:10.1007/s10208-014-9223-y
apa: Edelsbrunner, H., Jablonski, G., & Mrozek, M. (2015). The persistent homology
of a self-map. Foundations of Computational Mathematics. Springer. https://doi.org/10.1007/s10208-014-9223-y
chicago: Edelsbrunner, Herbert, Grzegorz Jablonski, and Marian Mrozek. “The Persistent
Homology of a Self-Map.” Foundations of Computational Mathematics. Springer,
2015. https://doi.org/10.1007/s10208-014-9223-y.
ieee: H. Edelsbrunner, G. Jablonski, and M. Mrozek, “The persistent homology of
a self-map,” Foundations of Computational Mathematics, vol. 15, no. 5.
Springer, pp. 1213–1244, 2015.
ista: Edelsbrunner H, Jablonski G, Mrozek M. 2015. The persistent homology of a
self-map. Foundations of Computational Mathematics. 15(5), 1213–1244.
mla: Edelsbrunner, Herbert, et al. “The Persistent Homology of a Self-Map.” Foundations
of Computational Mathematics, vol. 15, no. 5, Springer, 2015, pp. 1213–44,
doi:10.1007/s10208-014-9223-y.
short: H. Edelsbrunner, G. Jablonski, M. Mrozek, Foundations of Computational Mathematics
15 (2015) 1213–1244.
date_created: 2018-12-11T11:55:20Z
date_published: 2015-10-01T00:00:00Z
date_updated: 2021-01-12T06:54:53Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/s10208-014-9223-y
ec_funded: 1
file:
- access_level: open_access
checksum: 3566f3a8b0c1bc550e62914a88c584ff
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:10Z
date_updated: 2020-07-14T12:45:26Z
file_id: '4670'
file_name: IST-2016-486-v1+1_s10208-014-9223-y.pdf
file_size: 1317546
relation: main_file
file_date_updated: 2020-07-14T12:45:26Z
has_accepted_license: '1'
intvolume: ' 15'
issue: '5'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '10'
oa: 1
oa_version: Published Version
page: 1213 - 1244
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Foundations of Computational Mathematics
publication_status: published
publisher: Springer
publist_id: '5022'
pubrep_id: '486'
quality_controlled: '1'
scopus_import: 1
status: public
title: The persistent homology of a self-map
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2015'
...