@article{11606, abstract = {Context. Our knowledge of the dynamics of stars has undergone a revolution through the simultaneous large amount of high-quality photometric observations collected by space-based asteroseismology and ground-based high-precision spectropolarimetry. They allowed us to probe the internal rotation of stars and their surface magnetism in the whole Hertzsprung-Russell diagram. However, new methods should still be developed to probe the deep magnetic fields in these stars. Aims. Our goal is to provide seismic diagnoses that allow us to probe the internal magnetism of stars. Methods. We focused on asymptotic low-frequency gravity modes and high-frequency acoustic modes. Using a first-order perturbative theory, we derived magnetic splittings of their frequencies as explicit functions of stellar parameters. Results. As in the case of rotation, we show that asymptotic gravity and acoustic modes can allow us to probe the different components of the magnetic field in the cavities in which they propagate. This again demonstrates the high potential of using mixed-modes when this is possible.}, author = {Mathis, S. and Bugnet, Lisa Annabelle and Prat, V. and Augustson, K. and Mathur, S. and Garcia, R. A.}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, asteroseismology / waves / stars, magnetic field / stars, oscillations / methods, analytical}, publisher = {EDP Sciences}, title = {{Probing the internal magnetism of stars using asymptotic magneto-asteroseismology}}, doi = {10.1051/0004-6361/202039180}, volume = {647}, year = {2021}, } @article{11608, abstract = {In order to understand stellar evolution, it is crucial to efficiently determine stellar surface rotation periods. Indeed, while they are of great importance in stellar models, angular momentum transport processes inside stars are still poorly understood today. Surface rotation, which is linked to the age of the star, is one of the constraints needed to improve the way those processes are modelled. Statistics of the surface rotation periods for a large sample of stars of different spectral types are thus necessary. An efficient tool to automatically determine reliable rotation periods is needed when dealing with large samples of stellar photometric datasets. The objective of this work is to develop such a tool. For this purpose, machine learning classifiers constitute relevant bases to build our new methodology. Random forest learning abilities are exploited to automate the extraction of rotation periods in Kepler light curves. Rotation periods and complementary parameters are obtained via three different methods: a wavelet analysis, the autocorrelation function of the light curve, and the composite spectrum. We trained three different classifiers: one to detect if rotational modulations are present in the light curve, one to flag close binary or classical pulsators candidates that can bias our rotation period determination, and finally one classifier to provide the final rotation period. We tested our machine learning pipeline on 23 431 stars of the Kepler K and M dwarf reference rotation catalogue for which 60% of the stars have been visually inspected. For the sample of 21 707 stars where all the input parameters are provided to the algorithm, 94.2% of them are correctly classified (as rotating or not). Among the stars that have a rotation period in the reference catalogue, the machine learning provides a period that agrees within 10% of the reference value for 95.3% of the stars. Moreover, the yield of correct rotation periods is raised to 99.5% after visually inspecting 25.2% of the stars. Over the two main analysis steps, rotation classification and period selection, the pipeline yields a global agreement with the reference values of 92.1% and 96.9% before and after visual inspection. Random forest classifiers are efficient tools to determine reliable rotation periods in large samples of stars. The methodology presented here could be easily adapted to extract surface rotation periods for stars with different spectral types or observed by other instruments such as K2, TESS or by PLATO in the near future.}, author = {Breton, S. N. and Santos, A. R. G. and Bugnet, Lisa Annabelle and Mathur, S. and García, R. A. and Pallé, P. L.}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, methods: data analysis / stars: solar-type / stars: activity / stars: rotation / starspots}, publisher = {EDP Sciences}, title = {{ROOSTER: A machine-learning analysis tool for Kepler stellar rotation periods}}, doi = {10.1051/0004-6361/202039947}, volume = {647}, year = {2021}, } @article{11609, abstract = {Context. Stellar interiors are the seat of efficient transport of angular momentum all along their evolution. In this context, understanding the dependence of the turbulent transport triggered by the instabilities of the vertical and horizontal shears of the differential rotation in stellar radiation zones as a function of their rotation, stratification, and thermal diffusivity is mandatory. Indeed, it constitutes one of the cornerstones of the rotational transport and mixing theory, which is implemented in stellar evolution codes to predict the rotational and chemical evolutions of stars. Aims. We investigate horizontal shear instabilities in rotating stellar radiation zones by considering the full Coriolis acceleration with both the dimensionless horizontal Coriolis component f̃ and the vertical component f. Methods. We performed a linear stability analysis using linearized equations derived from the Navier-Stokes and heat transport equations in the rotating nontraditional f-plane. We considered a horizontal shear flow with a hyperbolic tangent profile as the base flow. The linear stability was analyzed numerically in wide ranges of parameters, and we performed an asymptotic analysis for large vertical wavenumbers using the Wentzel-Kramers-Brillouin-Jeffreys (WKBJ) approximation for nondiffusive and highly-diffusive fluids. Results. As in the traditional f-plane approximation, we identify two types of instabilities: the inflectional and inertial instabilities. The inflectional instability is destabilized as f̃ increases and its maximum growth rate increases significantly, while the thermal diffusivity stabilizes the inflectional instability similarly to the traditional case. The inertial instability is also strongly affected; for instance, the inertially unstable regime is also extended in the nondiffusive limit as 0 < f < 1 + f̃ 2/N2, where N is the dimensionless Brunt-Väisälä frequency. More strikingly, in the high thermal diffusivity limit, it is always inertially unstable at any colatitude θ except at the poles (i.e., 0° < θ <  180°). We also derived the critical Reynolds numbers for the inertial instability using the asymptotic dispersion relations obtained from the WKBJ analysis. Using the asymptotic and numerical results, we propose a prescription for the effective turbulent viscosities induced by the inertial and inflectional instabilities that can be possibly used in stellar evolution models. The characteristic time of this turbulence is short enough so that it is efficient to redistribute angular momentum and to mix chemicals in stellar radiation zones.}, author = {Park, J. and Prat, V. and Mathis, S. and Bugnet, Lisa Annabelle}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, hydrodynamics / turbulence / stars, rotation / stars, evolution}, publisher = {EDP Sciences}, title = {{Horizontal shear instabilities in rotating stellar radiation zones: II. Effects of the full Coriolis acceleration}}, doi = {10.1051/0004-6361/202038654}, volume = {646}, year = {2021}, } @inproceedings{11649, abstract = {While operating communication networks adaptively may improve utilization and performance, frequent adjustments also introduce an algorithmic challenge: the re-optimization of traffic engineering solutions is time-consuming and may limit the granularity at which a network can be adjusted. This paper is motivated by question whether the reactivity of a network can be improved by re-optimizing solutions dynamically rather than from scratch, especially if inputs such as link weights do not change significantly. This paper explores to what extent dynamic algorithms can be used to speed up fundamental tasks in network operations. We specifically investigate optimizations related to traffic engineering (namely shortest paths and maximum flow computations), but also consider spanning tree and matching applications. While prior work on dynamic graph algorithms focusses on link insertions and deletions, we are interested in the practical problem of link weight changes. We revisit existing upper bounds in the weight-dynamic model, and present several novel lower bounds on the amortized runtime for recomputing solutions. In general, we find that the potential performance gains depend on the application, and there are also strict limitations on what can be achieved, even if link weights change only slightly.}, author = {Henzinger, Monika H and Paz, Ami and Schmid, Stefan}, booktitle = {IFIP Networking Conference}, issn = {1861-2288}, location = { Espoo and Helsinki, Finland}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{On the complexity of weight-dynamic network algorithms}}, doi = {10.23919/ifipnetworking52078.2021.9472803}, year = {2021}, } @article{11663, abstract = {Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability. In this article, we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem. (1) For dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3 (n) high-probability worst-case time bound for maintaining a (2k-1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k-1 and Õ(n1+1/k) edges.) (2) For dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log 5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2+ϵ)-approximate, and hence not maximal. Our results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: An algorithm is said to have worst-case expected update time ɑ if for every update σ, the expected time to process σ is at most ɑ. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: A worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires ϴ (f(n)) time to process, for arbitrarily high f(n). In this article, we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: The query time remains the same, while the update time increases by a factor of O(log 2(n)). Thus, we achieve our results in two steps: (1) First, we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times. (2) Then, we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms.}, author = {Bernstein, Aaron and Forster, Sebastian and Henzinger, Monika H}, issn = {1549-6333}, journal = {ACM Transactions on Algorithms}, number = {4}, publisher = {Association for Computing Machinery}, title = {{A deamortization approach for dynamic spanner and dynamic maximal matching}}, doi = {10.1145/3469833}, volume = {17}, year = {2021}, } @article{11756, abstract = {We give two fully dynamic algorithms that maintain a (1 + ε)-approximation of the weight M of a minimum spanning forest (MSF) of an n-node graph G with edges weights in [1, W ], for any ε > 0. (1) Our deterministic algorithm takes O (W 2 log W /ε3) worst-case update time, which is O (1) if both W and ε are constants. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case O (log W /ε4) update time if W = O ((m∗)1/6/log2/3 n), where m∗ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement our algorithmic results with two cell-probe lower bounds for dynamically maintaining an approximation of the weight of an MSF of a graph.}, author = {Henzinger, Monika H and Peng, Pan}, issn = {0890-5401}, journal = {Information and Computation}, number = {12}, publisher = {Elsevier}, title = {{Constant-time dynamic weight approximation for minimum spanning forest}}, doi = {10.1016/j.ic.2021.104805}, volume = {281}, year = {2021}, } @inproceedings{11771, abstract = {Classic dynamic data structure problems maintain a data structure subject to a sequence S of updates and they answer queries using the latest version of the data structure, i.e., the data structure after processing the whole sequence. To handle operations that change the sequence S of updates, Demaine et al. [7] introduced retroactive data structures (RDS). A retroactive operation modifies the update sequence S in a given position t, called time, and either creates or cancels an update in S at time t. A fully retroactive data structure supports queries at any time t: a query at time t is answered using only the updates of S up to time t. While efficient RDS have been proposed for classic data structures, e.g., stack, priority queue and binary search tree, the retroactive version of graph problems are rarely studied. In this paper we study retroactive graph problems including connectivity, minimum spanning forest (MSF), maximum degree, etc. We show that under the OMv conjecture (proposed by Henzinger et al. [15]), there does not exist fully RDS maintaining connectivity or MSF, or incremental fully RDS maintaining the maximum degree with 𝑂(𝑛1−𝜖) time per operation, for any constant 𝜖>0. Furthermore, We provide RDS with almost tight time per operation. We give fully RDS for maintaining the maximum degree, connectivity and MSF in 𝑂̃ (𝑛) time per operation. We also give an algorithm for the incremental (insertion-only) fully retroactive connectivity with 𝑂̃ (1) time per operation, showing that the lower bound cannot be extended to this setting. We also study a restricted version of RDS, where the only change to S is the swap of neighboring updates and show that for this problem we can beat the above hardness result. This also implies the first non-trivial dynamic Reeb graph computation algorithm.}, author = {Henzinger, Monika H and Wu, Xiaowei}, booktitle = {17th International Symposium on Algorithms and Data Structures}, isbn = {9783030835071}, issn = {1611-3349}, location = {Virtual}, pages = {471–484}, publisher = {Springer Nature}, title = {{Upper and lower bounds for fully retroactive graph problems}}, doi = {10.1007/978-3-030-83508-8_34}, volume = {12808}, year = {2021}, } @article{7883, abstract = {All vertebrates have a spinal cord with dimensions and shape specific to their species. Yet how species‐specific organ size and shape are achieved is a fundamental unresolved question in biology. The formation and sculpting of organs begins during embryonic development. As it develops, the spinal cord extends in anterior–posterior direction in synchrony with the overall growth of the body. The dorsoventral (DV) and apicobasal lengths of the spinal cord neuroepithelium also change, while at the same time a characteristic pattern of neural progenitor subtypes along the DV axis is established and elaborated. At the basis of these changes in tissue size and shape are biophysical determinants, such as the change in cell number, cell size and shape, and anisotropic tissue growth. These processes are controlled by global tissue‐scale regulators, such as morphogen signaling gradients as well as mechanical forces. Current challenges in the field are to uncover how these tissue‐scale regulatory mechanisms are translated to the cellular and molecular level, and how regulation of distinct cellular processes gives rise to an overall defined size. Addressing these questions will help not only to achieve a better understanding of how size is controlled, but also of how tissue size is coordinated with the specification of pattern.}, author = {Kuzmicz-Kowalska, Katarzyna and Kicheva, Anna}, issn = {17597692}, journal = {Wiley Interdisciplinary Reviews: Developmental Biology}, publisher = {Wiley}, title = {{Regulation of size and scale in vertebrate spinal cord development}}, doi = {10.1002/wdev.383}, year = {2021}, } @article{7900, abstract = {Hartree–Fock theory has been justified as a mean-field approximation for fermionic systems. However, it suffers from some defects in predicting physical properties, making necessary a theory of quantum correlations. Recently, bosonization of many-body correlations has been rigorously justified as an upper bound on the correlation energy at high density with weak interactions. We review the bosonic approximation, deriving an effective Hamiltonian. We then show that for systems with Coulomb interaction this effective theory predicts collective excitations (plasmons) in accordance with the random phase approximation of Bohm and Pines, and with experimental observation.}, author = {Benedikter, Niels P}, issn = {1793-6659}, journal = {Reviews in Mathematical Physics}, number = {1}, publisher = {World Scientific}, title = {{Bosonic collective excitations in Fermi gases}}, doi = {10.1142/s0129055x20600090}, volume = {33}, year = {2021}, } @article{7901, abstract = {We derive rigorously the leading order of the correlation energy of a Fermi gas in a scaling regime of high density and weak interaction. The result verifies the prediction of the random-phase approximation. Our proof refines the method of collective bosonization in three dimensions. We approximately diagonalize an effective Hamiltonian describing approximately bosonic collective excitations around the Hartree–Fock state, while showing that gapless and non-collective excitations have only a negligible effect on the ground state energy.}, author = {Benedikter, Niels P and Nam, Phan Thành and Porta, Marcello and Schlein, Benjamin and Seiringer, Robert}, issn = {1432-1297}, journal = {Inventiones Mathematicae}, pages = {885--979}, publisher = {Springer}, title = {{Correlation energy of a weakly interacting Fermi gas}}, doi = {10.1007/s00222-021-01041-5}, volume = {225}, year = {2021}, } @article{7905, abstract = {We investigate a sheaf-theoretic interpretation of stratification learning from geometric and topological perspectives. Our main result is the construction of stratification learning algorithms framed in terms of a sheaf on a partially ordered set with the Alexandroff topology. We prove that the resulting decomposition is the unique minimal stratification for which the strata are homogeneous and the given sheaf is constructible. In particular, when we choose to work with the local homology sheaf, our algorithm gives an alternative to the local homology transfer algorithm given in Bendich et al. (Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1355–1370, ACM, New York, 2012), and the cohomology stratification algorithm given in Nanda (Found. Comput. Math. 20(2), 195–222, 2020). Additionally, we give examples of stratifications based on the geometric techniques of Breiding et al. (Rev. Mat. Complut. 31(3), 545–593, 2018), illustrating how the sheaf-theoretic approach can be used to study stratifications from both topological and geometric perspectives. This approach also points toward future applications of sheaf theory in the study of topological data analysis by illustrating the utility of the language of sheaf theory in generalizing existing algorithms.}, author = {Brown, Adam and Wang, Bei}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {1166--1198}, publisher = {Springer Nature}, title = {{Sheaf-theoretic stratification learning from geometric and topological perspectives}}, doi = {10.1007/s00454-020-00206-y}, volume = {65}, year = {2021}, } @article{7925, abstract = {In this paper, we introduce a relaxed CQ method with alternated inertial step for solving split feasibility problems. We give convergence of the sequence generated by our method under some suitable assumptions. Some numerical implementations from sparse signal and image deblurring are reported to show the efficiency of our method.}, author = {Shehu, Yekini and Gibali, Aviv}, issn = {1862-4480}, journal = {Optimization Letters}, pages = {2109--2126}, publisher = {Springer Nature}, title = {{New inertial relaxed method for solving split feasibilities}}, doi = {10.1007/s11590-020-01603-1}, volume = {15}, year = {2021}, } @article{7939, abstract = {We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include: A (2+ϵ)-approximation for all-pairs shortest paths in O(log2n/ϵ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model. A (1+ϵ)-approximation for multi-source shortest paths from O(n−−√) sources in O(log2n/ϵ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size. Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in O~(n1/6) rounds. }, author = {Censor-Hillel, Keren and Dory, Michal and Korhonen, Janne and Leitersdorf, Dean}, issn = {1432-0452}, journal = {Distributed Computing}, pages = {463--487}, publisher = {Springer Nature}, title = {{Fast approximate shortest paths in the congested clique}}, doi = {10.1007/s00446-020-00380-5}, volume = {34}, year = {2021}, } @article{8196, abstract = {This paper aims to obtain a strong convergence result for a Douglas–Rachford splitting method with inertial extrapolation step for finding a zero of the sum of two set-valued maximal monotone operators without any further assumption of uniform monotonicity on any of the involved maximal monotone operators. Furthermore, our proposed method is easy to implement and the inertial factor in our proposed method is a natural choice. Our method of proof is of independent interest. Finally, some numerical implementations are given to confirm the theoretical analysis.}, author = {Shehu, Yekini and Dong, Qiao-Li and Liu, Lu-Lu and Yao, Jen-Chih}, issn = {1573-2924}, journal = {Optimization and Engineering}, pages = {2627--2653}, publisher = {Springer Nature}, title = {{New strong convergence method for the sum of two maximal monotone operators}}, doi = {10.1007/s11081-020-09544-5}, volume = {22}, year = {2021}, } @article{8198, abstract = {We investigate how the critical driving amplitude at the Floquet many-body localized (MBL) to ergodic phase transition differs between smooth and nonsmooth drives. To this end, we numerically study a disordered spin-1/2 chain which is periodically driven by a sine or square-wave drive over a wide range of driving frequencies. In both cases the critical driving amplitude increases monotonically with the frequency, and at large frequencies it is identical for the two drives. However, at low and intermediate frequencies the critical amplitude of the square-wave drive depends strongly on the frequency, while that of the sinusoidal drive is almost constant over a wide frequency range. By analyzing the density of drive-induced resonances we conclude that this difference is due to resonances induced by the higher harmonics which are present (absent) in the Fourier spectrum of the square-wave (sine) drive. Furthermore, we suggest a numerically efficient method for estimating the frequency dependence of the critical driving amplitudes for different drives which is based on calculating the density of drive-induced resonances. We conclude that delocalization occurs once the density of drive-induced resonances reaches a critical value determined only by the static system.}, author = {Diringer, Asaf A. and Gulden, Tobias}, issn = {24699969}, journal = {Physical Review B}, number = {21}, publisher = {American Physical Society}, title = {{Impact of drive harmonics on the stability of Floquet many-body localization}}, doi = {10.1103/PhysRevB.103.214204}, volume = {103}, year = {2021}, } @article{8248, abstract = {We consider the following setting: suppose that we are given a manifold M in Rd with positive reach. Moreover assume that we have an embedded simplical complex A without boundary, whose vertex set lies on the manifold, is sufficiently dense and such that all simplices in A have sufficient quality. We prove that if, locally, interiors of the projection of the simplices onto the tangent space do not intersect, then A is a triangulation of the manifold, that is, they are homeomorphic.}, author = {Boissonnat, Jean-Daniel and Dyer, Ramsay and Ghosh, Arijit and Lieutier, Andre and Wintraecken, Mathijs}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {666--686}, publisher = {Springer Nature}, title = {{Local conditions for triangulating submanifolds of Euclidean space}}, doi = {10.1007/s00454-020-00233-9}, volume = {66}, year = {2021}, } @article{8253, abstract = {Brains process information in spiking neural networks. Their intricate connections shape the diverse functions these networks perform. In comparison, the functional capabilities of models of spiking networks are still rudimentary. This shortcoming is mainly due to the lack of insight and practical algorithms to construct the necessary connectivity. Any such algorithm typically attempts to build networks by iteratively reducing the error compared to a desired output. But assigning credit to hidden units in multi-layered spiking networks has remained challenging due to the non-differentiable nonlinearity of spikes. To avoid this issue, one can employ surrogate gradients to discover the required connectivity in spiking network models. However, the choice of a surrogate is not unique, raising the question of how its implementation influences the effectiveness of the method. Here, we use numerical simulations to systematically study how essential design parameters of surrogate gradients impact learning performance on a range of classification problems. We show that surrogate gradient learning is robust to different shapes of underlying surrogate derivatives, but the choice of the derivative’s scale can substantially affect learning performance. When we combine surrogate gradients with a suitable activity regularization technique, robust information processing can be achieved in spiking networks even at the sparse activity limit. Our study provides a systematic account of the remarkable robustness of surrogate gradient learning and serves as a practical guide to model functional spiking neural networks.}, author = {Zenke, Friedemann and Vogels, Tim P}, issn = {1530-888X}, journal = {Neural Computation}, number = {4}, pages = {899--925}, publisher = {MIT Press}, title = {{The remarkable robustness of surrogate gradient learning for instilling complex function in spiking neural networks}}, doi = {10.1162/neco_a_01367}, volume = {33}, year = {2021}, } @article{8286, abstract = {We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step t≥ 0, one unit of load is created, and placed at a randomly chosen graph node. In the same step, the chosen node picks a random neighbor, and the two nodes balance their loads by averaging them. We are interested in the expected gap between the minimum and maximum loads at nodes as the process progresses, and its dependence on n and on the graph structure. Variants of the above graphical balanced allocation process have been studied previously by Peres, Talwar, and Wieder [Peres et al., 2015], and by Sauerwald and Sun [Sauerwald and Sun, 2015]. These authors left as open the question of characterizing the gap in the case of cycle graphs in the dynamic case, where weights are created during the algorithm’s execution. For this case, the only known upper bound is of 𝒪(n log n), following from a majorization argument due to [Peres et al., 2015], which analyzes a related graphical allocation process. In this paper, we provide an upper bound of 𝒪 (√n log n) on the expected gap of the above process for cycles of length n. We introduce a new potential analysis technique, which enables us to bound the difference in load between k-hop neighbors on the cycle, for any k ≤ n/2. We complement this with a "gap covering" argument, which bounds the maximum value of the gap by bounding its value across all possible subsets of a certain structure, and recursively bounding the gaps within each subset. We provide analytical and experimental evidence that our upper bound on the gap is tight up to a logarithmic factor. }, author = {Alistarh, Dan-Adrian and Nadiradze, Giorgi and Sabour, Amirmojtaba}, issn = {1432-0541}, journal = {Algorithmica}, location = {Virtual, Online; Germany}, publisher = {Springer Nature}, title = {{Dynamic averaging load balancing on cycles}}, doi = {10.1007/s00453-021-00905-9}, year = {2021}, } @article{8317, abstract = {When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability.}, author = {Aichholzer, Oswin and Akitaya, Hugo A. and Cheung, Kenneth C. and Demaine, Erik D. and Demaine, Martin L. and Fekete, Sándor P. and Kleist, Linda and Kostitsyna, Irina and Löffler, Maarten and Masárová, Zuzana and Mundilova, Klara and Schmidt, Christiane}, issn = {09257721}, journal = {Computational Geometry: Theory and Applications}, publisher = {Elsevier}, title = {{Folding polyominoes with holes into a cube}}, doi = {10.1016/j.comgeo.2020.101700}, volume = {93}, year = {2021}, } @article{8338, abstract = {Canonical parametrisations of classical confocal coordinate systems are introduced and exploited to construct non-planar analogues of incircular (IC) nets on individual quadrics and systems of confocal quadrics. Intimate connections with classical deformations of quadrics that are isometric along asymptotic lines and circular cross-sections of quadrics are revealed. The existence of octahedral webs of surfaces of Blaschke type generated by asymptotic and characteristic lines that are diagonally related to lines of curvature is proved theoretically and established constructively. Appropriate samplings (grids) of these webs lead to three-dimensional extensions of non-planar IC nets. Three-dimensional octahedral grids composed of planes and spatially extending (checkerboard) IC-nets are shown to arise in connection with systems of confocal quadrics in Minkowski space. In this context, the Laguerre geometric notion of conical octahedral grids of planes is introduced. The latter generalise the octahedral grids derived from systems of confocal quadrics in Minkowski space. An explicit construction of conical octahedral grids is presented. The results are accompanied by various illustrations which are based on the explicit formulae provided by the theory.}, author = {Akopyan, Arseniy and Bobenko, Alexander I. and Schief, Wolfgang K. and Techter, Jan}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {938--976}, publisher = {Springer Nature}, title = {{On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs}}, doi = {10.1007/s00454-020-00240-w}, volume = {66}, year = {2021}, }