Showing 1–46 of 46 results for author: Neumann, S

Finite State Machine with Input and Process Render

Authors: Sierra Zoe Bennett-Manke, Sebastian Neumann, Ryan E. Dougherty

Abstract: Finite State Machines are a concept widely taught in undergraduate theory of computing courses. Educators typically use tools with static representations of FSMs to help students visualize these objects and processes; however, all existing tools require manual editing by the instructor. In this poster, we created an automatic visualization tool for FSMs that generates videos of FSM simulation, nam… ▽ More Finite State Machines are a concept widely taught in undergraduate theory of computing courses. Educators typically use tools with static representations of FSMs to help students visualize these objects and processes; however, all existing tools require manual editing by the instructor. In this poster, we created an automatic visualization tool for FSMs that generates videos of FSM simulation, named Finite State Machine with Input and Process Render (FSMIPR). Educators can input any formal definition of an FSM and an input string, and FSMIPR generates an accompanying video of its simulation. We believe that FSMIPR will be beneficial to students who learn difficult computer theory concepts. We conclude with future work currently in-progress with FSMIPR. △ Less

Submitted 25 September, 2024; originally announced September 2024.

Comments: Accepted to SIGCSE Virtual 2024

The Cross-environment Hyperparameter Setting Benchmark for Reinforcement Learning

Authors: Andrew Patterson, Samuel Neumann, Raksha Kumaraswamy, Martha White, Adam White

Abstract: This paper introduces a new empirical methodology, the Cross-environment Hyperparameter Setting Benchmark, that compares RL algorithms across environments using a single hyperparameter setting, encouraging algorithmic development which is insensitive to hyperparameters. We demonstrate that this benchmark is robust to statistical noise and obtains qualitatively similar results across repeated appli… ▽ More This paper introduces a new empirical methodology, the Cross-environment Hyperparameter Setting Benchmark, that compares RL algorithms across environments using a single hyperparameter setting, encouraging algorithmic development which is insensitive to hyperparameters. We demonstrate that this benchmark is robust to statistical noise and obtains qualitatively similar results across repeated applications, even when using few samples. This robustness makes the benchmark computationally cheap to apply, allowing statistically sound insights at low cost. We demonstrate two example instantiations of the CHS, on a set of six small control environments (SC-CHS) and on the entire DM Control suite of 28 environments (DMC-CHS). Finally, to illustrate the applicability of the CHS to modern RL algorithms on challenging environments, we conduct a novel empirical study of an open question in the continuous control literature. We show, with high confidence, that there is no meaningful difference in performance between Ornstein-Uhlenbeck noise and uncorrelated Gaussian noise for exploration with the DDPG algorithm on the DMC-CHS. △ Less

Submitted 26 July, 2024; originally announced July 2024.

Comments: Accepted to RLC 2024

Sublinear-Time Opinion Estimation in the Friedkin--Johnsen Model

Authors: Stefan Neumann, Yinhao Dong, Pan Peng

