TY - JOUR AB - The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel et al. [DISC’17]. AU - Czumaj, Artur AU - Davies, Peter AU - Parter, Merav ID - 9541 IS - 2 JF - ACM Transactions on Algorithms SN - 1549-6325 TI - Graph sparsification for derandomizing massively parallel computation with low space VL - 17 ER - TY - JOUR AB - We investigate the effect of coupling between translational and internal degrees of freedom of composite quantum particles on their localization in a random potential. We show that entanglement between the two degrees of freedom weakens localization due to the upper bound imposed on the inverse participation ratio by purity of a quantum state. We perform numerical calculations for a two-particle system bound by a harmonic force in a 1D disordered lattice and a rigid rotor in a 2D disordered lattice. We illustrate that the coupling has a dramatic effect on localization properties, even with a small number of internal states participating in quantum dynamics. AU - Suzuki, Fumika AU - Lemeshko, Mikhail AU - Zurek, Wojciech H. AU - Krems, Roman V. ID - 10134 IS - 16 JF - Physical Review Letters KW - General Physics and Astronomy SN - 0031-9007 TI - Anderson localization of composite particles VL - 127 ER - TY - CONF AB - We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively. AU - Brandt, Sebastian AU - Keller, Barbara AU - Rybicki, Joel AU - Suomela, Jukka AU - Uitto, Jara ID - 9678 SN - 9781450380706 T2 - Annual ACM Symposium on Parallelism in Algorithms and Architectures TI - Efficient load-balancing through distributed token dropping ER - TY - JOUR AB - 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. AU - Alistarh, Dan-Adrian AU - Nadiradze, Giorgi AU - Sabour, Amirmojtaba ID - 8286 JF - Algorithmica SN - 0178-4617 TI - Dynamic averaging load balancing on cycles ER - TY - THES AB - This thesis is the result of the research carried out by the author during his PhD at IST Austria between 2017 and 2021. It mainly focuses on the Fröhlich polaron model, specifically to its regime of strong coupling. This model, which is rigorously introduced and discussed in the introduction, has been of great interest in condensed matter physics and field theory for more than eighty years. It is used to describe an electron interacting with the atoms of a solid material (the strength of this interaction is modeled by the presence of a coupling constant α in the Hamiltonian of the system). The particular regime examined here, which is mathematically described by considering the limit α →∞, displays many interesting features related to the emergence of classical behavior, which allows for a simplified effective description of the system under analysis. The properties, the range of validity and a quantitative analysis of the precision of such classical approximations are the main object of the present work. We specify our investigation to the study of the ground state energy of the system, its dynamics and its effective mass. For each of these problems, we provide in the introduction an overview of the previously known results and a detailed account of the original contributions by the author. AU - Feliciangeli, Dario ID - 9733 SN - 2663-337X TI - The polaron at strong coupling ER -