Search

Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient. Other properties like a giant component, the small world phenomena and others follow. This motivates the design of simple algorithms for hyperbolic random graphs. In this paper we consider threshold hyperbolic random graphs (HRGs). Greedy heuristics are commonly used in practice as they deliver a good approximations to the optimal solution even though their theoretical analysis would suggest otherwise. A typical example for HRGs are degeneracy-based greedy algorithms [Bl\"asius, Fischbeck; Transactions of Algorithms '24]. In an attempt to bridge this theory-practice gap we characterise the parameter of degeneracy yielding a simple approximation algorithm for colouring HRGs. The approximation ratio of our algorithm ranges from $(2/\sqrt{3})$ to $4/3$ depending on the power-law exponent of the model. We complement our findings for the degeneracy with new insights on the clique number of hyperbolic random graphs. We show that degeneracy and clique number are substantially different and derive an improved upper bound on the clique number. Additionally, we show that the core of HRGs does not constitute the largest clique. Lastly we demonstrate that the degeneracy of the closely related standard model of geometric inhomogeneous random graphs behaves inherently different compared to the one of hyperbolic random graphs.

High-dimensional Bayesian optimization (BO) tasks such as molecular design often require 10,000 function evaluations before obtaining meaningful results. While methods like sparse variational Gaussian processes (SVGPs) reduce computational requirements in these settings, the underlying approximations result in suboptimal data acquisitions that slow the progress of optimization. In this paper we modify SVGPs to better align with the goals of BO: targeting informed data acquisition rather than global posterior fidelity. Using the framework of utility-calibrated variational inference, we unify GP approximation and data acquisition into a joint optimization problem, thereby ensuring optimal decisions under a limited computational budget. Our approach can be used with any decision-theoretic acquisition function and is compatible with trust region methods like TuRBO. We derive efficient joint objectives for the expected improvement and knowledge gradient acquisition functions in both the standard and batch BO settings. Our approach outperforms standard SVGPs on high-dimensional benchmark tasks in control and molecular design.

We consider the problem of coloring graphs of maximum degree $\Delta$ with $\Delta$ colors in the distributed setting with limited bandwidth. Specifically, we give a $\mathsf{poly}\log\log n$-round randomized algorithm in the CONGEST model. This is close to the lower bound of $\Omega(\log \log n)$ rounds from [Brandt et al., STOC '16], which holds also in the more powerful LOCAL model. The core of our algorithm is a reduction to several special instances of the constructive Lov\'asz local lemma (LLL) and the $deg+1$-list coloring problem.

The constructive Lov\'{a}sz Local Lemma has become a central tool for designing efficient distributed algorithms. While it has been extensively studied in the classic LOCAL model that uses unlimited bandwidth, much less is known in the bandwidth-restricted CONGEST model. In this paper, we present bandwidth- and time-efficient algorithms for various subclasses of LLL problems, including a large class of subgraph sampling problems that are naturally formulated as LLLs. Lastly, we use our LLLs to design efficient CONGEST algorithms for coloring sparse and triangle-free graphs with few colors. These coloring algorithms are exponentially faster than previous LOCAL model algorithms.

Over the years, various approaches have been employed to enhance the productivity of knowledge workers, from addressing psychological well-being to the development of personal knowledge assistants. A significant challenge in this research area has been the absence of a comprehensive, publicly accessible dataset that mirrors real-world knowledge work. Although a handful of datasets exist, many are restricted in access or lack vital information dimensions, complicating meaningful comparison and benchmarking in the domain. This paper presents RLKWiC, a novel dataset of Real-Life Knowledge Work in Context, derived from monitoring the computer interactions of eight participants over a span of two months. As the first publicly available dataset offering a wealth of essential information dimensions (such as explicated contexts, textual contents, and semantics), RLKWiC seeks to address the research gap in the personal information management domain, providing valuable insights for modeling user behavior., Comment: Accepted and presented at the 10th International Conference on Information Management (ICIM2024), will be published in Springer CCIS series Conference Proceedings (Electronic ISSN: 1865-0937; Print ISSN: 1865-0929)

In anticipation of forthcoming data releases of current and future spectroscopic surveys, we present the validation tests and analysis of systematic effects within \texttt{velocileptors} modeling pipeline when fitting mock data from the \texttt{AbacusSummit} N-body simulations. We compare the constraints obtained from parameter compression methods to the direct fitting (Full-Modeling) approaches of modeling the galaxy power spectra, and show that the ShapeFit extension to the traditional template method is consistent with the Full-Modeling method within the standard $\Lambda$CDM parameter space. We show the dependence on scale cuts when fitting the different redshift bins using the ShapeFit and Full-Modeling methods. We test the ability to jointly fit data from multiple redshift bins as well as joint analysis of the pre-reconstruction power spectrum with the post-reconstruction BAO correlation function signal. We further demonstrate the behavior of the model when opening up the parameter space beyond $\Lambda$CDM and also when combining likelihoods with external datasets, namely the Planck CMB priors. Finally, we describe different parametrization options for the galaxy bias, counterterm, and stochastic parameters, and employ the halo model in order to physically motivate suitable priors that are necessary to ensure the stability of the perturbation theory., Comment: 56 pages, 23 figures. Supporting publication of DESI 2024 V: Analysis of the full shape of two-point clustering statistics from galaxies and quasars

DESI aims to provide one of the tightest constraints on cosmological parameters by analysing the clustering of more than thirty million galaxies. However, obtaining such constraints requires special care in validating the methodology and efforts to reduce the computational time required through data compression and emulation techniques. In this work, we perform a rigorous validation of the PyBird power spectrum modelling code with both a traditional emulated Full-Modelling approach and the model-independent ShapeFit compression approach. By using cubic box simulations that accurately reproduce the clustering and precision of the DESI survey, we find that the cosmological constraints from ShapeFit and Full-Modelling are consistent with each other at the $\sim0.5\sigma$ level for the $\Lambda$CDM model. Both ShapeFit and Full-Modelling are also consistent with the true $\Lambda$CDM simulation cosmology down to a scale of $k_{\mathrm{max}} = 0.20 h\mathrm{Mpc}^{-1}$ even after including the hexadecapole. For extended models such as the wCDM and the oCDM models, we find that including the hexadecapole can significantly improve the constraints and reduce the modelling errors with the same $k_{\mathrm{max}}$. While their discrepancies between the constraints from ShapeFit and Full-Modelling are more significant than $\Lambda$CDM, they remain consistent within $0.7\sigma$. Lastly, we also show that the constraints on cosmological parameters with the correlation function evaluated from PyBird down to $s_{\mathrm{min}} = 30 h^{-1} \mathrm{Mpc}$ are unbiased and consistent with the constraints from the power spectrum., Comment: Supporting publication of DESI 2024 V: Analysis of the full shape of two-point clustering statistics from galaxies and quasars (In prep). 51 pages, 21 figures, and 12 tables. 2nd revised version for JCAP

In preparation for the next generation of galaxy redshift surveys, and in particular the year-one data release from the Dark Energy Spectroscopic Instrument (DESI), we investigate the consistency of a variety of effective field theory models that describe the galaxy-galaxy power spectra in redshift space into the quasi-linear regime using 1-loop perturbation theory. These models are employed in the pipelines \texttt{velocileptors}, \texttt{PyBird}, and \texttt{Folps$\nu$}. While these models have been validated independently, a detailed comparison with consistent choices has not been attempted. After briefly discussing the theoretical differences between the models we describe how to provide a more apples-to-apples comparison between them. We present the results of fitting mock spectra from the \texttt{AbacusSummit} suite of N-body simulations provided in three redshift bins to mimic the types of dark time tracers targeted by the DESI survey. We show that the theories behave similarly and give consistent constraints in both the forward-modeling and ShapeFit compressed fitting approaches. We additionally generate (noiseless) synthetic data from each pipeline to be fit by the others, varying the scale cuts in order to show that the models agree within the range of scales for which we expect 1-loop perturbation theory to be applicable. This work lays the foundation of Full-Shape analysis with DESI Y1 galaxy samples where in the tests we performed, we found no systematic error associated with the modeling of the galaxy redshift space power spectrum for this volume., Comment: 33 pages, 12 figures. Supporting publication of DESI 2024 V: Analysis of the full shape of two-point clustering statistics from galaxies and quasars

The Dark Energy Spectroscopic Instrument (DESI) will provide unprecedented information about the large-scale structure of our Universe. In this work, we study the robustness of the theoretical modelling of the power spectrum of FOLPS, a novel effective field theory-based package for evaluating the redshift space power spectrum in the presence of massive neutrinos. We perform this validation by fitting the AbacusSummit high-accuracy $N$-body simulations for Luminous Red Galaxies, Emission Line Galaxies and Quasar tracers, calibrated to describe DESI observations. We quantify the potential systematic error budget of FOLPS, finding that the modelling errors are fully sub-dominant for the DESI statistical precision within the studied range of scales. Additionally, we study two complementary approaches to fit and analyse the power spectrum data, one based on direct Full-Modelling fits and the other on the ShapeFit compression variables, both resulting in very good agreement in precision and accuracy. In each of these approaches, we study a set of potential systematic errors induced by several assumptions, such as the choice of template cosmology, the effect of prior choice in the nuisance parameters of the model, or the range of scales used in the analysis. Furthermore, we show how opening up the parameter space beyond the vanilla $\Lambda$CDM model affects the DESI observables. These studies include the addition of massive neutrinos, spatial curvature, and dark energy equation of state. We also examine how relaxing the usual Cosmic Microwave Background and Big Bang Nucleosynthesis priors on the primordial spectral index and the baryonic matter abundance, respectively, impacts the inference on the rest of the parameters of interest. This paper pathways towards performing a robust and reliable analysis of the shape of the power spectrum of DESI galaxy and quasar clustering using FOLPS., Comment: Supporting publication of DESI 2024 VII: Cosmological constraints from full-shape analyses of the two-point clustering statistics measurements, in preparation (2024)

In the contemporary era of high-precision spectroscopic surveys, led by projects like DESI, there is an increasing demand for optimizing the extraction of cosmological information from clustering data. This work conducts a thorough comparison of various methodologies for modeling the full shape of the two-point statistics in configuration space. We investigate the performance of both direct fits (Full-Modeling) and the parameter compression approaches (ShapeFit and Standard). We utilize the ABACUS-SUMMIT simulations, tailored to exceed DESI's precision requirements. Particularly, we fit the two-point statistics of three distinct tracers (LRG, ELG, and QSO), by employing a Gaussian Streaming Model in tandem with Convolution Lagrangian Perturbation Theory and Effective Field Theory. We explore methodological setup variations, including the range of scales, the set of galaxy bias parameters, the inclusion of the hexadecapole, as well as model extensions encompassing varying $n_s$ and allowing for $w_0w_a$CDM dark energy model. Throughout these varied explorations, while precision levels fluctuate and certain configurations exhibit tighter parameter constraints, our pipeline consistently recovers the parameter values of the mocks within $1\sigma$ in all cases for a 1-year DESI volume. Additionally, we compare the performance of configuration space analysis with its Fourier space counterpart using three models: PyBird, FOLPS and velocileptors, presented in companion papers. We find good agreement with the results from all these models., Comment: Supporting publication of DESI 2024 KP5

We present cosmological results from the measurement of baryon acoustic oscillations (BAO) in galaxy, quasar and Lyman-$\alpha$ forest tracers from the first year of observations from the Dark Energy Spectroscopic Instrument (DESI), to be released in the DESI Data Release 1. DESI BAO provide robust measurements of the transverse comoving distance and Hubble rate, or their combination, relative to the sound horizon, in seven redshift bins from over 6 million extragalactic objects in the redshift range $0.1-1$ and $w_a<0$. This preference is 2.6$\sigma$ for the DESI+CMB combination, and persists or grows when SN~Ia are added in, giving results discrepant with the $\Lambda$CDM model at the $2.5\sigma$, $3.5\sigma$ or $3.9\sigma$ levels for the addition of Pantheon+, Union3, or DES-SN5YR datasets respectively. For the flat $\Lambda$CDM model with the sum of neutrino mass $\sum m_\nu$ free, combining the DESI and CMB data yields an upper limit $\sum m_\nu < 0.072$ $(0.113)$ eV at 95% confidence for a $\sum m_\nu>0$ $(\sum m_\nu>0.059)$ eV prior. These neutrino-mass constraints are substantially relaxed in models beyond $\Lambda$CDM. [Abridged.], Comment: This DESI Collaboration Key Publication is part of the 2024 publication series using the first year of observations (see https://data.desi.lbl.gov/doc/papers). 68 pages, 15 figures. Version accepted for publication in JCAP

We present the measurement of Baryon Acoustic Oscillations (BAO) from the Lyman-$\alpha$ (Ly$\alpha$) forest of high-redshift quasars with the first-year dataset of the Dark Energy Spectroscopic Instrument (DESI). Our analysis uses over $420\,000$ Ly$\alpha$ forest spectra and their correlation with the spatial distribution of more than $700\,000$ quasars. An essential facet of this work is the development of a new analysis methodology on a blinded dataset. We conducted rigorous tests using synthetic data to ensure the reliability of our methodology and findings before unblinding. Additionally, we conducted multiple data splits to assess the consistency of the results and scrutinized various analysis approaches to confirm their robustness. For a given value of the sound horizon ($r_d$), we measure the expansion at $z_{\rm eff}=2.33$ with 2\% precision, $H(z_{\rm eff}) = (239.2 \pm 4.8) (147.09~{\rm Mpc} /r_d)$ km/s/Mpc. Similarly, we present a 2.4\% measurement of the transverse comoving distance to the same redshift, $D_M(z_{\rm eff}) = (5.84 \pm 0.14) (r_d/147.09~{\rm Mpc})$ Gpc. Together with other DESI BAO measurements at lower redshifts, these results are used in a companion paper to constrain cosmological parameters., Comment: This DESI Collaboration Key Publication is part of the 2024 publication series using the first year of observations (see https://data.desi.lbl.gov/doc/papers). Minor changes in v4, version accepted for publication in JCAP

We present the DESI 2024 galaxy and quasar baryon acoustic oscillations (BAO) measurements using over 5.7 million unique galaxy and quasar redshifts in the range 0.1

Classic symmetry-breaking problems on graphs have gained a lot of attention in models of modern parallel computation. The Adaptive Massively Parallel Computation (AMPC) is a model that captures the central challenges in data center computations. Chang et al. [PODC'2019] gave an extremely fast, constant time, algorithm for the $(\Delta + 1)$-coloring problem, where $\Delta$ is the maximum degree of an input graph of $n$ nodes. The algorithm works in the most restrictive low-space setting, where each machine has $n^{\delta}$ local space for a constant $0 < \delta < 1$. In this work, we study the vertex-coloring problem in sparse graphs parameterized by their arboricity $\alpha$, a standard measure for sparsity. We give deterministic algorithms that in constant, or almost constant, time give $\text{poly} ~\alpha$ and $O(\alpha)$-colorings, where $\alpha$ can be arbitrarily smaller than $\Delta$. A strong and standard approach to compute arboricity-dependent colorings is through the Nash-Williams forest decomposition, which gives rise to an (acyclic) orientation of the edges such that each node has a small out-degree. Our main technical contribution is giving efficient deterministic algorithms to compute these orientations and showing how to leverage them to find colorings in low-space AMPC. A key technical challenge is that the color of a node may depend on almost all of the other nodes in the graph and these dependencies cannot be stored on a single machine. Nevertheless, our novel and careful exploration technique yields the orientation, and the arboricity-dependent coloring, with a sublinear number of adaptive queries per node., Comment: ACM Symposium on Principles of Distributed Computing (PODC) 2024

Bayesian Optimization (BO) is a technique for sample-efficient black-box optimization that employs probabilistic models to identify promising input locations for evaluation. When dealing with composite-structured functions, such as f=g o h, evaluating a specific location x yields observations of both the final outcome f(x) = g(h(x)) as well as the intermediate output(s) h(x). Previous research has shown that integrating information from these intermediate outputs can enhance BO performance substantially. However, existing methods struggle if the outputs h(x) are high-dimensional. Many relevant problems fall into this setting, including in the context of generative AI, molecular design, or robotics. To effectively tackle these challenges, we introduce Joint Composite Latent Space Bayesian Optimization (JoCo), a novel framework that jointly trains neural network encoders and probabilistic models to adaptively compress high-dimensional input and output spaces into manageable latent representations. This enables viable BO on these compressed representations, allowing JoCo to outperform other state-of-the-art methods in high-dimensional BO on a wide variety of simulated and real-world problems.

This paper presents a retrospective overview of a decade of research in our department towards self-organizing personal knowledge assistants in evolving corporate memories. Our research is typically inspired by real-world problems and often conducted in interdisciplinary collaborations with research and industry partners. We summarize past experiments and results comprising topics like various ways of knowledge graph construction in corporate and personal settings, Managed Forgetting and (Self-organizing) Context Spaces as a novel approach to Personal Information Management (PIM) and knowledge work support. Past results are complemented by an overview of related work and some of our latest findings not published so far. Last, we give an overview of our related industry use cases including a detailed look into CoMem, a Corporate Memory based on our presented research already in productive use and providing challenges for further research. Many contributions are only first steps in new directions with still a lot of untapped potential, especially with regard to further increasing the automation in PIM and knowledge work support., Comment: 73 pages, 22 figures

We show the first conditionally optimal deterministic algorithm for $3$-coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in $O(\log \log n)$ rounds and uses optimal global space. The best previous algorithm requires $4$ colors [Ghaffari, Grunau, Jin, DISC'20] and is randomized, while our algorithm are inherently deterministic. Our main technical contribution is an $O(\log \log n)$-round algorithm to compute a partition of the forest into $O(\log n)$ ordered layers such that every node has at most two neighbors in the same or higher layers. Similar decompositions are often used in the area and we believe that this result is of independent interest. Our results also immediately yield conditionally optimal deterministic algorithms for maximal independent set and maximal matching for forests, matching the state of the art [Giliberti, Fischer, Grunau, SPAA'23]. In contrast to their solution, our algorithms are not based on derandomization, and are arguably simpler., Comment: 37th International Symposium on Distributed Computing (DISC 2023)

Inverse protein folding -- the task of predicting a protein sequence from its backbone atom coordinates -- has surfaced as an important problem in the "top down", de novo design of proteins. Contemporary approaches have cast this problem as a conditional generative modelling problem, where a large generative model over protein sequences is conditioned on the backbone. While these generative models very rapidly produce promising sequences, independent draws from generative models may fail to produce sequences that reliably fold to the correct backbone. Furthermore, it is challenging to adapt pure generative approaches to other settings, e.g., when constraints exist. In this paper, we cast the problem of improving generated inverse folds as an optimization problem that we solve using recent advances in "deep" or "latent space" Bayesian optimization. Our approach consistently produces protein sequences with greatly reduced structural error to the target backbone structure as measured by TM score and RMSD while using fewer computational resources. Additionally, we demonstrate other advantages of an optimization-based approach to the problem, such as the ability to handle constraints.

We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in $O(\log D)$ rounds in the massively parallel computation model (MPC), with $O(n^\delta)$ words of local memory per machine, for any given constant $0 < \delta < 1$. Here $D$ is the diameter of the tree and $n$ is the number of nodes--we emphasize that our running time is independent of $n$. Our algorithm can solve many classical graph optimization problems such as maximum weight independent set, maximum weight matching, minimum weight dominating set, and minimum weight vertex cover. It can also be used to solve many accumulation tasks in which some aggregate information is propagated upwards or downwards in the tree--this includes, for example, computing the sum, minimum, or maximum of the input labels in each subtree, as well as many inference tasks commonly solved with belief propagation. Our algorithm can also solve any locally checkable labeling problem (LCLs) in trees. Our algorithm works for any reasonable representation of the input tree; for example, the tree can be represented as a list of edges or as a string with nested parentheses or tags. The running time of $O(\log D)$ rounds is also known to be necessary, assuming the widely-believed $2$-cycle conjecture. Our algorithm strictly improves on two prior algorithms: (i) Bateni, Behnezhad, Derakhshan, Hajiaghayi, and Mirrokni [ICALP'18] solve problems of these flavors in $O(\log n)$ rounds, while our algorithm is much faster in low-diameter trees. Furthermore, their algorithm also uses randomness, while our algorithm is deterministic. (ii) Balliu, Latypov, Maus, Olivetti, and Uitto [SODA'23] solve only locally checkable labeling problems in $O(\log D)$ rounds, while our algorithm can be applied to a much broader family of problems.

For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended rotation system (ERS) of the drawing is the collection of the rotations of all vertices and crossings. A drawing is simple if each pair of edges has at most one common point. Gioan's Theorem states that for any two simple drawings of the complete graph $K_n$ with the same crossing edge pairs, one drawing can be transformed into the other by a sequence of triangle flips (a.k.a. Reidemeister moves of Type 3). This operation refers to the act of moving one edge of a triangular cell formed by three pairwise crossing edges over the opposite crossing of the cell, via a local transformation. We investigate to what extent Gioan-type theorems can be obtained for wider classes of graphs. A necessary (but in general not sufficient) condition for two drawings of a graph to be transformable into each other by a sequence of triangle flips is that they have the same ERS. As our main result, we show that for the large class of complete multipartite graphs, this necessary condition is in fact also sufficient. We present two different proofs of this result, one of which is shorter, while the other one yields a polynomial time algorithm for which the number of needed triangle flips for graphs on $n$ vertices is bounded by $O(n^{16})$. The latter proof uses a Carath\'eodory-type theorem for simple drawings of complete multipartite graphs, which we believe to be of independent interest. Moreover, we show that our Gioan-type theorem for complete multipartite graphs is essentially tight in the sense that having the same ERS does not remain sufficient when removing or adding very few edges., Comment: Abstract shortened for arxiv. This work (without appendix) is available at the 39th International Symposium on Computational Geometry (SoCG 2023)