@article{10628,
  abstract     = {The surface states of 3D topological insulators in general have negligible quantum oscillations (QOs) when the chemical potential is tuned to the Dirac points. In contrast, we find that topological Kondo insulators (TKIs) can support surface states with an arbitrarily large Fermi surface (FS) when the chemical potential is pinned to the Dirac point. We illustrate that these FSs give rise to finite-frequency QOs, which can become comparable to the extremal area of the unhybridized bulk bands. We show that this occurs when the crystal symmetry is lowered from cubic to tetragonal in a minimal two-orbital model. We label such surface modes as 'shadow surface states'. Moreover, we show that the sufficient next-nearest neighbor out-of-plane hybridization leading to shadow surface states can be self-consistently stabilized for tetragonal TKIs. Consequently, shadow surface states provide an important example of high-frequency QOs beyond the context of cubic TKIs.},
  author       = {Ghazaryan, Areg and Nica, Emilian M. and Erten, Onur and Ghaemi, Pouyan},
  issn         = {1367-2630},
  journal      = {New Journal of Physics},
  number       = {12},
  publisher    = {IOP Publishing},
  title        = {{Shadow surface states in topological Kondo insulators}},
  doi          = {10.1088/1367-2630/ac4124},
  volume       = {23},
  year         = {2021},
}

@inproceedings{10629,
  abstract     = {Product graphs arise naturally in formal verification and program analysis. For example, the analysis of two concurrent threads requires the product of two component control-flow graphs, and for language inclusion of deterministic automata the product of two automata is constructed. In many cases, the component graphs have constant treewidth, e.g., when the input contains control-flow graphs of programs. We consider the algorithmic analysis of products of two constant-treewidth graphs with respect to three classic specification languages, namely, (a) algebraic properties, (b) mean-payoff properties, and (c) initial credit for energy properties.
Our main contributions are as follows. Consider a graph G that is the product of two constant-treewidth graphs of size n each. First, given an idempotent semiring, we present an algorithm that computes the semiring transitive closure of G in time Õ(n⁴). Since the output has size Θ(n⁴), our algorithm is optimal (up to polylog factors). Second, given a mean-payoff objective, we present an O(n³)-time algorithm for deciding whether the value of a starting state is non-negative, improving the previously known O(n⁴) bound. Third, given an initial credit for energy objective, we present an O(n⁵)-time algorithm for computing the minimum initial credit for all nodes of G, improving the previously known O(n⁸) bound. At the heart of our approach lies an algorithm for the efficient construction of strongly-balanced tree decompositions of constant-treewidth graphs. Given a constant-treewidth graph G' of n nodes and a positive integer λ, our algorithm constructs a binary tree decomposition of G' of width O(λ) with the property that the size of each subtree decreases geometrically with rate (1/2 + 2^{-λ}).},
  author       = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas},
  booktitle    = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  isbn         = {978-3-9597-7215-0},
  issn         = {1868-8969},
  location     = {Virtual},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Quantitative verification on product graphs of small treewidth}},
  doi          = {10.4230/LIPIcs.FSTTCS.2021.42},
  volume       = {213},
  year         = {2021},
}

@inproceedings{10630,
  abstract     = {In the Intersection Non-emptiness problem, we are given a list of finite automata A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine whether some string w ∈ Σ^* lies in the intersection of the languages accepted by the automata in the list. We analyze the complexity of the Intersection Non-emptiness problem under the promise that all input automata accept a language in some level of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy. Automata accepting languages from the lowest levels of these hierarchies arise naturally in the context of model checking. We identify a dichotomy in the dot-depth hierarchy by showing that the problem is already NP-complete when all input automata accept languages of the levels B_0 or B_{1/2} and already PSPACE-hard when all automata accept a language from the level B_1. Conversely, we identify a tetrachotomy in the Straubing-Thérien hierarchy. More precisely, we show that the problem is in AC^0 when restricted to level L_0; complete for L or NL, depending on the input representation, when restricted to languages in the level L_{1/2}; NP-complete when the input is given as DFAs accepting a language in L_1 or L_{3/2}; and finally, PSPACE-complete when the input automata accept languages in level L_2 or higher. Moreover, we show that the proof technique used to show containment in NP for DFAs accepting languages in L_1 or L_{3/2} does not generalize to the context of NFAs. To prove this, we identify a family of languages that provide an exponential separation between the state complexity of general NFAs and that of partially ordered NFAs. To the best of our knowledge, this is the first superpolynomial separation between these two models of computation.},
  author       = {Arrighi, Emmanuel and Fernau, Henning and Hoffmann, Stefan and Holzer, Markus and Jecker, Ismael R and De Oliveira Oliveira, Mateus and Wolf, Petra},
  booktitle    = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  isbn         = {978-3-9597-7215-0},
  issn         = {1868-8969},
  location     = {Virtual},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{On the complexity of intersection non-emptiness for star-free language classes}},
  doi          = {10.4230/LIPIcs.FSTTCS.2021.34},
  volume       = {213},
  year         = {2021},
}

