Given the computational cost and technical expertise required to train machine learning models, users may delegate the task of learning to a service provider. We show how a malicious learner can plant an undetectable backdoor into a classifier. On the surface, such a backdoored classifier behaves normally, but in reality, the learner maintains a mechanism for changing the classification of any input, with only a slight perturbation. Importantly, without the appropriate "backdoor key", the mechanism is hidden and cannot be detected by any computationally-bounded observer. We demonstrate two frameworks for planting undetectable backdoors, with incomparable guarantees. First, we show how to plant a backdoor in any model, using digital signature schemes. The construction guarantees that given black-box access to the original model and the backdoored version, it is computationally infeasible to find even a single input where they differ. This property implies that the backdoored model has generalization error comparable with the original model. Second, we demonstrate how to insert undetectable backdoors in models trained using the Random Fourier Features (RFF) learning paradigm or in Random ReLU networks. In this construction, undetectability holds against powerful white-box distinguishers: given a complete description of the network and the training data, no efficient distinguisher can guess whether the model is "clean" or contains a backdoor. Our construction of undetectable backdoors also sheds light on the related issue of robustness to adversarial examples. In particular, our construction can produce a classifier that is indistinguishable from an "adversarially robust" classifier, but where every input has an adversarial example! In summary, the existence of undetectable backdoors represent a significant theoretical roadblock to certifying adversarial robustness.

This document contains a description of several of my papers, including remarks on history and connection with subsequent work. It also contains some new results and conjectures.

The star-forming main sequence (SFMS) is a tight relation observed between stellar masses and star formation rates (SFR) in a population of galaxies. This relation is observed at different redshifts, in various morphological, and environmental domains, and is key to understanding the underlying relations between a galaxy budget of cold gas and its stellar content. Euclid Quick Data Release 1 (Q1) gives us the opportunity to investigate this fundamental relation in galaxy formation and evolution. We complement the Euclid release with public IRAC observations of the Euclid Deep Fields, improving the quality of recovered photometric redshifts, stellar masses, and SFRs, as is shown both with simulations and a comparison with available spectroscopic redshifts. From Q1 data alone, we recover more than $\sim 30\,\mathrm{k}$ galaxies with $\log_{10} (M_\ast/M_\odot) > 11$, giving a precise constraint of the SFMS at the high-mass end. We investigated the SFMS, in a redshift interval between $0.2$ and $3.0$, comparing our results with the existing literature and fitting them with a parameterisation taking into account the presence of a bending of the relation at the high-mass end, depending on the bending mass, $M_0$. We find good agreement with previous results in terms of $M_0$ values, and an increasing trend for the relation scatter at higher stellar masses. We also investigate the distribution of physical (e.g. dust absorption, $A_V$, and formation age) and morphological properties (e.g., Sérsic index and radius) in the SFR--stellar mass plane, and their relation with the SFMS. These results highlight the potential of Euclid in studying the fundamental scaling relations that regulate galaxy formation and evolution in anticipation of the forthcoming Data Release 1.

The notion of replicable algorithms was introduced in Impagliazzo et al. [STOC '22] to describe randomized algorithms that are stable under the resampling of their inputs. More precisely, a replicable algorithm gives the same output with high probability when its randomness is fixed and it is run on a new i.i.d. sample drawn from the same distribution. Using replicable algorithms for data analysis can facilitate the verification of published results by ensuring that the results of an analysis will be the same with high probability, even when that analysis is performed on a new data set. In this work, we establish new connections and separations between replicability and standard notions of algorithmic stability. In particular, we give sample-efficient algorithmic reductions between perfect generalization, approximate differential privacy, and replicability for a broad class of statistical problems. Conversely, we show any such equivalence must break down computationally: there exist statistical problems that are easy under differential privacy, but that cannot be solved replicably without breaking public-key cryptography. Furthermore, these results are tight: our reductions are statistically optimal, and we show that any computational separation between DP and replicability must imply the existence of one-way functions. Our statistical reductions give a new algorithmic framework for translating between notions of stability, which we instantiate to answer several open questions in replicability and privacy. This includes giving sample-efficient replicable algorithms for various PAC learning, distribution estimation, and distribution testing problems, algorithmic amplification of $\delta$ in approximate DP, conversions from item-level to user-level privacy, and the existence of private agnostic-to-realizable learning reductions under structured distributions.

Gravitational lensing allows the detection of binary black holes (BBH) at cosmological distances with chirp masses that appear to be enhanced by $1+z$ in the range $195\%$), from which we infer a factor $\simeq 5$ higher intrinsic rate of NSBH events than BBH events, reflecting a higher proportion of neutron stars formed by early star formation. We predict a distinctive locus for lensed NSBH events in the observed binary mass plane, spanning $1

