Search

The current standard model of cosmology successfully describes a variety of measurements, but the nature of its main ingredients, dark matter and dark energy, remains unknown. Euclid is a medium-class mission in the Cosmic Vision 2015-2025 programme of the European Space Agency (ESA) that will provide high-resolution optical imaging, as well as near-infrared imaging and spectroscopy, over about 14,000 deg^2 of extragalactic sky. In addition to accurate weak lensing and clustering measurements that probe structure formation over half of the age of the Universe, its primary probes for cosmology, these exquisite data will enable a wide range of science. This paper provides a high-level overview of the mission, summarising the survey characteristics, the various data-processing steps, and data products. We also highlight the main science objectives and expected performance., Comment: Accepted for publication in the A&A special issue`Euclid on Sky'

We present new two-party protocols for the Unbalanced Private Set Union (UPSU) problem.Here, the Sender holds a set of data points, and the Receiver holds another (possibly much larger) set, and they would like for the Receiver to learn the union of the two sets and nothing else. Furthermore, the Sender's computational cost, along with the communication complexity, should be smaller when the Sender has a smaller set.While the UPSU problem has numerous applications and has seen considerable recent attention in the literature, our protocols are the first where the Sender's computational cost and communication volume are linear in the size of the Sender's set only, and do not depend on the size of the Receiver's set.Our constructions combine linearly homomorphic encryption (LHE) withfully homomorphic encryption (FHE). The first construction uses multi-point polynomial evaluation (MEv) on FHE, and achieves optimal linear cost for the Sender, but has higher quadratic computational cost for the Receiver. In the second construction we explore another trade-off: the Receiver computes fast polynomial Euclidean remainder in FHE while the Sender computes a fast MEv, in LHE only. This reduces the Receiver's cost to quasi-linear, with a modest increase in the computational cost for the Sender.Preliminary experimental results using HElib indicate that, for example, a Sender holding 1000 elements can complete our first protocol using less than 2s of computation time and less than 10MB of communication volume, independently of the Receiver's set size.

We consider the classical problems of interpolating a polynomial given a black box for evaluation, and of multiplying two polynomials, in the setting where the bit-lengths of the coefficients may vary widely, so-called unbalanced polynomials. Writing s for the total bit-length and D for the degree, our new algorithms have expected running time $\tilde{O}(s \log D)$, whereas previous methods for (resp.) dense or sparse arithmetic have at least $\tilde{O}(sD)$ or $\tilde{O}(s^2)$ bit complexity.

This paper deals with simultaneously fast and in-place algorithms for formulae where the result has to be linearly accumulated: some of the output variables are also input variables, linked by a linear dependency. Fundamental examples include the in-place accumulated multiplication of polynomials or matrices, C+=AB. The difficulty is to combine in-place computations with fast algorithms: those usually come at the expense of (potentially large) extra temporary space, but with accumulation the output variables are not even available to store intermediate values. We first propose a novel automatic design of fast and in-place accumulating algorithms for any bilinear formulae (and thus for polynomial and matrix multiplication) and then extend it to any linear accumulation of a collection of functions. For this, we relax the in-place model to any algorithm allowed to modify its inputs, provided that those are restored to their initial state afterwards. This allows us, in fine, to derive unprecedented in-place accumulating algorithms for fast polynomial multiplications and for Strassen-like matrix multiplications., Comment: Proceedings of the 49th International Symposium on Symbolic and Algebraic Computation (ISSAC'24), ACM SIGSAM, Jul 2024, Raleigh, NC, United States

This article aims at clarifying the situation about astrophysical sources that might be observed with haloscope experiments sensitive to gravitational waves in the 1-10 GHz band. The GrAHal setup is taken as a benchmark. We follow a very pedagogical path so that the full analysis can easily be used by the entire community who might not be familiar with the theoretical framework. Different relevant physical regimes are considered in details and some formulas encountered in the literature are revised. In particular, we carefully take into account the fast drift of the gravitational wave frequency and the relevant experimental timescales. We also relax the usual assumption that only the merging phase should be considered. The distances that can be probed and expected event rates are carefully evaluated, taking into account degeneracies between physical parameters. We show where experimental efforts should be focused to improve the sensitivity and we conclude that any detection in the near future is extremely unlikely.

We consider the simultaneously fast and in-place computation of the Euclidean polynomial modular remainder $R(X) $\not\equiv$ A(X) \mod B(X)$ with $A$ and $B$ of respective degrees $n$ and $m $\le$ n$. But fast algorithms for this usually come at the expense of (potentially large) extra temporary space. To remain in-place a further issue is to avoid the storage of the whole quotient $Q(X)$ such that $A=BQ+R$. If the multiplication of two polynomials of degree $k$ can be performed with $M(k)$ operations and $O(k)$ extra space, and if it is allowed to use the input space of $A$ or $B$ for intermediate computations, but putting $A$ and $B$ back to their initial states after the completion of the remainder computation, we here propose an in-place algorithm (that is with its extra required space reduced to $O(1)$ only) using at most $O(n/m M(m)\log(m)$ arithmetic operations, if $\M(m)$ is quasi-linear, or $O(n/m M(m)}$ otherwise. We also propose variants that compute -- still in-place and with the same kind of complexity bounds -- the over-place remainder $A(X) $\not\equiv$ A(X) \mod B(X)$, the accumulated remainder $R(X) += A(X) \mod B(X)$ and the accumulated modular multiplication $R(X) += A(X)C(X) \mod B(X)$. To achieve this, we develop techniques for Toeplitz matrix operations which output is also part of the input. Fast and in-place accumulating versions are obtained for the latter, and thus for convolutions, and then used for polynomial remaindering. This is realized via further reductions to accumulated polynomial multiplication, for which fast in-place algorithms have recently been developed., Comment: Proceedings of the 49th International Symposium on Symbolic and Algebraic Computation (ISSAC'24), ACM SIGSAM, Jul 2024, Raleigh, NC, United States

A recent experimental work has reported an excess of the non-linear conductivity in the charge density wave (CDW) sliding mode of the quasi one-dimensional compound (TaSe4)2I, when a magnetic field is applied co-linearly to the electric field [Gooth et al., Nature 575, 315 (2019)]. This result has opened a conceptual approach, where the CDW gap in (TaSe4)2I is opened between Weyl fermions of opposite chirality with the assumption that this compound is a Weyl semi-metal in its undistorted high temperature phase. We report measurements in the sliding state of (TaSe4)2I performed in similar conditions. We have found no increase in the magnetoconductivity. In our attempts for understanding this unsettling discrepancy, we stress the specific nature of the Peierls transition in (TaSe4)2I and the strong electron-phonon coupling present in this compound. Given the lack of further evidence, we think that it is premature to assert that (TaSe4)2I is an axionic insulator., Comment: 8 pages, 3 figures

Numerous algorithms call for computation over the integers modulo a randomly-chosen large prime. In some cases, the quasi-cubic complexity of selecting a random prime can dominate the total running time. We propose a new variant of the classic D5 algorithm for "dynamic evaluation", applied to a randomly-chosen (composite) integer. Unlike the D5 principle which has been used in the past to compute over a direct product of fields, our method is simpler as it only requires following a single path after any modulus splits. The transformation we propose can apply to any algorithm in the algebraic RAM model, even allowing randomization. The resulting transformed algorithm avoids any primality tests and will, with constant positive probability, have the same result as the original computation modulo a randomly-chosen prime. As an application, we demonstrate how to compute the exact number of nonzero terms in an unknown integer polynomial in quasi-linear time. We also show how the same algorithmic transformation technique can be used for computing modulo random irreducible polynomials over a finite field.

Given a way to evaluate an unknown polynomial with integer coefficients, we present new algorithms to recover its nonzero coefficients and corresponding exponents. As an application, we adapt this interpolation algorithm to the problem of computing the exact quotient of two given polynomials. These methods are efficient in terms of the bit-length of the sparse representation, that is, the number of nonzero terms, the size of coefficients, the number of variables, and the logarithm of the degree. At the core of our results is a new Monte Carlo randomized algorithm to recover a polynomial $f(x)$ with integer coefficients given a way to evaluate $f(\theta) \bmod m$ for any chosen integers $\theta$ and $m$. This algorithm has nearly-optimal bit complexity, meaning that the total bit-length of the probes, as well as the computational running time, is softly linear (ignoring logarithmic factors) in the bit-length of the resulting sparse polynomial. To our knowledge, this is the first sparse interpolation algorithm with soft-linear bit complexity in the total output size. For polynomials with integer coefficients, the best previously known results have at least a cubic dependency on the bit-length of the exponents., Comment: 22 pages

We describe a straightforward method to generate a random prime q such that the multiplicative group GF(q)* also has a random large prime-order subgroup. The described algorithm also yields this order p as well as a p'th primitive root of unity. The methods here are efficient asymptotically, but due to large constants may not be very useful in practical settings.

In this note we report on the development plans and first results of the Grenoble Axion Haloscope (GrAHal) project. It is aimed at developing a haloscope platform dedicated to the search for axion dark matter particles. We discuss its general framework and the plans to reach the sensitivity required to probe well known invisible axion models, over particularly relevant axion masses and coupling regions. We also present our first haloscope prototype and the result of its test run at liquid He temperature, setting a new exclusion limit $g_{a \gamma \gamma} \leq 2.2 \times 10^{-13}~ \text{GeV}^{-1}$ ($g_{a \gamma \gamma} \leq 22 \times g_{\text{KSVZ}}$) around 6.375 GHz ($m_a \simeq 26.37$ $\mu \text{eV}$)., Comment: 5 pages

The impact of epitaxial strain on the structural, electronic, and thermoelectric properties of p-type transparent Sr-doped LaCrO3 thin films has been investigated. For this purpose, high-quality fully strained La0.75Sr0.25CrO3 (LSCO) epitaxial thin films were grown by molecular beam epitaxy on three different (pseudo)cubic (001)-oriented perovskite oxide substrates: LaAlO3, (LaAlO3)0.3(Sr2AlTaO6)0.7, and DyScO3. The lattice mismatch between the LSCO films and the substrates induces in-plane strain ranging from -2.06% (compressive) to +1.75% (tensile). The electric conductivity can be controlled over 2 orders of magnitude, ranging from 0.5 S/cm (tensile strain) to 35 S/cm (compressive strain). Consistently, the Seebeck coefficient S can be finely tuned by a factor of almost 2 from 127 microV/K (compressive strain) to 208 microV/K (tensile strain). Interestingly, we show that the thermoelectric power factor can consequently be tuned by almost 2 orders of magnitude. The compressive strain yields a remarkable enhancement by a factor of 3 for 2% compressive strain with respect to almost relaxed films. These results demonstrate that epitaxial strain is a powerful lever to control the electric properties of LSCO and enhance its thermoelectric properties, which is of high interest for various devices and key applications such as thermal energy harvesters, coolers, transparent conductors, photocatalyzers, and spintronic memories., Comment: Article, 10 pages in final published format, 6 figures

The matching literature often recommends market centralization under the assumption that agents know their own preferences and that their preferences are fixed. We find counterevidence to this assumption in a quasi-experiment. In Germany's university admissions, a clearinghouse implements the early stages of the Gale-Shapley algorithm in real time. We show that early offers made in this decentralized phase, although not more desirable, are accepted more often than later ones. These results, together with survey evidence and a theoretical model, are consistent with students' costly learning about universities. We propose a hybrid mechanism to combine the advantages of decentralization and centralization. Published at The Journal of Political Economy under a new title, ``Preference Discovery in University Admissions: The Case for Dynamic Multioffer Mechanisms,'' available at https://doi.org/10.1086/718983 (Open Access).

This paper describes the observation of non-equilibrium field effects at room temperature in four disordered insulating systems: granular Al, discontinuous Au, amorphous NbSi and amorphous InOx thin films. The use of wide enough gate voltage ranges and a cautious analysis of the data allow us to uncover memory dips, the advocated hallmark of the electron glass, in the four systems. These memory dips are found to relax slowly over days of measurements under gate voltage changes, reflecting the impossibility for the systems to reach an equilibrium state within experimentally accessible times. Our findings demonstrate that these electrical glassy effects, so far essentially reported at cryogenic temperatures, actually extend up to room temperature.

The Zoetrope Genetic Programming (ZGP) algorithm is based on an original representation for mathematical expressions, targeting evolutionary symbolic regression.The zoetropic representation uses repeated fusion operations between partial expressions, starting from the terminal set. Repeated fusions within an individual gradually generate more complex expressions, ending up in what can be viewed as new features. These features are then linearly combined to best fit the training data. ZGP individuals then undergo specific crossover and mutation operators, and selection takes place between parents and offspring. ZGP is validated using a large number of public domain regression datasets, and compared to other symbolic regression algorithms, as well as to traditional machine learning algorithms. ZGP reaches state-of-the-art performance with respect to both types of algorithms, and demonstrates a low computational time compared to other symbolic regression approaches.

No polynomial-time algorithm is known to test whether a sparse polynomial G divides another sparse polynomial $F$. While computing the quotient Q=F quo G can be done in polynomial time with respect to the sparsities of F, G and Q, this is not yet sufficient to get a polynomial-time divisibility test in general. Indeed, the sparsity of the quotient Q can be exponentially larger than the ones of F and G. In the favorable case where the sparsity #Q of the quotient is polynomial, the best known algorithm to compute Q has a non-linear factor #G#Q in the complexity, which is not optimal. In this work, we are interested in the two aspects of this problem. First, we propose a new randomized algorithm that computes the quotient of two sparse polynomials when the division is exact. Its complexity is quasi-linear in the sparsities of F, G and Q. Our approach relies on sparse interpolation and it works over any finite field or the ring of integers. Then, as a step toward faster divisibility testing, we provide a new polynomial-time algorithm when the divisor has a specific shape. More precisely, we reduce the problem to finding a polynomial S such that QS is sparse and testing divisibility by S can be done in polynomial time. We identify some structure patterns in the divisor G for which we can efficiently compute such a polynomial~S.

Polynomial multiplication is known to have quasi-linear complexity in both the dense and the sparse cases. Yet no truly linear algorithm has been given in any case for the problem, and it is not clear whether it is even possible. This leaves room for a better algorithm for the simpler problem of verifying a polynomial product. While finding deterministic methods seems out of reach, there exist probabilistic algorithms for the problem that are optimal in number of algebraic operations. We study the generalization of the problem to the verification of a polynomial product modulo a sparse divisor. We investigate its bit complexity for both dense and sparse multiplicands. In particular, we are able to show the primacy of the verification over modular multiplication when the divisor has a constant sparsity and a second highest-degree monomial that is not too large. We use these results to obtain new bounds on the bit complexity of the standard polynomial multiplication verification. In particular, we provide optimal algorithms in the bit complexity model in the dense case by improving a result of Kaminski and develop the first quasi-optimal algorithm for verifying sparse polynomial product.

We report on the precise determination of both the band gap E$_\text{g}$, and the characteristic energy $U$ of the band tail of localized defect states, for monocrystalline Ag$_2$ZnSnSe$_4$. Both photoluminescence excitation and time-resolved photoluminescence studies lead to E$_\text{g} = 1223\pm3$ meV, and $U = 20\pm3$ meV, at 6 K. The interest of the methodology developed here is to account quantitatively for the time-resolved photoluminescence and photoluminescence excitation spectra by only considering standard textbook density of states, and state filling effects. Such an approach is different from the one most often used to evaluate the energy extent of the localized states, namely by measuring the energy shift between the photoluminescence emission and the excitation one -- the so-called Stokes shift. The advantage of the present method is that no arbitrary choice of the low power excitation has to be done to select the photoluminescence emission spectrum and its peak energy., Comment: 6 pages, 4 figures. Supplemental GIF file is the animated view over a large subset of the TRPL data (article ref. 29)

We consider space-saving versions of several important operations on univariate polynomials, namely power series inversion and division, division with remainder, multi-point evaluation, and interpolation. Now-classical results show that such problems can be solved in (nearly) the same asymptotic time as fast polynomial multiplication. However, these reductions, even when applied to an in-place variant of fast polynomial multiplication, yield algorithms which require at least a linear amount of extra space for intermediate results. We demonstrate new in-place algorithms for the aforementioned polynomial computations which require only constant extra space and achieve the same asymptotic running time as their out-of-place counterparts. We also provide a precise complexity analysis so that all constants are made explicit, parameterized by the space usage of the underlying multiplication algorithms.

We present a probabilistic algorithm to compute the product of two univariate sparse polynomials over a field with a number of bit operations that is quasi-linear in the size of the input and the output. Our algorithm works for any field of characteristic zero or larger than the degree. We mainly rely on sparse interpolation and on a new algorithm for verifying a sparse product that has also a quasi-linear time complexity. Using Kronecker substitution techniques we extend our result to the multivariate case., Comment: 12 pages

We report on non equilibrium field effect in insulating amorphous NbSi thin films having different Nb contents and thicknesses. The hallmark of an electron glass, namely the logarithmic growth of a memory dip in conductance versus gate voltage curves, is observed in all the films after a cooling from room temperature to 4.2 K. A very rich phenomenology is demonstrated. While the memory dip width is found to strongly vary with the film parameters, as was also observed in amorphous indium oxide films, screening lengths and temperature dependence of the dynamics are closer to what is observed in granular Al films. Our results demonstrate that the differentiation between continuous and discontinuous systems is not relevant to understand the discrepancies reported between various systems in the electron glass features. We suggest instead that they are not of fundamental nature and stem from differences in the protocols used and in the electrical inhomogeneity length scales within each material., Comment: Submission SciPost