@article{10631,
  abstract     = {We combine experimental and theoretical approaches to explore excited rotational states of molecules embedded in helium nanodroplets using CS2 and I2 as examples. Laser-induced nonadiabatic molecular alignment is employed to measure spectral lines for rotational states extending beyond those initially populated at the 0.37 K droplet temperature. We construct a simple quantum-mechanical model, based on a linear rotor coupled to a single-mode bosonic bath, to determine the rotational energy structure in its entirety. The calculated and measured spectral lines are in good agreement. We show that the effect of the surrounding superfluid on molecular rotation can be rationalized by a single quantity, the angular momentum, transferred from the molecule to the droplet.},
  author       = {Cherepanov, Igor and Bighin, Giacomo and Schouder, Constant A. and Chatterley, Adam S. and Albrechtsen, Simon H. and Muñoz, Alberto Viñas and Christiansen, Lars and Stapelfeldt, Henrik and Lemeshko, Mikhail},
  issn         = {2469-9934},
  journal      = {Physical Review A},
  number       = {6},
  publisher    = {American Physical Society},
  title        = {{Excited rotational states of molecules in a superfluid}},
  doi          = {10.1103/PhysRevA.104.L061303},
  volume       = {104},
  year         = {2021},
}

@article{10635,
  abstract     = {The brain efficiently performs nonlinear computations through its intricate networks of spiking neurons, but how this is done remains elusive. While nonlinear computations can be implemented successfully in spiking neural networks, this requires supervised training and the resulting connectivity can be hard to interpret. In contrast, the required connectivity for any computation in the form of a linear dynamical system can be directly derived and understood with the spike coding network (SCN) framework. These networks also have biologically realistic activity patterns and are highly robust to cell death. Here we extend the SCN framework to directly implement any polynomial dynamical system, without the need for training. This results in networks requiring a mix of synapse types (fast, slow, and multiplicative), which we term multiplicative spike coding networks (mSCNs). Using mSCNs, we demonstrate how to directly derive the required connectivity for several nonlinear dynamical systems. We also show how to carry out higher-order polynomials with coupled networks that use only pair-wise multiplicative synapses, and provide expected numbers of connections for each synapse type. Overall, our work demonstrates a novel method for implementing nonlinear computations in spiking neural networks, while keeping the attractive features of standard SCNs (robustness, realistic activity patterns, and interpretable connectivity). Finally, we discuss the biological plausibility of our approach, and how the high accuracy and robustness of the approach may be of interest for neuromorphic computing.},
  author       = {Nardin, Michele and Phillips, James W. and Podlaski, William F. and Keemink, Sander W.},
  issn         = {2804-3871},
  journal      = {Peer Community Journal},
  publisher    = {Peer Community In},
  title        = {{Nonlinear computations in spiking neural networks through multiplicative synapses}},
  doi          = {10.24072/pcjournal.69},
  volume       = {1},
  year         = {2021},
}