We give improved pseudorandom generators (PRGs) for Lipschitz functions of low-degree polynomials over the hypercube. These are functions of the form psi(P(x)), where P is a low-degree polynomial and psi is a function with small Lipschitz constant. PRGs for smooth functions of low-degree polynomials have received a lot of attention recently and play an important role in constructing PRGs for the natural class of polynomial threshold functions. In spite of the recent progress, no nontrivial PRGs were known for fooling Lipschitz functions of degree O(log n) polynomials even for constant error rate. In this work, we give the first such generator obtaining a seed-length of (log n)\tilde{O}(d^2/eps^2) for fooling degree d polynomials with error eps. Previous generators had an exponential dependence on the degree. We use our PRG to get better integrality gap instances for sparsest cut, a fundamental problem in graph theory with many applications in graph optimization. We give an instance of uniform sparsest cut for which a powerful semi-definite relaxation (SDP) first introduced by Goemans and Linial and studied in the seminal work of Arora, Rao and Vazirani has an integrality gap of exp(\Omega((log log n)^{1/2})). Understanding the performance of the Goemans-Linial SDP for uniform sparsest cut is an important open problem in approximation algorithms and metric embeddings and our work gives a near-exponential improvement over previous lower bounds which achieved a gap of \Omega(log log n).

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can be computed by a shallow decision tree. While this conjecture implies that smooth functions are easy to compute in the simplest computational model, to date no non-trivial upper bounds were known for such functions in any computational model, including unrestricted Boolean circuits. Even a bound on the description length of such functions better than the trivial $2^n$ does not seem to have been known. In this work, we establish the first computational upper bounds on smooth Boolean functions: 1) We show that every sensitivity s function is uniquely specified by its values on a Hamming ball of radius 2s. We use this to show that such functions can be computed by circuits of size $n^{O(s)}$. 2) We show that sensitivity s functions satisfy a strong pointwise noise-stability guarantee for random noise of rate O(1/s). We use this to show that these functions have formulas of depth O(s log n). 3) We show that sensitivity s functions can be (locally) self-corrected from worst-case noise of rate $\exp(-O(s))$. All our results are simple, and follow rather directly from (variants of) the basic fact that that the function value at few points in small neighborhoods of a given point determine its function value via a majority vote. Our results confirm various consequences of the conjecture. They may be viewed as providing a new form of evidence towards its validity, as well as new directions towards attacking it.

The photometer section of SPIRE is one of the key instruments on board of Herschel. Its legacy depends very much on how well the scanmap observations that it carried out during the Herschel mission can be converted to high quality maps. In order to have a comprehensive assessment on the current status of SPIRE map-making, as well as to provide guidance for future development of the SPIRE scan-map data reduction pipeline, we carried out a test campaign on SPIRE map-making. In this report, we present results of the tests in this campaign.

We prove a lower bound of $\Omega(n^{1/2 - c})$, for all $c>0$, on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an $n$-variable Boolean function is monotone versus constant-far from monotone. This improves a $\tilde{\Omega}(n^{1/5})$ lower bound for the same problem that was recently given in [CST14] and is very close to $\Omega(n^{1/2})$, which we conjecture is the optimal lower bound for this model.