Abstract: Online social networks are ubiquitous parts of modern societies and the discussions that take place in these networks impact people's opinions on diverse topics, such as politics or vaccination. One of the most popular models to formally describe this opinion formation process is the Friedkin--Johnsen (FJ) model, which allows to define measures, such as the polarization and the disagreement of a n… ▽ More Online social networks are ubiquitous parts of modern societies and the discussions that take place in these networks impact people's opinions on diverse topics, such as politics or vaccination. One of the most popular models to formally describe this opinion formation process is the Friedkin--Johnsen (FJ) model, which allows to define measures, such as the polarization and the disagreement of a network. Recently, Xu, Bao and Zhang (WebConf'21) showed that all opinions and relevant measures in the FJ model can be approximated in near-linear time. However, their algorithm requires the entire network and the opinions of all nodes as input. Given the sheer size of online social networks and increasing data-access limitations, obtaining the entirety of this data might, however, be unrealistic in practice. In this paper, we show that node opinions and all relevant measures, like polarization and disagreement, can be efficiently approximated in time that is sublinear in the size of the network. Particularly, our algorithms only require query-access to the network and do not have to preprocess the graph. Furthermore, we use a connection between FJ opinion dynamics and personalized PageRank, and show that in $d$-regular graphs, we can deterministically approximate each node's opinion by only looking at a constant-size neighborhood, independently of the network size. We also experimentally validate that our estimation algorithms perform well in practice. △ Less

Submitted 25 April, 2024; originally announced April 2024.

Comments: To appear at the 2024 ACM Web Conference

Modeling the Impact of Timeline Algorithms on Opinion Dynamics Using Low-rank Updates

Authors: Tianyi Zhou, Stefan Neumann, Kiran Garimella, Aristides Gionis

Abstract: Timeline algorithms are key parts of online social networks, but during recent years they have been blamed for increasing polarization and disagreement in our society. Opinion-dynamics models have been used to study a variety of phenomena in online social networks, but an open question remains on how these models can be augmented to take into account the fine-grained impact of user-level timeline… ▽ More Timeline algorithms are key parts of online social networks, but during recent years they have been blamed for increasing polarization and disagreement in our society. Opinion-dynamics models have been used to study a variety of phenomena in online social networks, but an open question remains on how these models can be augmented to take into account the fine-grained impact of user-level timeline algorithms. We make progress on this question by providing a way to model the impact of timeline algorithms on opinion dynamics. Specifically, we show how the popular Friedkin--Johnsen opinion-formation model can be augmented based on aggregate information, extracted from timeline data. We use our model to study the problem of minimizing the polarization and disagreement; we assume that we are allowed to make small changes to the users' timeline compositions by strengthening some topics of discussion and penalizing some others. We present a gradient descent-based algorithm for this problem, and show that under realistic parameter settings, our algorithm computes a $(1+\varepsilon)$-approximate solution in time $\tilde{O}(m\sqrt{n} \lg(1/\varepsilon))$, where $m$ is the number of edges in the graph and $n$ is the number of vertices. We also present an algorithm that provably computes an $\varepsilon$-approximation of our model in near-linear time. We evaluate our method on real-world data and show that it effectively reduces the polarization and disagreement in the network. Finally, we release an anonymized graph dataset with ground-truth opinions and more than 27\,000 nodes (the previously largest publicly available dataset contains less than 550 nodes). △ Less

Submitted 15 February, 2024; originally announced February 2024.

Comments: To appear at The WebConf 2024

Ontologies for increasing the FAIRness of plant research data

Authors: Kathryn Dumschott, Hannah Dörpholz, Marie-Angélique Laporte, Dominik Brilhaus, Andrea Schrader, Björn Usadel, Steffen Neumann, Elizabeth Arnaud, Angela Kranz

Abstract: The importance of improving the FAIRness (findability, accessibility, interoperability, reusability) of research data is undeniable, especially in the face of large, complex datasets currently being produced by omics technologies. Facilitating the integration of a dataset with other types of data increases the likelihood of reuse, and the potential of answering novel research questions. Ontologies… ▽ More The importance of improving the FAIRness (findability, accessibility, interoperability, reusability) of research data is undeniable, especially in the face of large, complex datasets currently being produced by omics technologies. Facilitating the integration of a dataset with other types of data increases the likelihood of reuse, and the potential of answering novel research questions. Ontologies are a useful tool for semantically tagging datasets as adding relevant metadata increases the understanding of how data was produced and increases its interoperability. Ontologies provide concepts for a particular domain as well as the relationships between concepts. By tagging data with ontology terms, data becomes both human and machine interpretable, allowing for increased reuse and interoperability. However, the task of identifying ontologies relevant to a particular research domain or technology is challenging, especially within the diverse realm of fundamental plant research. In this review, we outline the ontologies most relevant to the fundamental plant sciences and how they can be used to annotate data related to plant-specific experiments within metadata frameworks, such as Investigation-Study-Assay (ISA). We also outline repositories and platforms most useful for identifying applicable ontologies or finding ontology terms. △ Less

Submitted 25 August, 2023; originally announced September 2023.

Comments: 34 pages, 4 figures, 1 table, 1 supplementary table

Visualizing Overlapping Biclusterings and Boolean Matrix Factorizations

Authors: Thibault Marette, Pauli Miettinen, Stefan Neumann

Abstract: Finding (bi-)clusters in bipartite graphs is a popular data analysis approach. Analysts typically want to visualize the clusters, which is simple as long as the clusters are disjoint. However, many modern algorithms find overlapping clusters, making visualization more complicated. In this paper, we study the problem of visualizing \emph{a given clustering} of overlapping clusters in bipartite grap… ▽ More Finding (bi-)clusters in bipartite graphs is a popular data analysis approach. Analysts typically want to visualize the clusters, which is simple as long as the clusters are disjoint. However, many modern algorithms find overlapping clusters, making visualization more complicated. In this paper, we study the problem of visualizing \emph{a given clustering} of overlapping clusters in bipartite graphs and the related problem of visualizing Boolean Matrix Factorizations. We conceptualize three different objectives that any good visualization should satisfy: (1) proximity of cluster elements, (2) large consecutive areas of elements from the same cluster, and (3) large uninterrupted areas in the visualization, regardless of the cluster membership. We provide objective functions that capture these goals and algorithms that optimize these objective functions. Interestingly, in experiments on real-world datasets, we find that the best trade-off between these competing goals is achieved by a novel heuristic, which locally aims to place rows and columns with similar cluster membership next to each other. △ Less

Submitted 14 July, 2023; originally announced July 2023.

Comments: 17 pages, 7 figures, to be published in ECML PKDD 2023

Adversaries with Limited Information in the Friedkin--Johnsen Model

Authors: Sijing Tu, Stefan Neumann, Aristides Gionis

Abstract: In recent years, online social networks have been the target of adversaries who seek to introduce discord into societies, to undermine democracies and to destabilize communities. Often the goal is not to favor a certain side of a conflict but to increase disagreement and polarization. To get a mathematical understanding of such attacks, researchers use opinion-formation models from sociology, such… ▽ More In recent years, online social networks have been the target of adversaries who seek to introduce discord into societies, to undermine democracies and to destabilize communities. Often the goal is not to favor a certain side of a conflict but to increase disagreement and polarization. To get a mathematical understanding of such attacks, researchers use opinion-formation models from sociology, such as the Friedkin--Johnsen model, and formally study how much discord the adversary can produce when altering the opinions for only a small set of users. In this line of work, it is commonly assumed that the adversary has full knowledge about the network topology and the opinions of all users. However, the latter assumption is often unrealistic in practice, where user opinions are not available or simply difficult to estimate accurately. To address this concern, we raise the following question: Can an attacker sow discord in a social network, even when only the network topology is known? We answer this question affirmatively. We present approximation algorithms for detecting a small set of users who are highly influential for the disagreement and polarization in the network. We show that when the adversary radicalizes these users and if the initial disagreement/polarization in the network is not very high, then our method gives a constant-factor approximation on the setting when the user opinions are known. To find the set of influential users, we provide a novel approximation algorithm for a variant of MaxCut in graphs with positive and negative edge weights. We experimentally evaluate our methods, which have access only to the network topology, and we find that they have similar performance as methods that have access to the network topology and all user opinions. We further present an NP-hardness proof, which was an open question by Chen and Racz [IEEE Trans. Netw. Sci. Eng., 2021]. △ Less

Submitted 12 September, 2023; v1 submitted 17 June, 2023; originally announced June 2023.

Comments: KDD'23

Reducing Exposure to Harmful Content via Graph Rewiring

Authors: Corinna Coupette, Stefan Neumann, Aristides Gionis

Abstract: Most media content consumed today is provided by digital platforms that aggregate input from diverse sources, where access to information is mediated by recommendation algorithms. One principal challenge in this context is dealing with content that is considered harmful. Striking a balance between competing stakeholder interests, rather than block harmful content altogether, one approach is to min… ▽ More Most media content consumed today is provided by digital platforms that aggregate input from diverse sources, where access to information is mediated by recommendation algorithms. One principal challenge in this context is dealing with content that is considered harmful. Striking a balance between competing stakeholder interests, rather than block harmful content altogether, one approach is to minimize the exposure to such content that is induced specifically by algorithmic recommendations. Hence, modeling media items and recommendations as a directed graph, we study the problem of reducing the exposure to harmful content via edge rewiring. We formalize this problem using absorbing random walks, and prove that it is NP-hard and NP-hard to approximate to within an additive error, while under realistic assumptions, the greedy method yields a (1-1/e)-approximation. Thus, we introduce Gamine, a fast greedy algorithm that can reduce the exposure to harmful content with or without quality constraints on recommendations. By performing just 100 rewirings on YouTube graphs with several hundred thousand edges, Gamine reduces the initial exposure by 50%, while ensuring that its recommendations are at most 5% less relevant than the original recommendations. Through extensive experiments on synthetic data and real-world data from video recommendation and news feed applications, we confirm the effectiveness, robustness, and efficiency of Gamine in practice. △ Less

Submitted 5 June, 2023; originally announced June 2023.

Comments: 25 pages, 28 figures, accepted at KDD 2023

Empirical Design in Reinforcement Learning

Authors: Andrew Patterson, Samuel Neumann, Martha White, Adam White

Abstract: Empirical design in reinforcement learning is no small task. Running good experiments requires attention to detail and at times significant computational resources. While compute resources available per dollar have continued to grow rapidly, so have the scale of typical experiments in reinforcement learning. It is now common to benchmark agents with millions of parameters against dozens of tasks,… ▽ More Empirical design in reinforcement learning is no small task. Running good experiments requires attention to detail and at times significant computational resources. While compute resources available per dollar have continued to grow rapidly, so have the scale of typical experiments in reinforcement learning. It is now common to benchmark agents with millions of parameters against dozens of tasks, each using the equivalent of 30 days of experience. The scale of these experiments often conflict with the need for proper statistical evidence, especially when comparing algorithms. Recent studies have highlighted how popular algorithms are sensitive to hyper-parameter settings and implementation details, and that common empirical practice leads to weak statistical evidence (Machado et al., 2018; Henderson et al., 2018). Here we take this one step further. This manuscript represents both a call to action, and a comprehensive resource for how to do good experiments in reinforcement learning. In particular, we cover: the statistical assumptions underlying common performance measures, how to properly characterize performance variation and stability, hypothesis testing, special considerations for comparing multiple agents, baseline and illustrative example construction, and how to deal with hyper-parameters and experimenter bias. Throughout we highlight common mistakes found in the literature and the statistical consequences of those in example experiments. The objective of this document is to provide answers on how we can use our unprecedented compute to do good science in reinforcement learning, as well as stay alert to potential pitfalls in our empirical design. △ Less

Submitted 3 April, 2023; originally announced April 2023.

Comments: In submission to JMLR

Photonic entanglement during a zero-g flight

Authors: Julius Bittermann, Lukas Bulla, Sebastian Ecker, Sebastian Philipp Neumann, Matthias Fink, Martin Bohmann, Nicolai Friis, Marcus Huber, Rupert Ursin

Abstract: Quantum technologies have matured to the point that we can test fundamental quantum phenomena under extreme conditions. Specifically, entanglement, a cornerstone of modern quantum information theory, can be robustly produced and verified in various adverse environments. We take these tests further and implement a high-quality Bell experiment during a parabolic flight, transitioning from microgravi… ▽ More Quantum technologies have matured to the point that we can test fundamental quantum phenomena under extreme conditions. Specifically, entanglement, a cornerstone of modern quantum information theory, can be robustly produced and verified in various adverse environments. We take these tests further and implement a high-quality Bell experiment during a parabolic flight, transitioning from microgravity to hypergravity of 1.8 g while continuously observing Bell violation, with Bell-CHSH parameters between $S=-2.6202$ and $-2.7323$, an average of $\overline{S} = -2.680$, and average standard deviation of $\overline{ΔS} = 0.014$. This violation is unaffected both by uniform and non-uniform acceleration. This experiment demonstrates the stability of current quantum communication platforms for space-based applications and adds an important reference point for testing the interplay of non-inertial motion and quantum information. △ Less

Submitted 12 February, 2024; v1 submitted 23 March, 2023; originally announced March 2023.

Comments: 10+12 pages, 18 figures

Journal ref: Quantum 8, 1256 (2024)

Distribution of genuine high-dimensional entanglement over 10.2 km of noisy metropolitan atmosphere

Authors: Lukas Bulla, Kristian Hjorth, Oskar Kohout, Jan Lang, Sebastian Ecker, Sebastian P. Neumann, Julius Bittermann, Robert Kindler, Marcus Huber, Martin Bohmann, Rupert Ursin, Matej Pivoluska

Abstract: In a recent quantum key distribution experiment, high-dimensional protocols were used to show an improved noise resistance over a 10.2 km free-space channel. One of the unresolved questions in this context is whether the communicating parties actually shared genuine high-dimensional entanglement. In this letter we introduce an improved discretisation and entanglement certification scheme for high-… ▽ More In a recent quantum key distribution experiment, high-dimensional protocols were used to show an improved noise resistance over a 10.2 km free-space channel. One of the unresolved questions in this context is whether the communicating parties actually shared genuine high-dimensional entanglement. In this letter we introduce an improved discretisation and entanglement certification scheme for high-dimensional time-bin setups and apply it to the data obtained during the experiment. Our analysis answers the aforementioned question affirmatively and thus the experiment constitutes the first transmission of genuine high-dimensional entanglement in a single degree of freedom over a long-range free-space channel. △ Less

Submitted 13 January, 2023; originally announced January 2023.

Comments: 6 pages, 3 figures

Dynamic Maintenance of Monotone Dynamic Programs and Applications

Authors: Monika Henzinger, Stefan Neumann, Harald Räcke, Stefan Schmid

Abstract: Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or tota… ▽ More Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity. In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce a novel data structure for computing $(1+\varepsilon)$-approximate DP solutions in near-linear time and space in the static setting, and with polylogarithmic update times when the DP entries change dynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-$n$ DP table rows with entries in $[0,W]$ using only polylog$(n,W)$ bits, and to perform operations, such as $(\min,+)$-convolution or rounding, on these functions in polylogarithmic time. We further present several applications of our data structure. For bicriteria versions of $k$-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack. △ Less

Submitted 4 January, 2023; originally announced January 2023.

Comments: Abstract shortened to comply with arxiv formatting rules. To appear at STACS'23

Resolving diverse oxygen transport pathways across Sr-doped lanthanum ferrite and metal-perovskite heterostructures

Authors: Sandra D. Taylor, Kayla H. Yano, Michel Sassi, Bethany E. Matthews, Sten V. Lambeets, Sydney Neumann, Daniel K. Schreiber, Le Wang, Yingge Du, Steven R. Spurgeon

Abstract: Perovskite structured transition metal oxides are important technological materials for catalysis and solid oxide fuel cell applications. Their functionality often depends on oxygen diffusivity and mobility through complex oxide heterostructures, which can be significantly impacted by structural and chemical modifications, such as doping. Further, when utilized within electrochemical cells, interf… ▽ More Perovskite structured transition metal oxides are important technological materials for catalysis and solid oxide fuel cell applications. Their functionality often depends on oxygen diffusivity and mobility through complex oxide heterostructures, which can be significantly impacted by structural and chemical modifications, such as doping. Further, when utilized within electrochemical cells, interfacial reactions with other components (e.g. Ni- and Cr-based alloy electrodes and interconnects) can influence the perovskite's reactivity and ion transport, leading to complex dependencies that are difficult to control in real-world environments. Here we use isotopic tracers and atom probe tomography to directly visualize oxygen diffusion and transport pathways across perovskite and metal-perovskite heterostructures, i.e. (Ni-Cr coated) Sr-doped lanthanum ferrite (LSFO). Annealing in 18O2(g) results in elemental and isotopic redistributions through oxygen exchange (OE) in the LSFO while Ni-Cr undergoes oxidation via multiple mechanisms and transport pathways. Complementary density functional theory (DFT) calculations at experimental conditions provide rationale for OE reaction mechanisms and reveal a complex interplay of different thermodynamic and kinetic drivers. Our results shed light on the fundamental coupling of defects and oxygen transport in an important class of catalytic materials. △ Less

Submitted 19 September, 2022; originally announced September 2022.

Comments: 39 pages, 10 figures

Spatial and spectral characterization of photon pairs at telecommunication-wavelength from type-0 spontaneous parametric down-conversion

Authors: Evelyn A. Ortega, Jorge Fuenzalida, Mirela Selimovic, Krishna Dovzhik, Lukas Achatz, Soeren Wengerowsky, Rodrigo F. Shiozaki, Sebastian Philipp Neumann, Martin Bohmann, Rupert Ursin

Abstract: The thorough characterization of entangled-photon sources is vital for their optimal use in quantum communication. However, this task is not trivial at telecommunication wavelengths. While cameras and spectrometers are well developed for visible and near-infrared spectra, that does not apply in the mid-infrared range. Here we present a spatial and spectral characterization of photon pairs emitted… ▽ More The thorough characterization of entangled-photon sources is vital for their optimal use in quantum communication. However, this task is not trivial at telecommunication wavelengths. While cameras and spectrometers are well developed for visible and near-infrared spectra, that does not apply in the mid-infrared range. Here we present a spatial and spectral characterization of photon pairs emitted in a type-0 phase-matched spontaneous parametric down-converted source. We experimentally show how these photon properties are modified by the crystal temperature. This parameter allows easy modification of photon-pair properties to fit novel multiplexing schemes based on only one entanglement photon source. Our results pave the way for the optimal design and use of spatial and spectral properties of quantum-correlated photon pairs at telecommunication wavelengths. △ Less

Submitted 31 August, 2022; originally announced September 2022.

Journal ref: J. Opt. Soc. Am. B 40, 165-171 (2023)

Sublinear-Time Clustering Oracle for Signed Graphs

Authors: Stefan Neumann, Pan Peng

Abstract: Social networks are often modeled using signed graphs, where vertices correspond to users and edges have a sign that indicates whether an interaction between users was positive or negative. The arising signed graphs typically contain a clear community structure in the sense that the graph can be partitioned into a small number of polarized communities, each defining a sparse cut and indivisible in… ▽ More Social networks are often modeled using signed graphs, where vertices correspond to users and edges have a sign that indicates whether an interaction between users was positive or negative. The arising signed graphs typically contain a clear community structure in the sense that the graph can be partitioned into a small number of polarized communities, each defining a sparse cut and indivisible into smaller polarized sub-communities. We provide a local clustering oracle for signed graphs with such a clear community structure, that can answer membership queries, i.e., "Given a vertex $v$, which community does $v$ belong to?", in sublinear time by reading only a small portion of the graph. Formally, when the graph has bounded maximum degree and the number of communities is at most $O(\log n)$, then with $\tilde{O}(\sqrt{n}\operatorname{poly}(1/\varepsilon))$ preprocessing time, our oracle can answer each membership query in $\tilde{O}(\sqrt{n}\operatorname{poly}(1/\varepsilon))$ time, and it correctly classifies a $(1-\varepsilon)$-fraction of vertices w.r.t. a set of hidden planted ground-truth communities. Our oracle is desirable in applications where the clustering information is needed for only a small number of vertices. Previously, such local clustering oracles were only known for unsigned graphs; our generalization to signed graphs requires a number of new ideas and gives a novel spectral analysis of the behavior of random walks with signs. We evaluate our algorithm for constructing such an oracle and answering membership queries on both synthetic and real-world datasets, validating its performance in practice. △ Less

Submitted 28 June, 2022; originally announced June 2022.

Comments: To appear at ICML'22

Non-local temporal interferometry for highly resilient free-space quantum communication

Authors: Lukas Bulla, Matej Pivoluska, Kristian Hjorth, Oskar Kohout, Jan Lang, Sebastian Ecker, Sebastian Philipp Neumann, Julius Bittermann, Robert Kindler, Marcus Huber, Martin Bohmann, Rupert Ursin

Abstract: Entanglement distribution via photons over long distances enables many applications, including quantum key distribution (QKD), which provides unprecedented privacy. The inevitable degradation of entanglement through noise accumulated over long distances remains one of the key challenges in this area. Exploiting the potential of higher-dimensional entangled photons promises to address this challeng… ▽ More Entanglement distribution via photons over long distances enables many applications, including quantum key distribution (QKD), which provides unprecedented privacy. The inevitable degradation of entanglement through noise accumulated over long distances remains one of the key challenges in this area. Exploiting the potential of higher-dimensional entangled photons promises to address this challenge, but poses extreme demands on the experimental implementation. Here, we present an interstate free-space quantum link, distributing hyper-entanglement over $10.2\,$km with flexible dimensionality of encoding by deploying a phase-stable non-local Franson interferometer. With this distribution of multidimensional energy-time entangled photons, we analyse the achievable key rate in a dimensionally-adaptive QKD protocol that can be optimized with respect to any environmental noise conditions. Our approach enables and emphasises the power of high-dimensional entanglement for quantum communication, yielding a positive asymptotic key rate well into the dawn of the day. △ Less

Submitted 15 April, 2022; originally announced April 2022.

Comments: 11 pages, 4 figures

Journal ref: Phys. Rev. X 13, 021001 (2023)

Continuous entanglement distribution over a transnational 248 km fibre link

Authors: Sebastian Philipp Neumann, Alexander Buchner, Lukas Bulla, Martin Bohmann, Rupert Ursin

Abstract: Entanglement is the basis of many quantum applications. The technically most mature of them, quantum key distribution, harnesses quantum correlations of entangled photons to produce cryptographic keys of provably unbreakable security. A key challenge in this context is the establishment of continuously working, reliable long-distance distributions of entanglement. However, connections via satellit… ▽ More Entanglement is the basis of many quantum applications. The technically most mature of them, quantum key distribution, harnesses quantum correlations of entangled photons to produce cryptographic keys of provably unbreakable security. A key challenge in this context is the establishment of continuously working, reliable long-distance distributions of entanglement. However, connections via satellites don't allow for interruption-free operation, and deployed fibre implementations have so far been limited to less than 100 km by losses, a few hours of duty time, or use trusted nodes. Here, we present a continuously working international link between Austria and Slovakia, directly distributing polarization-entangled photon pairs via 248 km of deployed telecommunication fibre. Despite 79 dB loss, we measure stable pair rates of 9 s$^{-1}$ over an exemplary operation time of 110 hours. We mitigate multi-pair detections with strict temporal filtering, enabled by nonlocal compensation of chromatic dispersion. Fully automatized active polarization stabilization keeps the entangled state's visibility at 86 % for altogether 82 hours, producing 403 kbit of quantum-secure key at a rate of 1.4 bits/s. Our work paves the way for low-maintenance, ultra-stable quantum communication over long distances, independent of cloud coverage and time of day, thus constituting an important step towards the quantum internet. △ Less

Submitted 23 March, 2022; originally announced March 2022.

Comments: 23 pages, 6 figures

Journal ref: Nature Communications 13, 6134 (2022)

Unconditionally secure digital signatures implemented in an 8-user quantum network

Authors: Yoann Pelet, Ittoop Vergheese Puthoor, Natarajan Venkatachalam, Sören Wengerowsky, Martin Lončarić, Sebastian Philipp Neumann, Bo Liu, Željko Samec, Mario Stipčević, Rupert Ursin, Erika Andersson, John G. Rarity, Djeylan Aktas, Siddarth Koduru Joshi

Abstract: The ability to know and verifiably demonstrate the origins of messages can often be as important as encrypting the message itself. Here we present an experimental demonstration of an unconditionally secure digital signature (USS) protocol implemented for the first time, to the best of our knowledge, on a fully connected quantum network without trusted nodes. Our USS protocol is secure against forg… ▽ More The ability to know and verifiably demonstrate the origins of messages can often be as important as encrypting the message itself. Here we present an experimental demonstration of an unconditionally secure digital signature (USS) protocol implemented for the first time, to the best of our knowledge, on a fully connected quantum network without trusted nodes. Our USS protocol is secure against forging, repudiation and messages are transferrable. We show the feasibility of unconditionally secure signatures using only bi-partite entangled states distributed throughout the network and experimentally evaluate the performance of the protocol in real world scenarios with varying message lengths. △ Less

Submitted 10 February, 2022; v1 submitted 9 February, 2022; originally announced February 2022.

Comments: Preprint, 9 pages, 7 figures, 1 table

A Viral Marketing-Based Model For Opinion Dynamics in Online Social Networks

Authors: Sijing Tu, Stefan Neumann

Abstract: Online social networks provide a medium for citizens to form opinions on different societal issues, and a forum for public discussion. They also expose users to viral content, such as breaking news articles. In this paper, we study the interplay between these two aspects: opinion formation and information cascades in online social networks. We present a new model that allows us to quantify how use… ▽ More Online social networks provide a medium for citizens to form opinions on different societal issues, and a forum for public discussion. They also expose users to viral content, such as breaking news articles. In this paper, we study the interplay between these two aspects: opinion formation and information cascades in online social networks. We present a new model that allows us to quantify how users change their opinion as they are exposed to viral content. Our model is a combination of the popular Friedkin--Johnsen model for opinion dynamics and the independent cascade model for information propagation. We present algorithms for simulating our model, and we provide approximation algorithms for optimizing certain network indices, such as the sum of user opinions or the disagreement--controversy index; our approach can be used to obtain insights into how much viral content can increase these indices in online social networks. Finally, we evaluate our model on real-world datasets. We show experimentally that marketing campaigns and polarizing contents have vastly different effects on the network: while the former have only limited effect on the polarization in the network, the latter can increase the polarization up to 59% even when only 0.5% of the users start sharing a polarizing content. We believe that this finding sheds some light into the growing segregation in today's online media. △ Less

Submitted 8 April, 2022; v1 submitted 7 February, 2022; originally announced February 2022.

Comments: To appear at WebConf'22. Correct the errors of scales in Figure 2

Experimental entanglement generation for quantum key distribution beyond 1 Gbit/s

Authors: Sebastian Philipp Neumann, Mirela Selimovic, Martin Bohmann, Rupert Ursin

Abstract: Top-performance sources of photonic entanglement are an indispensable resource for many applications in quantum communication, most notably quantum key distribution. However, up to now, no source has been shown to simultaneously exhibit the high pair-creation rate, broad bandwidth, excellent state fidelity, and low intrinsic loss necessary for gigabit secure key rates. In this work, we present for… ▽ More Top-performance sources of photonic entanglement are an indispensable resource for many applications in quantum communication, most notably quantum key distribution. However, up to now, no source has been shown to simultaneously exhibit the high pair-creation rate, broad bandwidth, excellent state fidelity, and low intrinsic loss necessary for gigabit secure key rates. In this work, we present for the first time a source of polarization-entangled photon pairs at telecommunication wavelengths that covers all these needs of real-world quantum-cryptographic applications, thus enabling unprecedented quantum-secure key rates of more than 1 Gbit/s. Our source is designed to optimally exploit state-of-the-art telecommunication equipment and detection systems. Any technological improvement of the latter would result in an even higher rate without modification of the source. We discuss the used wavelength-multiplexing approach, including its potential for multi-user quantum networks and its fundamental limitations. Our source paves the way for high-speed quantum encryption approaching present-day internet bandwidth. △ Less

Submitted 26 September, 2022; v1 submitted 16 July, 2021; originally announced July 2021.

Comments: 8 pages, 6 figures v1: Typos corrected v2: typos corrected, certain aspects emphasized, additional measurement included; v4: Final version peer-reviewed and accepted by Quantum

Journal ref: Quantum 6, 822 (2022)

A model for optimizing quantum key distribution with continuous-wave pumped entangled-photon sources

Authors: Sebastian Philipp Neumann, Thomas Scheidl, Mirela Selimovic, Matej Pivoluska, Bo Liu, Martin Bohmann, Rupert Ursin

Abstract: Quantum Key Distribution (QKD) allows unconditionally secure communication based on the laws of quantum mechanics rather then assumptions about computational hardness. Optimizing the operation parameters of a given QKD implementation is indispensable in order to achieve high secure key rates. So far, there exists no model that accurately describes entanglement-based QKD with continuous-wave pump l… ▽ More Quantum Key Distribution (QKD) allows unconditionally secure communication based on the laws of quantum mechanics rather then assumptions about computational hardness. Optimizing the operation parameters of a given QKD implementation is indispensable in order to achieve high secure key rates. So far, there exists no model that accurately describes entanglement-based QKD with continuous-wave pump lasers. For the first time, we analyze the underlying mechanisms for QKD with temporally uniform pair-creation probabilities and develop a simple but accurate model to calculate optimal trade-offs for maximal secure key rates. In particular, we find an optimization strategy of the source brightness for given losses and detection-time resolution. All experimental parameters utilized by the model can be inferred directly in standard QKD implementations, and no additional assessment of device performance is required. Comparison with experimental data shows the validity of our model. Our results yield a tool to determine optimal operation parameters for already existing QKD systems, to plan a full QKD implementation from scratch, and to determine fundamental key rate and distance limits of given connections. △ Less

Submitted 22 July, 2021; v1 submitted 26 March, 2021; originally announced March 2021.

Comments: 12 pages, 6 figures. [v2]: Small corrections of footnotes and references [v3]: More typos corrected, Fig. 1 changed and corrected, Fig. 2 information added

Journal ref: Phys. Rev. A 104, 022406 (2021)

Scalable authentication and optimal flooding in a quantum network

Authors: Naomi R. Solomons, Alasdair I. Fletcher, Djeylan Aktas, Natarajan Venkatachalam, Sören Wengerowsky, Martin Lončarić, Sebastian P. Neumann, Bo Liu, Željko Samec, Mario Stipčević, Rupert Ursin, Stefano Pirandola, John G. Rarity, Siddarth Koduru Joshi

Abstract: The global interest in quantum networks stems from the security guaranteed by the laws of physics. Deploying quantum networks means facing the challenges of scaling up the physical hardware and, more importantly, of scaling up all other network layers and optimally utilising network resources. Here we consider two related protocols, their experimental demonstrations on an 8-user quantum network te… ▽ More The global interest in quantum networks stems from the security guaranteed by the laws of physics. Deploying quantum networks means facing the challenges of scaling up the physical hardware and, more importantly, of scaling up all other network layers and optimally utilising network resources. Here we consider two related protocols, their experimental demonstrations on an 8-user quantum network test-bed, and discuss their usefulness with the aid of example use cases. First, an authentication transfer protocol to manage a fundamental limitation of quantum communication -- the need for a pre-shared key between every pair of users linked together on the quantum network. By temporarily trusting some intermediary nodes for a short period of time (<35 min in our network), we can generate and distribute these initial authentication keys with a very high level of security. Second, when end users quantify their trust in intermediary nodes, our flooding protocol can be used to improve both end-to-end communication speeds and increase security against malicious nodes. △ Less

Submitted 21 June, 2023; v1 submitted 28 January, 2021; originally announced January 2021.

Comments: New version includes changes suggested by referees, and a modification to an incorrect calculation. Fig. 6 has been updated correspondingly. With thanks to Rui Wang for spotting the mistake, and the referees for detailed feedback

Journal ref: PRX Quantum 3, 020311 (2022)

Biclustering and Boolean Matrix Factorization in Data Streams

Authors: Stefan Neumann, Pauli Miettinen

Abstract: We study the clustering of bipartite graphs and Boolean matrix factorization in data streams. We consider a streaming setting in which the vertices from the left side of the graph arrive one by one together with all of their incident edges. We provide an algorithm that, after one pass over the stream, recovers the set of clusters on the right side of the graph using sublinear space; to the best of… ▽ More We study the clustering of bipartite graphs and Boolean matrix factorization in data streams. We consider a streaming setting in which the vertices from the left side of the graph arrive one by one together with all of their incident edges. We provide an algorithm that, after one pass over the stream, recovers the set of clusters on the right side of the graph using sublinear space; to the best of our knowledge, this is the first algorithm with this property. We also show that after a second pass over the stream, the left clusters of the bipartite graph can be recovered and we show how to extend our algorithm to solve the Boolean matrix factorization problem (by exploiting the correspondence of Boolean matrices and bipartite graphs). We evaluate an implementation of the algorithm on synthetic data and on real-world data. On real-world datasets the algorithm is orders of magnitudes faster than a static baseline algorithm while providing quality results within a factor 2 of the baseline algorithm. Our algorithm scales linearly in the number of edges in the graph. Finally, we analyze the algorithm theoretically and provide sufficient conditions under which the algorithm recovers a set of planted clusters under a standard random graph model. △ Less

Submitted 5 December, 2020; originally announced December 2020.

Comments: This technical report is the slightly extended version of a paper [34] which appeared at VLDB'20

Recent Developments in Boolean Matrix Factorization

Authors: Pauli Miettinen, Stefan Neumann

Abstract: The goal of Boolean Matrix Factorization (BMF) is to approximate a given binary matrix as the product of two low-rank binary factor matrices, where the product of the factor matrices is computed under the Boolean algebra. While the problem is computationally hard, it is also attractive because the binary nature of the factor matrices makes them highly interpretable. In the last decade, BMF has rec… ▽ More The goal of Boolean Matrix Factorization (BMF) is to approximate a given binary matrix as the product of two low-rank binary factor matrices, where the product of the factor matrices is computed under the Boolean algebra. While the problem is computationally hard, it is also attractive because the binary nature of the factor matrices makes them highly interpretable. In the last decade, BMF has received a considerable amount of attention in the data mining and formal concept analysis communities and, more recently, the machine learning and the theory communities also started studying BMF. In this survey, we give a concise summary of the efforts of all of these communities and raise some open questions which in our opinion require further investigation. △ Less

Submitted 5 December, 2020; originally announced December 2020.

Comments: This technical report is the slightly extended version of a survey which appeared at IJCAI'20

Experimental implementation of secure anonymous protocols on an eight-user quantum network

Authors: Zixin Huang, Siddarth Koduru Joshi, Djeylan Aktas, Cosmo Lupo, Armanda O. Quintavalle, Natarajan Venkatachalam, Sören Wengerowsky, Martin Lončarić, Sebastian Philipp Neumann, Bo Liu, Željko Samec, Laurent Kling, Mario Stipčević, Rupert Ursin, John G. Rarity

Abstract: Anonymity in networked communication is vital for many privacy-preserving tasks. Secure key distribution alone is insufficient for high-security communications, often knowing who transmits a message to whom and when must also be kept hidden from an adversary. Here we experimentally demonstrate 5 information-theoretically secure anonymity protocols on an 8 user city-wide quantum network using polar… ▽ More Anonymity in networked communication is vital for many privacy-preserving tasks. Secure key distribution alone is insufficient for high-security communications, often knowing who transmits a message to whom and when must also be kept hidden from an adversary. Here we experimentally demonstrate 5 information-theoretically secure anonymity protocols on an 8 user city-wide quantum network using polarisation-entangled photon pairs. At the heart of these protocols is anonymous broadcasting, which is a cryptographic primitive that allows one user to reveal one bit of information while keeping her identity anonymous. For a network of $n$ users, the protocols retain anonymity for the sender, given less than $n-2$ users are dishonest. This is one of the earliest implementations of genuine multi-user cryptographic protocols beyond standard QKD. Our anonymous protocols enhance the functionality of any fully-connected Quantum Key Distribution network without trusted nodes. △ Less

Submitted 18 November, 2020; originally announced November 2020.

Comments: 11 pages, 4 figures, 1 table, experimental work. ZH and SKJ contributed equally to this work and are joint first authors

Tight Bounds for Online Graph Partitioning

Authors: Monika Henzinger, Stefan Neumann, Harald Räcke, Stefan Schmid

Abstract: We consider the following online optimization problem. We are given a graph $G$ and each vertex of the graph is assigned to one of $\ell$ servers, where servers have capacity $k$ and we assume that the graph has $\ell \cdot k$ vertices. Initially, $G$ does not contain any edges and then the edges of $G$ are revealed one-by-one. The goal is to design an online algorithm $\operatorname{ONL}$, which… ▽ More We consider the following online optimization problem. We are given a graph $G$ and each vertex of the graph is assigned to one of $\ell$ servers, where servers have capacity $k$ and we assume that the graph has $\ell \cdot k$ vertices. Initially, $G$ does not contain any edges and then the edges of $G$ are revealed one-by-one. The goal is to design an online algorithm $\operatorname{ONL}$, which always places the connected components induced by the revealed edges on the same server and never exceeds the server capacities by more than $\varepsilon k$ for constant $\varepsilon>0$. Whenever $\operatorname{ONL}$ learns about a new edge, the algorithm is allowed to move vertices from one server to another. Its objective is to minimize the number of vertex moves. More specifically, $\operatorname{ONL}$ should minimize the competitive ratio: the total cost $\operatorname{ONL}$ incurs compared to an optimal offline algorithm $\operatorname{OPT}$. Our main contribution is a polynomial-time randomized algorithm, that is asymptotically optimal: we derive an upper bound of $O(\log \ell + \log k)$ on its competitive ratio and show that no randomized online algorithm can achieve a competitive ratio of less than $Ω(\log \ell + \log k)$. We also settle the open problem of the achievable competitive ratio by deterministic online algorithms, by deriving a competitive ratio of $Θ(\ell \lg k)$; to this end, we present an improved lower bound as well as a deterministic polynomial-time online algorithm. Our algorithms rely on a novel technique which combines efficient integer programming with a combinatorial approach for maintaining ILP solutions. We believe this technique is of independent interest and will find further applications in the future. △ Less

Submitted 2 November, 2020; originally announced November 2020.

Comments: Full version of a paper that will appear at SODA'21. Abstract shortened to obey arxiv's abstract requirements

A low-noise single-photon detector for long-distance free-space quantum communication

Authors: Elena Anisimova, Dmitri Nikulov, Simeng Simone Hu, Mark Bourgon, Sebastian Philipp Neumann, Rupert Ursin, Thomas Jennewein, Vadim Makarov

Abstract: We build and test a single-photon detector based on a Si avalanche photodiode Excelitas 30902SH thermoelectrically cooled to -100 deg. C. Our detector has dark count rate below 1 Hz, 500 um diameter photosensitive area, photon detection efficiency around 50%, afterpulsing less than 0.35%, and timing jitter under 1 ns. These characteristics make it suitable for long-distance free-space quantum comm… ▽ More We build and test a single-photon detector based on a Si avalanche photodiode Excelitas 30902SH thermoelectrically cooled to -100 deg. C. Our detector has dark count rate below 1 Hz, 500 um diameter photosensitive area, photon detection efficiency around 50%, afterpulsing less than 0.35%, and timing jitter under 1 ns. These characteristics make it suitable for long-distance free-space quantum communication links, which we briefly discuss. We also report an improved method that we call long-time afterpulsing analysis, used to determine and visualise long trap lifetimes at different temperatures. △ Less

Submitted 8 December, 2021; v1 submitted 24 July, 2020; originally announced July 2020.

Comments: 10 pages, 9 figures, 1 table

Journal ref: EPJ Quantum Technol. 8, 23 (2021)

Experimentally optimizing QKD rates via nonlocal dispersion compensation

Authors: Sebastian Philipp Neumann, Domenico Ribezzo, Martin Bohmann, Rupert Ursin

Abstract: Quantum key distribution (QKD) enables unconditionally secure communication guaranteed by the laws of physics. The last decades have seen tremendous efforts in making this technology feasible under real-life conditions, with implementations bridging ever longer distances and creating ever higher secure key rates. Readily deployed glass fiber connections are a natural choice for distributing the si… ▽ More Quantum key distribution (QKD) enables unconditionally secure communication guaranteed by the laws of physics. The last decades have seen tremendous efforts in making this technology feasible under real-life conditions, with implementations bridging ever longer distances and creating ever higher secure key rates. Readily deployed glass fiber connections are a natural choice for distributing the single photons necessary for QKD both in intra- and intercity links. Any fiber-based implementation however experiences chromatic dispersion which deteriorates temporal detection precision. This ultimately limits maximum distance and achievable key rate of such QKD systems. In this work, we address this limitation to both maximum distance and key rate and present an effective and easy-to-implement method to overcome chromatic dispersion effects. By exploiting the entangled photons' frequency correlations, we make use of nonlocal dispersion compensation to improve the photons' temporal correlations. Our experiment is the first implementation utilizing the inherently quantum-mechanical effect of nonlocal dispersion compensation for QKD in this way. We experimentally show an increase in key rate from 6.1 to 228.3 bits/s over 6.46 km of telecom fiber. Our approach is extendable to arbitrary fiber lengths and dispersion values, resulting in substantially increased key rates and even enabling QKD in the first place where strong dispersion would otherwise frustrate key extraction at all. △ Less

Submitted 12 April, 2021; v1 submitted 1 July, 2020; originally announced July 2020.

Comments: 14 pages, 4 figures. v2: Corrected typos, slightly changed chapter structure, rephrasing of abstract and introduction. v3: Rephrasings, citations added, Appendix chapter added

Journal ref: Quantum Sci. Technol. 6, 025017 (2021)

SARS-CoV-2, a Threat to Privacy?

Authors: Tim Daubenschuetz, Oksana Kulyk, Stephan Neumann, Isabella Hinterleitner, Paula Ramos Delgado, Carmen Hoffmann, Florian Scheible

Abstract: The global SARS-CoV-2 pandemic is currently putting a massive strain on the world's critical infrastructures. With healthcare systems and internet service providers already struggling to provide reliable service, some operators may, intentionally or unintentionally, lever out privacy-protecting measures to increase their system's efficiency in fighting the virus. Moreover, though it may seem all e… ▽ More The global SARS-CoV-2 pandemic is currently putting a massive strain on the world's critical infrastructures. With healthcare systems and internet service providers already struggling to provide reliable service, some operators may, intentionally or unintentionally, lever out privacy-protecting measures to increase their system's efficiency in fighting the virus. Moreover, though it may seem all encouraging to see the effectiveness of authoritarian states in battling the crisis, we, the authors of this paper, would like to raise the community's awareness towards developing more effective means in battling the crisis without the need to limit fundamental human rights. To analyze the current situation, we are discussing and evaluating the steps corporations and governments are taking to condemn the virus by applying established privacy research. △ Less

Submitted 4 July, 2022; v1 submitted 21 April, 2020; originally announced April 2020.

Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles

Authors: Monika Henzinger, Stefan Neumann, Andreas Wiese

Abstract: Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that… ▽ More Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect. We present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in $d$ dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worst-case update times that are polylogarithmic for constant $d$ and $ε> 0$, assuming that the coordinates of all input objects are in $[0, N]^d$ and each of their edges has length at least 1. We obtain the following results: $\bullet$ For weighted intervals, we maintain a $(1+ε)$-approximate solution. $\bullet$ For $d$-dimensional hypercubes we maintain a $(1+ε)2^{d}$-approximate solution in the unweighted case and a $O(2^{d})$-approximate solution in the weighted case. Also, we show that for maintaining an unweighted $(1+ε)$-approximate solution one needs polynomial update time for $d\ge2$ if the ETH holds. $\bullet$ For weighted $d$-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio $(1+ε)\log^{d-1}N$. △ Less

Submitted 5 March, 2020; originally announced March 2020.

Comments: The conference version of this paper will appear at the Symposium on Computational Geometry (SoCG) 2020

Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity

Authors: Monika Henzinger, Stefan Neumann, Andreas Wiese

Abstract: Graph coloring is a fundamental problem in computer science. We study the fully dynamic version of the problem in which the graph is undergoing edge insertions and deletions and we wish to maintain a vertex-coloring with small update time after each insertion and deletion. We show how to maintain an $O(α\lg n)$-coloring with polylogarithmic update time, where $n$ is the number of vertices in the… ▽ More Graph coloring is a fundamental problem in computer science. We study the fully dynamic version of the problem in which the graph is undergoing edge insertions and deletions and we wish to maintain a vertex-coloring with small update time after each insertion and deletion. We show how to maintain an $O(α\lg n)$-coloring with polylogarithmic update time, where $n$ is the number of vertices in the graph and $α$ is the current arboricity of the graph. This improves upon a result by Solomon and Wein (ESA'18) who maintained an $O(α_{\max}\lg^2 n)$-coloring, where $α_{\max}$ is the maximum arboricity of the graph over all updates. Furthermore, motivated by a lower bound by Barba et al. (Algorithmica'19), we initiate the study of implicit dynamic colorings. Barba et al. showed that dynamic algorithms with polylogarithmic update time cannot maintain an $f(α)$-coloring for any function $f$ when the vertex colors are stored explicitly, i.e., for each vertex the color is stored explicitly in the memory. Previously, all dynamic algorithms maintained explicit colorings. Therefore, we propose to study implicit colorings, i.e., the data structure only needs to offer an efficient query procedure to return the color of a vertex (instead of storing its color explicitly). We provide an algorithm which breaks the lower bound and maintains an implicit $2^{O(α)}$-coloring with polylogarithmic update time. In particular, this yields the first dynamic $O(1)$-coloring for graphs with constant arboricity such as planar graphs or graphs with bounded tree-width, which is impossible using explicit colorings. We also show how to dynamically maintain a partition of the graph's edges into $O(α)$ forests with polylogarithmic update time. We believe this data structure is of independent interest and might have more applications in the future. △ Less

Submitted 24 February, 2020; originally announced February 2020.

A trusted-node-free eight-user metropolitan quantum communication network

Authors: Siddarth Koduru Joshi, Djeylan Aktas, Sören Wengerowsky, Martin Lončarić, Sebastian Philipp Neumann, Bo Liu, Thomas Scheidl, Guillermo Currás-Lorenzo, Željko Samec, Laurent Kling, Alex Qiu, Mohsen Razavi, Mario Stipčević, John G. Rarity, Rupert Ursin

Abstract: Quantum communication is rapidly gaining popularity due to its high security and technological maturity. However, most implementations are limited to just two communicating parties (users). Quantum communication networks aim to connect a multitude of users. Here we present a fully connected quantum communication network on a city wide scale without active switching or trusted nodes. We demonstrate… ▽ More Quantum communication is rapidly gaining popularity due to its high security and technological maturity. However, most implementations are limited to just two communicating parties (users). Quantum communication networks aim to connect a multitude of users. Here we present a fully connected quantum communication network on a city wide scale without active switching or trusted nodes. We demonstrate simultaneous and secure connections between all 28 pairings of 8 users. Our novel network topology is easily scalable to many users, allows traffic management features and minimises the infrastructure as well as the user hardware needed. △ Less

Submitted 11 September, 2020; v1 submitted 18 July, 2019; originally announced July 2019.

Comments: 16 pages, 9 figures, 3 tables. Corrected typos, updated references

Journal ref: Science Advances 6, no. 36 (2020): eaba0959

Efficient Distributed Workload (Re-)Embedding

Authors: Monika Henzinger, Stefan Neumann, Stefan Schmid

Abstract: Modern networked systems are increasingly reconfigurable, enabling demand-aware infrastructures whose resources can be adjusted according to the workload they currently serve. Such dynamic adjustments can be exploited to improve network utilization and hence performance, by moving frequently interacting communication partners closer, e.g., collocating them in the same server or datacenter. However… ▽ More Modern networked systems are increasingly reconfigurable, enabling demand-aware infrastructures whose resources can be adjusted according to the workload they currently serve. Such dynamic adjustments can be exploited to improve network utilization and hence performance, by moving frequently interacting communication partners closer, e.g., collocating them in the same server or datacenter. However, dynamically changing the embedding of workloads is algorithmically challenging: communication patterns are often not known ahead of time, but must be learned. During the learning process, overheads related to unnecessary moves (i.e., re-embeddings) should be minimized. This paper studies a fundamental model which captures the tradeoff between the benefits and costs of dynamically collocating communication partners on $\ell$ servers, in an online manner. Our main contribution is a distributed online algorithm which is asymptotically almost optimal, i.e., almost matches the lower bound (also derived in this paper) on the competitive ratio of any (distributed or centralized) online algorithm. As an application, we show that our algorithm can be used to solve a distributed union find problem in which the sets are stored across multiple servers. △ Less

Submitted 10 April, 2019; originally announced April 2019.

Comments: To appear at SIGMETRICS'19

New Amortized Cell-Probe Lower Bounds for Dynamic Problems

Authors: Sayan Bhattacharya, Monika Henzinger, Stefan Neumann

Abstract: We build upon the recent papers by Weinstein and Yu (FOCS'16), Larsen (FOCS'12), and Clifford et al. (FOCS'15) to present a general framework that gives amortized lower bounds on the update and query times of dynamic data structures. Using our framework, we present two concrete results. (1) For the dynamic polynomial evaluation problem, where the polynomial is defined over a finite field of size… ▽ More We build upon the recent papers by Weinstein and Yu (FOCS'16), Larsen (FOCS'12), and Clifford et al. (FOCS'15) to present a general framework that gives amortized lower bounds on the update and query times of dynamic data structures. Using our framework, we present two concrete results. (1) For the dynamic polynomial evaluation problem, where the polynomial is defined over a finite field of size $n^{1+Ω(1)}$ and has degree $n$, any dynamic data structure must either have an amortized update time of $Ω((\lg n/\lg \lg n)^2)$ or an amortized query time of $Ω((\lg n/\lg \lg n)^2)$. (2) For the dynamic online matrix vector multiplication problem, where we get an $n \times n$ matrix whose entires are drawn from a finite field of size $n^{Θ(1)}$, any dynamic data structure must either have an amortized update time of $Ω((\lg n/\lg \lg n)^2)$ or an amortized query time of $Ω(n \cdot (\lg n/\lg \lg n)^2)$. For these two problems, the previous works by Larsen (FOCS'12) and Clifford et al. (FOCS'15) gave the same lower bounds, but only for worst case update and query times. Our bounds match the highest unconditional lower bounds known till date for any dynamic problem in the cell-probe model. △ Less

Submitted 6 February, 2019; originally announced February 2019.

Greedy Actor-Critic: A New Conditional Cross-Entropy Method for Policy Improvement

Authors: Samuel Neumann, Sungsu Lim, Ajin Joseph, Yangchen Pan, Adam White, Martha White

Abstract: Many policy gradient methods are variants of Actor-Critic (AC), where a value function (critic) is learned to facilitate updating the parameterized policy (actor). The update to the actor involves a log-likelihood update weighted by the action-values, with the addition of entropy regularization for soft variants. In this work, we explore an alternative update for the actor, based on an extension o… ▽ More Many policy gradient methods are variants of Actor-Critic (AC), where a value function (critic) is learned to facilitate updating the parameterized policy (actor). The update to the actor involves a log-likelihood update weighted by the action-values, with the addition of entropy regularization for soft variants. In this work, we explore an alternative update for the actor, based on an extension of the cross entropy method (CEM) to condition on inputs (states). The idea is to start with a broader policy and slowly concentrate around maximal actions, using a maximum likelihood update towards actions in the top percentile per state. The speed of this concentration is controlled by a proposal policy, that concentrates at a slower rate than the actor. We first provide a policy improvement result in an idealized setting, and then prove that our conditional CEM (CCEM) strategy tracks a CEM update per state, even with changing action-values. We empirically show that our Greedy AC algorithm, that uses CCEM for the actor update, performs better than Soft Actor-Critic and is much less sensitive to entropy-regularization. △ Less

Submitted 28 February, 2023; v1 submitted 22 October, 2018; originally announced October 2018.

Comments: 27 pages, 8 figures

Model-Driven Architectural Monitoring and Adaptation for Autonomic Systems

Authors: Thomas Vogel, Stefan Neumann, Stephan Hildebrandt, Holger Giese, Basil Becker

Abstract: Architectural monitoring and adaptation allows self-management capabilities of autonomic systems to realize more powerful adaptation steps, which observe and adjust not only parameters but also the software architecture. However, monitoring as well as adaptation of the architecture of a running system in addition to the parameters are considerably more complex and only rather limited and costly so… ▽ More Architectural monitoring and adaptation allows self-management capabilities of autonomic systems to realize more powerful adaptation steps, which observe and adjust not only parameters but also the software architecture. However, monitoring as well as adaptation of the architecture of a running system in addition to the parameters are considerably more complex and only rather limited and costly solutions are available today. In this paper we propose a model-driven approach to ease the development of architectural monitoring and adaptation for autonomic systems. Using meta models and model transformation techniques, we were able to realize an incremental synchronization between the run-time system and models for different self-management activities. The synchronization might be triggered when needed and therefore the activities can operate concurrently. △ Less

Submitted 17 May, 2018; originally announced May 2018.

Journal ref: In: International Conference on Autonomic Computing and Communications. ICAC '09. ACM, 2009, pp. 67-68

Quantum Communication Uplink to a 3U CubeSat: Feasibility & Design

Authors: Sebastian Philipp Neumann, Siddarth Koduru Joshi, Matthias Fink, Thomas Scheidl, Roland Blach, Carsten Scharlemann, Sameh Abouagaga, Daanish Bambery, Erik Kerstel, Mathieu Barthelemy, Rupert Ursin

Abstract: Satellites are the efficient way to achieve global scale quantum communication (Q.Com) because unavoidable losses restrict fiber based Q.Com to a few hundred kilometers. We demonstrate the feasibility of establishing a Q.Com uplink with a tiny 3U CubeSat (measuring just 10X10X32 cm^3 ) using commercial off-the-shelf components, the majority of which have space heritage. We demonstrate how to lever… ▽ More Satellites are the efficient way to achieve global scale quantum communication (Q.Com) because unavoidable losses restrict fiber based Q.Com to a few hundred kilometers. We demonstrate the feasibility of establishing a Q.Com uplink with a tiny 3U CubeSat (measuring just 10X10X32 cm^3 ) using commercial off-the-shelf components, the majority of which have space heritage. We demonstrate how to leverage the latest advancements in nano-satellite body-pointing to show that our 4kg CubeSat can provide performance comparable to much larger 600kg satellite missions. A comprehensive link budget and simulation was performed to calculate the secure key rates. We discuss design choices and trade-offs to maximize the key rate while minimizing the cost and development needed. Our detailed design and feasibility study can be readily used as a template for global scale Q.Com. △ Less

Submitted 12 December, 2017; v1 submitted 9 November, 2017; originally announced November 2017.

Comments: 24 pages, 9 figures, 2 tables. Fixed tables and figures

Journal ref: EPJ Quantum Technol. (2018) 5: 4

Reductions for Frequency-Based Data Mining Problems

Authors: Stefan Neumann, Pauli Miettinen

Abstract: Studying the computational complexity of problems is one of the - if not the - fundamental questions in computer science. Yet, surprisingly little is known about the computational complexity of many central problems in data mining. In this paper we study frequency-based problems and propose a new type of reduction that allows us to compare the complexities of the maximal frequent pattern mining pr… ▽ More Studying the computational complexity of problems is one of the - if not the - fundamental questions in computer science. Yet, surprisingly little is known about the computational complexity of many central problems in data mining. In this paper we study frequency-based problems and propose a new type of reduction that allows us to compare the complexities of the maximal frequent pattern mining problems in different domains (e.g. graphs or sequences). Our results extend those of Kimelfeld and Kolaitis [ACM TODS, 2014] to a broader range of data mining problems. Our results show that, by allowing constraints in the pattern space, the complexities of many maximal frequent pattern mining problems collapse. These problems include maximal frequent subgraphs in labelled graphs, maximal frequent itemsets, and maximal frequent subsequences with no repetitions. In addition to theoretical interest, our results might yield more efficient algorithms for the studied problems. △ Less

Submitted 4 September, 2017; originally announced September 2017.

Comments: This is an extended version of a paper of the same title to appear in the Proceedings of the 17th IEEE International Conference on Data Mining (ICDM'17)

Conditional Hardness for Sensitivity Problems

Authors: Monika Henzinger, Andrea Lincoln, Stefan Neumann, Virginia Vassilevska Williams

Abstract: In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allows to apply batch updates of small size to the original input data. The sensitivity model is particularly appealing since recent strong conditional lower bounds ruled out fast algorithms for many dynamic problems, such as… ▽ More In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allows to apply batch updates of small size to the original input data. The sensitivity model is particularly appealing since recent strong conditional lower bounds ruled out fast algorithms for many dynamic problems, such as shortest paths, reachability, or subgraph connectivity. In this paper we prove conditional lower bounds for sensitivity problems. For example, we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial algorithms cannot compute the (4/3 - ε)-approximate diameter of an undirected unweighted dense graph with truly subcubic preprocessing time and truly subquadratic update/query time. This result is surprising since in the static setting it is not clear whether a reduction from BMM to diameter is possible. We further show under the BMM conjecture that many problems, such as reachability or approximate shortest paths, cannot be solved faster than by recomputation from scratch even after only one or two edge insertions. We give more lower bounds under the Strong Exponential Time Hypothesis and the All Pairs Shortest Paths Conjecture. Many of our lower bounds also hold for static oracle data structures where no sensitivity is required. Finally, we give the first algorithm for the (1 + ε)-approximate radius, diameter, and eccentricity problems in directed or undirected unweighted graphs in case of single edges failures. The algorithm has a truly subcubic running time for graphs with a truly subquadratic number of edges; it is tight w.r.t. the conditional lower bounds we obtain. △ Less

Submitted 5 March, 2017; originally announced March 2017.

Comments: Appeared in ITCS'17

ACM Class: F.2.2

Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning

Authors: Monika Henzinger, Stefan Neumann

Abstract: During the last 10 years it has become popular to study dynamic graph problems in a emergency planning or sensitivity setting: Instead of considering the general fully dynamic problem, we only have to process a single batch update of size $d$; after the update we have to answer queries. In this paper, we consider the dynamic subgraph connectivity problem with sensitivity $d$: We are given a grap… ▽ More During the last 10 years it has become popular to study dynamic graph problems in a emergency planning or sensitivity setting: Instead of considering the general fully dynamic problem, we only have to process a single batch update of size $d$; after the update we have to answer queries. In this paper, we consider the dynamic subgraph connectivity problem with sensitivity $d$: We are given a graph of which some vertices are activated and some are deactivated. After that we get a single update in which the states of up to d vertices are changed. Then we get a sequence of connectivity queries in the subgraph of activated vertices. We present the first fully dynamic algorithm for this problem which has an update and query time only slightly worse than the best decremental algorithm. In addition, we present the first incremental algorithm which is tight with respect to the best known conditional lower bound; moreover, the algorithm is simple and we believe it is implementable and efficient in practice. △ Less

Submitted 16 November, 2016; originally announced November 2016.

What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank

Authors: Stefan Neumann, Rainer Gemulla, Pauli Miettinen

Abstract: When factorizing binary matrices, we often have to make a choice between using expensive combinatorial methods that retain the discrete nature of the data and using continuous methods that can be more efficient but destroy the discrete structure. Alternatively, we can first compute a continuous factorization and subsequently apply a rounding procedure to obtain a discrete representation. But what… ▽ More When factorizing binary matrices, we often have to make a choice between using expensive combinatorial methods that retain the discrete nature of the data and using continuous methods that can be more efficient but destroy the discrete structure. Alternatively, we can first compute a continuous factorization and subsequently apply a rounding procedure to obtain a discrete representation. But what will we gain by rounding? Will this yield lower reconstruction errors? Is it easy to find a low-rank matrix that rounds to a given binary matrix? Does it matter which threshold we use for rounding? Does it matter if we allow for only non-negative factorizations? In this paper, we approach these and further questions by presenting and studying the concept of rounding rank. We show that rounding rank is related to linear classification, dimensionality reduction, and nested matrices. We also report on an extensive experimental study that compares different algorithms for finding good factorizations under the rounding rank model. △ Less

Submitted 6 October, 2016; v1 submitted 16 September, 2016; originally announced September 2016.

Comments: 14 pages, 7 figures. For associated source code, see http://dws.informatik.uni-mannheim.de/en/resources/software/rounding-rank/ . This is an extended version of a paper accepted for publication in the proceedings of the 2016 IEEE International Conference on Data Mining (ICDM)

This House Proves that Debating is Harder than Soccer

Authors: Stefan Neumann, Andreas Wiese

Abstract: During the last twenty years, a lot of research was conducted on the sport elimination problem: Given a sports league and its remaining matches, we have to decide whether a given team can still possibly win the competition, i.e., place first in the league at the end. Previously, the computational complexity of this problem was investigated only for games with two participating teams per game. In t… ▽ More During the last twenty years, a lot of research was conducted on the sport elimination problem: Given a sports league and its remaining matches, we have to decide whether a given team can still possibly win the competition, i.e., place first in the league at the end. Previously, the computational complexity of this problem was investigated only for games with two participating teams per game. In this paper we consider Debating Tournaments and Debating Leagues in the British Parliamentary format, where four teams are participating in each game. We prove that it is NP-hard to decide whether a given team can win a Debating League, even if at most two matches are remaining for each team. This contrasts settings like football where two teams play in each game since there this case is still polynomial time solvable. We prove our result even for a fictitious restricted setting with only three teams per game. On the other hand, for the common setting of Debating Tournaments we show that this problem is fixed parameter tractable if the parameter is the number of remaining rounds $k$. This also holds for the practically very important question of whether a team can still qualify for the knock-out phase of the tournament and the combined parameter $k + b$ where $b$ denotes the threshold rank for qualifying. Finally, we show that the latter problem is polynomial time solvable for any constant $k$ and arbitrary values $b$ that are part of the input. △ Less

Submitted 10 May, 2016; originally announced May 2016.

Comments: 18 pages, to appear at FUN 2016

ACM Class: F.2.2

Predicting chemical environments of bacteria from receptor signaling

Authors: Diana Clausznitzer, Gabriele Micali, Silke Neumann, Victor Sourjik, Robert G. Endres

Abstract: Sensory systems have evolved to respond to input stimuli of certain statistical properties, and to reliably transmit this information through biochemical pathways. Hence, for an experimentally well-characterized sensory system, one ought to be able to extract valuable information about the statistics of the stimuli. Based on dose-response curves from in vivo fluorescence resonance energy transfer… ▽ More Sensory systems have evolved to respond to input stimuli of certain statistical properties, and to reliably transmit this information through biochemical pathways. Hence, for an experimentally well-characterized sensory system, one ought to be able to extract valuable information about the statistics of the stimuli. Based on dose-response curves from in vivo fluorescence resonance energy transfer (FRET) experiments of the bacterial chemotaxis sensory system, we predict the chemical gradients chemotactic Escherichia coli cells typically encounter in their natural environment. To predict average gradients cells experience, we revaluate the phenomenological Weber's law and its generalizations to the Weber-Fechner law and fold-change detection. To obtain full distributions of gradients we use information theory and simulations, considering limitations of information transmission from both cell-external and internal noise. We identify broad distributions of exponential gradients, which lead to log-normal stimuli and maximal drift velocity. Our results thus provide a first step towards deciphering the chemical nature of complex, experimentally inaccessible cellular microenvironments, such as the human intestine. △ Less

Submitted 27 October, 2014; originally announced October 2014.

Comments: DG and GM contributed equally to this work

Journal ref: PLoS Comput Biol 10(10): e1003870 (2014)

Supervised Penalized Canonical Correlation Analysis

Authors: Andrea Thum, Susann Mönchgesang, Lore Westphal, Tilo Lübken, Sabine Rosahl, Steffen Neumann, Stefan Posch

Abstract: The canonical correlation analysis (CCA) is commonly used to analyze data sets with paired data, e.g. measurements of gene expression and metabolomic intensities of the same experiments. This allows to find interesting relationships between the data sets, e.g. they can be assigned to biological processes. However, it can be difficult to interpret the processes and often the relationships observed… ▽ More The canonical correlation analysis (CCA) is commonly used to analyze data sets with paired data, e.g. measurements of gene expression and metabolomic intensities of the same experiments. This allows to find interesting relationships between the data sets, e.g. they can be assigned to biological processes. However, it can be difficult to interpret the processes and often the relationships observed are not related to the experimental design but to some unknown parameters. Here we present an extension of the penalized CCA, the supervised penalized approach (spCCA), where the experimental design is used as a third data set and the correlation of the biological data sets with the design data set is maximized to find interpretable and meaningful canonical variables. The spCCA was successfully tested on a data set of Arabidopsis thaliana with gene expression and metabolite intensity measurements and resulted in eight significant canonical variables and their interpretation. We provide an R-package under the GPL license. △ Less

Submitted 7 May, 2014; originally announced May 2014.

Counting Zariski chambers on Del Pezzo surfaces

Authors: Thomas Bauer, Michael Funke, Sebastian Neumann

Abstract: Zariski chambers provide a natural decomposition of the big cone of an algebraic surface into rational locally polyhedral subcones that are interesting from the point of view of linear series. In the present paper we present an algorithm that allows to effectively determine Zariski chambers when the negative curves on the surface are known. We show how the algorithm can be used to compute the nu… ▽ More Zariski chambers provide a natural decomposition of the big cone of an algebraic surface into rational locally polyhedral subcones that are interesting from the point of view of linear series. In the present paper we present an algorithm that allows to effectively determine Zariski chambers when the negative curves on the surface are known. We show how the algorithm can be used to compute the number of chambers on Del Pezzo surfaces. △ Less

Submitted 4 December, 2009; originally announced December 2009.

MSC Class: 14C20; 14N10; 14Q10

Rationally connected foliations on surfaces

Authors: Sebastian Neumann

Abstract: In this short note we study foliations with rationally connected leaves on surfaces. Our main result is that on surfaces there exists a polarisation such that the Harder-Narasimhan filtration of the tangent bundle with respect to this polarisation yields the maximal rationally quotient of the surface. In this short note we study foliations with rationally connected leaves on surfaces. Our main result is that on surfaces there exists a polarisation such that the Harder-Narasimhan filtration of the tangent bundle with respect to this polarisation yields the maximal rationally quotient of the surface. △ Less

Submitted 20 November, 2008; originally announced November 2008.

Comments: 8 pages