@misc{10644,
  abstract     = {The purpose of this application note is to demonstrate a working example of a superconducting qubit measurement in a Bluefors cryostat using the Keysight quantum control hardware. Our motivation is twofold. First, we provide pre-qualification data that the Bluefors cryostat, including filtering and wiring, can support long-lived qubits. Second, we demonstrate that the Keysight system (controlled using Labber) provides a straightforward solution to perform these characterization measurements. This document is intended as a brief guide for starting an experimental platform for testing superconducting qubits. The setup described here is an immediate jumping off point for a suite of applications including testing quantum logical gates, quantum optics with microwaves, or even using the qubit itself as a sensitive probe of local electromagnetic fields. Qubit measurements rely on high performance of both the physical sample environment and the measurement electronics. An overview of the cryogenic system is shown in Figure 1, and an overview of the integration between the electronics and cryostat (including wiring details) is shown in Figure 2.},
  author       = {Lake, Russell and Simbierowicz, Slawomir and Krantz, Philip and Hassani, Farid and Fink, Johannes M},
  keywords     = {Application note},
  pages        = {9},
  publisher    = {Bluefors Oy},
  title        = {{The Bluefors dilution refrigerator as an integrated quantum measurement system}},
  year         = {2021},
}

@misc{10645,
  abstract     = {Superconducting qubits have emerged as a highly versatile and useful platform for quantum technological applications [1]. Bluefors and Zurich Instruments have supported the growth of this field from the 2010s onwards by providing well-engineered and reliable measurement infrastructure [2]– [6]. Having a long and stable qubit lifetime is a critical system property. Therefore, considerable effort has already gone into measuring qubit energy-relaxation timescales and their fluctuations, see Refs. [7]–[10] among others. Accurately extracting the statistics of a quantum device requires users to perform time consuming measurements. One measurement challenge is that the detection of the state-dependent
response of a superconducting resonator due to a dispersively-coupled qubit requires an inherently low signal level. Consequently, measurements must be performed using a microwave probe that contains only a few microwave photons. Improving the signal-to-noise ratio (SNR) by using near-quantum limited parametric amplifiers as well as the use of optimized signal processing enabled by efficient room temperature instrumentation help to reduce measurement time. An empirical observation for fixed frequency transmons from recent literature is that as the energy-relaxation time 𝑇𝑇1 increases, so do its natural temporal fluctuations [7], [10]. This necessitates many repeated measurements to understand the statistics (see for example, Ref. [10]). In addition, as state-of-the-art qubits increase in lifetime, longer
measurement times are expected to obtain accurate statistics. As described below, the scaling of the widths of the qubit energy-relaxation distributions also reveal clues about the origin of the energy-relaxation.},
  author       = {Simbierowicz, Slawomir and Shi, Chunyan and Collodo, Michele and Kirste, Moritz and Hassani, Farid and Fink, Johannes M and Bylander, Jonas and Perez Lozano, Daniel and Lake, Russell},
  keywords     = {Application note},
  pages        = {8},
  publisher    = {Bluefors Oy},
  title        = {{Qubit energy-relaxation statistics in the Bluefors quantum measurement system}},
  year         = {2021},
}

@article{10655,
  abstract     = {Adeno-associated viruses (AAVs) are widely used to deliver genetic material in vivo to distinct cell types such as neurons or glial cells, allowing for targeted manipulation. Transduction of microglia is mostly excluded from this strategy, likely due to the cells’ heterogeneous state upon environmental changes, which makes AAV design challenging. Here, we established the retina as a model system for microglial AAV validation and optimization. First, we show that AAV2/6 transduced microglia in both synaptic layers, where layer preference corresponds to the intravitreal or subretinal delivery method. Surprisingly, we observed significantly enhanced microglial transduction during photoreceptor degeneration. Thus, we modified the AAV6 capsid to reduce heparin binding by introducing four point mutations (K531E, R576Q, K493S, and K459S), resulting in increased microglial transduction in the outer plexiform layer. Finally, to improve microglial-specific transduction, we validated a Cre-dependent transgene delivery cassette for use in combination with the Cx3cr1CreERT2 mouse line. Together, our results provide a foundation for future studies optimizing AAV-mediated microglia transduction and highlight that environmental conditions influence microglial transduction efficiency.
},
  author       = {Maes, Margaret E and Wögenstein, Gabriele M. and Colombo, Gloria and Casado Polanco, Raquel and Siegert, Sandra},
  issn         = {2329-0501},
  journal      = {Molecular Therapy - Methods and Clinical Development},
  pages        = {210--224},
  publisher    = {Elsevier},
  title        = {{Optimizing AAV2/6 microglial targeting identified enhanced efficiency in the photoreceptor degenerative environment}},
  doi          = {10.1016/j.omtm.2021.09.006},
  volume       = {23},
  year         = {2021},
}