Let R be a perfect F_p-algebra, equipped with the trivial norm. Let W(R) be the ring of p-typical Witt vectors over R, equipped with the p-adic norm. At the level of nonarchimedean analytic spaces (in the sense of Berkovich), we demonstrate a close analogy between W(R) and the polynomial ring R[T] equipped with the Gauss norm, in which the role of the structure morphism from R to R[T] is played by the Teichmuller map. For instance, we show that the analytic space associated to R is a strong deformation retract of the space associated to W(R). We also show that each fibre forms a tree under the relation of pointwise comparison, and classify the points of fibres in the manner of Berkovich's classification of points of a nonarchimedean disc. Some results pertain to the study of p-adic representations of etale fundamental groups of nonarchimedean analytic spaces (i.e., relative p-adic Hodge theory).

SDSS-V will be an all-sky, multi-epoch spectroscopic survey of over six million objects. It is designed to decode the history of the Milky Way, trace the emergence of the chemical elements, reveal the inner workings of stars, and investigate the origin of planets. It will also create an integral-field spectroscopic map of the gas in the Galaxy and the Local Group that is 1,000x larger than the current state of the art and at high enough spatial resolution to reveal the self-regulation mechanisms of galactic ecosystems. SDSS-V will pioneer systematic, spectroscopic monitoring across the whole sky, revealing changes on timescales from 20 minutes to 20 years. The survey will thus track the flickers, flares, and radical transformations of the most luminous persistent objects in the universe: massive black holes growing at the centers of galaxies. The scope and flexibility of SDSS-V will be unique among extant and future spectroscopic surveys: it is all-sky, with matched survey infrastructures in both hemispheres; it provides near-IR and optical multi-object fiber spectroscopy that is rapidly reconfigurable to serve high target densities, targets of opportunity, and time-domain monitoring; and it provides optical, ultra-wide-field integral field spectroscopy. SDSS-V, with its programs anticipated to start in 2020, will be well-timed to multiply the scientific output from major space missions (e.g., TESS, Gaia, eROSITA) and ground-based projects. SDSS-V builds on the 25-year heritage of SDSS's advances in data analysis, collaboration infrastructure, and product deliverables. The project is now refining its science scope, optimizing the survey strategies, and developing new hardware that builds on the SDSS-IV infrastructure. We present here an overview of the current state of these developments as we seek to build our worldwide consortium of institutional and individual members.

Let $P:\{0,1\}^k \to \{0,1\}$ be a nontrivial $k$-ary predicate. Consider a random instance of the constraint satisfaction problem $\mathrm{CSP}(P)$ on $n$ variables with $\Delta n$ constraints, each being $P$ applied to $k$ randomly chosen literals. Provided the constraint density satisfies $\Delta \gg 1$, such an instance is unsatisfiable with high probability. The \emph{refutation} problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate $P$ supports a $t$-\emph{wise uniform} probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree $d = \Theta(\frac{n}{\Delta^{2/(t-1)} \log \Delta})$ (which runs in time $n^{O(d)}$) \emph{cannot} refute a random instance of $\mathrm{CSP}(P)$. In particular, the polynomial-time SOS algorithm requires $\widetilde{\Omega}(n^{(t+1)/2})$ constraints to refute random instances of CSP$(P)$ when $P$ supports a $t$-wise uniform distribution on its satisfying assignments. Together with recent work of Lee et al. [LRS15], our result also implies that \emph{any} polynomial-size semidefinite programming relaxation for refutation requires at least $\widetilde{\Omega}(n^{(t+1)/2})$ constraints. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate~$P$, they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of Allen et al. [AOW15] and Raghavendra et al. [RRS16], this full three-way tradeoff is \emph{tight}, up to lower-order factors.

We present a set of photometric catalogs primarily aimed at providing the community with a comprehensive database for the study of galaxy populations in the high redshift Universe. The set gathers data from eight JWST NIRCam observational programs, targeting the Abell 2744 (GLASS-JWST, UNCOVER, DDT2756 and GO3990), EGS (CEERS), COSMOS and UDS (PRIMER), and GOODS North and South (JADES and NGDEEP) deep fields, for a total area of $\sim$0.2 sq. degrees. Photometric estimates are obtained by means of well-established techniques, including tailored improvements designed to enhance the performance on the specific dataset. We also include new measurements from HST archival data, thus collecting 16 bands spanning from 0.44 to 4.44 $\mu$m. A grand total of $\sim$530 thousand sources is detected on stacks of NIRCam 3.56 and 4.44 $\mu$m mosaics. We assess the photometric accuracy by comparing fluxes and colors against archival catalogs. We also provide photometric redshift estimates, statistically validated against a large set of robust spectroscopic data. The catalogs are publicly available on the Astrodeep website.

We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff and efficient list decoding up to the Johnson bound in polynomial time. Previous constructions of list decodable good distance quantum codes either required access to a classical side channel or were based on algebraic constructions that preclude the LDPC property. Our construction relies on new algorithmic results for codes obtained via the quantum analog of the distance amplification scheme of Alon, Edmonds, and Luby [FOCS 1995]. These results are based on convex relaxations obtained using the Sum-of-Squares hierarchy, which reduce the problem of list decoding the distance amplified codes to unique decoding the starting base codes. Choosing these base codes to be the recent breakthrough constructions of good QLDPC codes with efficient unique decoders, we get efficiently list decodable QLDPC codes.