@inproceedings{10668,
  abstract     = {Robustness to variations in lighting conditions is a key objective for any deep vision system. To this end, our paper extends the receptive field of convolutional neural networks with two residual components, ubiquitous in the visual processing system of vertebrates: On-center and off-center pathways, with an excitatory center and inhibitory surround; OOCS for short. The On-center pathway is excited by the presence of a light stimulus in its center, but not in its surround, whereas the Off-center pathway is excited by the absence of a light stimulus in its center, but not in its surround. We design OOCS pathways via a difference of Gaussians, with their variance computed analytically from the size of the receptive fields. OOCS pathways complement each other in their response to light stimuli, ensuring this way a strong edge-detection capability, and as a result an accurate and robust inference under challenging lighting conditions. We provide extensive empirical evidence showing that networks supplied with OOCS pathways gain accuracy and illumination-robustness from the novel edge representation, compared to other baselines.},
  author       = {Babaiee, Zahra and Hasani, Ramin and Lechner, Mathias and Rus, Daniela and Grosu, Radu},
  booktitle    = {Proceedings of the 38th International Conference on Machine Learning},
  issn         = {2640-3498},
  location     = {Virtual},
  pages        = {478--489},
  publisher    = {ML Research Press},
  title        = {{On-off center-surround receptive fields for accurate and robust image classification}},
  volume       = {139},
  year         = {2021},
}

@inproceedings{10688,
  abstract     = {Civl is a static verifier for concurrent programs designed around the conceptual framework of layered refinement,
which views the task of verifying a program as a sequence of program simplification steps each justified by its own invariant. Civl verifies a layered concurrent program that compactly expresses all the programs in this sequence and the supporting invariants. This paper presents the design and implementation of the Civl verifier.},
  author       = {Kragl, Bernhard and Qadeer, Shaz},
  booktitle    = {Proceedings of the 21st Conference on Formal Methods in Computer-Aided Design},
  editor       = {Ruzica, Piskac and Whalen, Michael W.},
  isbn         = {978-3-85448-046-4},
  location     = {Virtual},
  pages        = {143–152},
  publisher    = {TU Wien Academic Press},
  title        = {{The Civl verifier}},
  doi          = {10.34727/2021/isbn.978-3-85448-046-4_23},
  volume       = {2},
  year         = {2021},
}

@inproceedings{10694,
  abstract     = {In a two-player zero-sum graph game the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. Traditionally, the players alternate turns in moving the token. In bidding games, however, the players have budgets, and in each turn, we hold an “auction” (bidding) to determine which player moves the token: both players simultaneously submit bids and the higher bidder moves the token. The bidding mechanisms differ in their payment schemes. Bidding games were largely studied with variants of first-price bidding in which only the higher bidder pays his bid. We focus on all-pay bidding, where both players pay their bids. Finite-duration all-pay bidding games were studied and shown to be technically more challenging than their first-price counterparts. We study for the first time, infinite-duration all-pay bidding games. Our most interesting results are for mean-payoff objectives: we portray a complete picture for games played on strongly-connected graphs. We study both pure (deterministic) and mixed (probabilistic) strategies and completely characterize the optimal and almost-sure (with probability 1) payoffs the players can respectively guarantee. We show that mean-payoff games under all-pay bidding exhibit the intriguing mathematical properties of their first-price counterparts; namely, an equivalence with random-turn games in which in each turn, the player who moves is selected according to a (biased) coin toss. The equivalences for all-pay bidding are more intricate and unexpected than for first-price bidding.},
  author       = {Avni, Guy and Jecker, Ismael R and Zikelic, Dorde},
  booktitle    = {Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms},
  editor       = {Marx, Dániel},
  isbn         = {978-1-61197-646-5},
  location     = {Virtual},
  pages        = {617--636},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Infinite-duration all-pay bidding games}},
  doi          = {10.1137/1.9781611976465.38},
  year         = {2021},
}

@unpublished{10762,
  abstract     = {Methods inspired from machine learning have recently attracted great interest in the computational study of quantum many-particle systems. So far, however, it has proven challenging to deal with microscopic models in which the total number of particles is not conserved. To address this issue, we propose a new variant of neural network states, which we term neural coherent states. Taking the Fröhlich impurity model as a case study, we show that neural coherent states can learn the ground state of non-additive systems very well. In particular, we observe substantial improvement over the standard coherent state estimates in the most challenging intermediate coupling regime. Our approach is generic and does not assume specific details of the system, suggesting wide applications.},
  author       = {Rzadkowski, Wojciech and Lemeshko, Mikhail and Mentink, Johan H.},
  booktitle    = {arXiv},
  pages        = {2105.15193},
  title        = {{Artificial neural network states for non-additive systems}},
  doi          = {10.48550/arXiv.2105.15193},
  year         = {2021},
}

@unpublished{10803,
  abstract     = {Given the abundance of applications of ranking in recent years, addressing fairness concerns around automated ranking systems becomes necessary for increasing the trust among end-users. Previous work on fair ranking has mostly focused on application-specific fairness notions, often tailored to online advertising, and it rarely considers learning as part of the process. In this work, we show how to transfer numerous fairness notions from binary classification to a learning to rank setting. Our formalism allows us to design methods for incorporating fairness objectives with provable generalization guarantees. An extensive experimental evaluation shows that our method can improve ranking fairness substantially with no or only little loss of model quality.},
  author       = {Konstantinov, Nikola H and Lampert, Christoph},
  booktitle    = {arXiv},
  title        = {{Fairness through regularization for learning to rank}},
  doi          = {10.48550/arXiv.2102.05996},
  year         = {2021},
}

@article{10806,
  abstract     = {Ligands are a fundamental part of nanocrystals. They control and direct nanocrystal syntheses and provide colloidal stability. Bound ligands also affect the nanocrystals’ chemical reactivity and electronic structure. Surface chemistry is thus crucial to understand nanocrystal properties and functionality. Here, we investigate the synthesis of metal oxide nanocrystals (CeO2-x, ZnO, and NiO) from metal nitrate precursors, in the presence of oleylamine ligands. Surprisingly, the nanocrystals are capped exclusively with a fatty acid instead of oleylamine. Analysis of the reaction mixtures with nuclear magnetic resonance spectroscopy revealed several reaction byproducts and intermediates that are common to the decomposition of Ce, Zn, Ni, and Zr nitrate precursors. Our evidence supports the oxidation of alkylamine and formation of a carboxylic acid, thus unraveling this counterintuitive surface chemistry.},
  author       = {Calcabrini, Mariano and Van den Eynden, Dietger and Sanchez Ribot, Sergi and Pokratath, Rohan and Llorca, Jordi and De Roo, Jonathan and Ibáñez, Maria},
  issn         = {2691-3704},
  journal      = {JACS Au},
  keywords     = {general medicine},
  number       = {11},
  pages        = {1898--1903},
  publisher    = {American Chemical Society},
  title        = {{Ligand conversion in nanocrystal synthesis: The oxidation of alkylamines to fatty acids by nitrate}},
  doi          = {10.1021/jacsau.1c00349},
  volume       = {1},
  year         = {2021},
}

@article{7685,
  abstract     = {We consider a gas of interacting bosons trapped in a box of side length one in the Gross–Pitaevskii limit. We review the proof of the validity of Bogoliubov’s prediction for the ground state energy and the low-energy excitation spectrum. This note is based on joint work with C. Brennecke, S. Cenatiempo and B. Schlein.},
  author       = {Boccato, Chiara},
  issn         = {0129-055X},
  journal      = {Reviews in Mathematical Physics},
  number       = {1},
  publisher    = {World Scientific Publishing},
  title        = {{The excitation spectrum of the Bose gas in the Gross-Pitaevskii regime}},
  doi          = {10.1142/S0129055X20600065},
  volume       = {33},
  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 Publishing},
  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},
}