When studying the expressive power of neural networks, a main challenge is to understand how the size and depth of the network affect its ability to approximate real functions. However, not all functions are interesting from a practical viewpoint: functions of interest usually have a polynomially-bounded Lipschitz constant, and can be computed efficiently. We call functions that satisfy these conditions "benign", and explore the benefits of size and depth for approximation of benign functions with ReLU networks. As we show, this problem is more challenging than the corresponding problem for non-benign functions. We give barriers to showing depth-lower-bounds: Proving existence of a benign function that cannot be approximated by polynomial-size networks of depth $4$ would settle longstanding open problems in computational complexity. It implies that beyond depth $4$ there is a barrier to showing depth-separation for benign functions, even between networks of constant depth and networks of nonconstant depth. We also study size-separation, namely, whether there are benign functions that can be approximated with networks of size $O(s(d))$, but not with networks of size $O(s'(d))$. We show a complexity-theoretic barrier to proving such results beyond size $O(d\log^2(d))$, but also show an explicit benign function, that can be approximated with networks of size $O(d)$ and not with networks of size $o(d/\log d)$. For approximation in $L_\infty$ we achieve such separation already between size $O(d)$ and size $o(d)$. Moreover, we show superpolynomial size lower bounds and barriers to such lower bounds, depending on the assumptions on the function. Our size-separation results rely on an analysis of size lower bounds for Boolean functions, which is of independent interest: We show linear size lower bounds for computing explicit Boolean functions with neural networks and threshold circuits.

The Planck full mission cosmic microwave background(CMB) temperature and E-mode polarization maps are analysed to obtain constraints on primordial non-Gaussianity(NG). Using three classes of optimal bispectrum estimators - separable template-fitting (KSW), binned, and modal - we obtain consistent values for the local, equilateral, and orthogonal bispectrum amplitudes, quoting as our final result from temperature alone fNL^local=2.5+\-5.7, fNL^equil=-16+\-70 and fNL^ortho=-34+\-33(68%CL). Combining temperature and polarization data we obtain fNL^local=0.8+\-5.0, fNL^equil=-4+\-43 and fNL^ortho=-26+\-21 (68%CL). The results are based on cross-validation of these estimators on simulations, are stable across component separation techniques, pass an extensive suite of tests, and are consistent with Minkowski functionals based measurements. The effect of time-domain de-glitching systematics on the bispectrum is negligible. In spite of these test outcomes we conservatively label the results including polarization data as preliminary, owing to a known mismatch of the noise model in simulations and the data. Beyond fNL estimates, we present model-independent reconstructions of the CMB bispectrum and derive constraints on early universe scenarios that generate NG, including general single-field and axion inflation, initial state modifications, parity-violating tensor bispectra, and directionally dependent vector models. We also present a wide survey of scale-dependent oscillatory bispectra, and we look for isocurvature NG. Our constraint on the local primordial trispectrum amplitude is gNL^local=(-9.0+\-7.7)x10^4 (68%CL), and we perform an analysis of additional trispectrum shapes. The global picture is one of consistency with the premises of the LambdaCDM cosmology, namely that the structure we observe today was sourced by adiabatic, passive, Gaussian, and primordial seed perturbations.[abridged]

We use PACS and SPIRE continuum data at 160 um, 250 um, 350 um, and 500 um from the Herschel Gould Belt Survey to sample seven clumps in Perseus: B1, B1-E, B5, IC348, L1448, L1455, and NGC1333. Additionally, we identify and characterize the embedded Class 0 protostars using detections of compact Herschel sources at 70 um as well as archival Spitzer catalogues and SCUBA 850 um photometric data. We identify 28 candidate Class 0 protostars, four of which are newly discovered sources not identified with Spitzer. We find that the star formation efficiency of clumps, as traced by Class 0 protostars, correlates strongly with the flatness of their respective column density distributions at high values. This correlation suggests that the fraction of high column density material in a clump reflects only its youngest protostellar population rather than its entire source population. We propose that feedback from either the formation or evolution of protostars changes the local density structure of clumps.

Let an algebraic group G act on X, a connected algebraic manifold, with finitely many orbits. For any Harish-Chandra pair (D,G) where D is a sheaf of twisted differential operators on X, we form a left ideal D.g in D generated by the Lie algebra g, of G. Then, D/D.g is a holonomic D-module and its restriction to a unique Zariski open dense G-orbit in X is a G-equivariant local system. We prove a criterion saying that the D-module D/D.g is isomorphic, under certain (quite restrictive) conditions, to a direct image of that local system to X. We apply this criterion in the special case where the group G=SL(n) acts diagonally on X = F \times F \times P^{n-1}, a triple product where F is the flag manifold for SL(n) and P^{n-1} is the projective space. We further relate D-modules on F \times F \times P^{n-1} to D-modules on the space SL(n) \times P^{n-1} via a pair, CH, HC, of adjoint functors, analogous to those used in Lusztig's theory of character sheaves. A second important result of the paper provides an explicit description of these functors showing that the functor HC gives an exact functor on the abelian category of mirabolic D-modules.

The growth of luminous structures and the building blocks of life in the Universe began as primordial gas was processed in stars and mixed at galactic scales. The mechanisms responsible for this development are not well understood and have changed over the intervening 13 billion years. To follow the evolution of matter over cosmic time, it is necessary to study the strongest (resonance) transitions of the most abundant species in the Universe. Most of them are in the ultraviolet (UV; 950A-3000A) spectral range that is unobservable from the ground. A versatile space observatory with UV sensitivity a factor of 50-100 greater than existing facilities will revolutionize our understanding of the Universe. Habitable planets grow in protostellar discs under ultraviolet irradiation, a by-product of the star-disk interaction that drives the physical and chemical evolution of discs and young planetary systems. The electronic transitions of the most abundant molecules are pumped by the UV field, providing unique diagnostics of the planet-forming environment that cannot be accessed from the ground. Earth's atmosphere is in constant interaction with the interplanetary medium and the solar UV radiation field. A 50-100 times improvement in sensitivity would enable the observation of the key atmospheric ingredients of Earth-like exoplanets (carbon, oxygen, ozone), provide crucial input for models of biologically active worlds outside the solar system, and provide the phenomenological baseline to understand the Earth atmosphere in context. In this white paper, we outline the key science that such a facility would make possible and outline the instrumentation to be implemented.