More Like this

1. A scaling limit for the length of the longest cycle in a sparse random digraph

   https://doi.org/10.1002/rsa.21030  

   Anastos, A.; Frieze, A. (January 2022, Random structures algorithms)

   We discuss the length $$\vL_{c,n}$$ of the longest directed cycle in the sparse random digraph $$D_{n,p},p=c/n$$, $$c$$ constant. We show that for large $$c$$ there exists a function $$\vf(c)$$ such that $$\vL_{c,n}/n\to \vf(c)$$ a.s. The function $$\vf(c)=1-\sum_{k=1}^\infty p_k(c)e^{-kc}$$ where $$p_k$$ is a polynomial in $$c$$. We are only able to explicitly give the values $$p_1,p_2$$, although we could in principle compute any $$p_k$$. 

   more » « less
2. Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem

   https://doi.org/10.4230/lipics.itcs.2025.77  

   Pettie, Seth; Wang, Dingyu (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   In the d-dimensional turnstile streaming model, a frequency vector 𝐱 = (𝐱(1),…,𝐱(n)) ∈ (ℝ^d)ⁿ is updated entry-wisely over a stream. We consider the problem of f-moment estimation for which one wants to estimate f(𝐱)=∑_{v ∈ [n]}f(𝐱(v)) with a small-space sketch. A function f is tractable if the f-moment can be estimated to within a constant factor using polylog(n) space. The f-moment estimation problem has been intensively studied in the d = 1 case. Flajolet and Martin estimate the F₀-moment (f(x) = 1 (x > 0), incremental stream); Alon, Matias, and Szegedy estimate the L₂-moment (f(x) = x²); Indyk estimates the L_α-moment (f(x) = |x|^α), α ∈ (0,2]. For d ≥ 2, Ganguly, Bansal, and Dube estimate the L_{p,q} hybrid moment (f:ℝ^d → ℝ,f(x) = (∑_{j = 1}^d |x_j|^p)^q), p ∈ (0,2],q ∈ (0,1). For tractability, Bar-Yossef, Jayram, Kumar, and Sivakumar show that f(x) = |x|^α is not tractable for α > 2. Braverman, Chestnut, Woodruff, and Yang characterize the class of tractable one-variable functions except for a class of nearly periodic functions. In this work we present a simple and generic scheme to construct sketches with the novel idea of hashing indices to Lévy processes, from which one can estimate the f-moment f(𝐱) where f is the characteristic exponent of the Lévy process. The fundamental Lévy-Khintchine representation theorem completely characterizes the space of all possible characteristic exponents, which in turn characterizes the set of f-moments that can be estimated by this generic scheme. The new scheme has strong explanatory power. It unifies the construction of many existing sketches (F₀, L₀, L₂, L_α, L_{p,q}, etc.) and it implies the tractability of many nearly periodic functions that were previously unclassified. Furthermore, the scheme can be conveniently generalized to multidimensional cases (d ≥ 2) by considering multidimensional Lévy processes and can be further generalized to estimate heterogeneous moments by projecting different indices with different Lévy processes. We conjecture that the set of tractable functions can be characterized using the Lévy-Khintchine representation theorem via what we called the Fourier-Hahn-Lévy method. 

   more » « less
3. The Cosmic Ultraviolet Baryon Survey (CUBS) – I. Overview and the diverse environments of Lyman limit systems at z < 1

   https://doi.org/10.1093/mnras/staa1773  

   Chen, Hsiao-Wen; Zahedy, Fakhri S; Boettcher, Erin; Cooper, Thomas M; Johnson, Sean D; Rudie, Gwen C; Chen, Mandy C; Walth, Gregory L; Cantalupo, Sebastiano; Cooksey, Kathy L; et al (September 2020, Monthly Notices of the Royal Astronomical Society)

   ABSTRACT We present initial results from the Cosmic Ultraviolet Baryon Survey (CUBS). CUBS is designed to map diffuse baryonic structures at redshift z ≲ 1 using absorption-line spectroscopy of 15 UV-bright QSOs with matching deep galaxy survey data. CUBS QSOs are selected based on their NUV brightness to avoid biases against the presence of intervening Lyman limit systems (LLSs) at zabs < 1. We report five new LLSs of $$\log \, N({\mathrm{ H} \,{\small I}})/{{\rm cm^{-2}}}\gtrsim 17.2$$ over a total redshift survey path-length of $$\Delta \, z_{\mathrm{ LL}}=9.3$$, and a number density of $$n(z)=0.43_{-0.18}^{+0.26}$$. Considering all absorbers with $$\log \, N({{\mathrm{ H} \,{\small I}}})/{{\rm cm^{-2}}}\gt 16.5$$ leads to $$n(z)=1.08_{-0.25}^{+0.31}$$ at zabs < 1. All LLSs exhibit a multicomponent structure and associated metal transitions from multiple ionization states such as C ii, C iii, Mg ii, Si ii, Si iii, and O vi absorption. Differential chemical enrichment levels as well as ionization states are directly observed across individual components in three LLSs. We present deep galaxy survey data obtained using the VLT-MUSE integral field spectrograph and the Magellan Telescopes, reaching sensitivities necessary for detecting galaxies fainter than $$0.1\, L_*$$ at d ≲ 300 physical kpc (pkpc) in all five fields. A diverse range of galaxy properties is seen around these LLSs, from a low-mass dwarf galaxy pair, a co-rotating gaseous halo/disc, a star-forming galaxy, a massive quiescent galaxy, to a galaxy group. The closest galaxies have projected distances ranging from d = 15 to 72 pkpc and intrinsic luminosities from $${\approx} 0.01\, L_*$$ to $${\approx} 3\, L_*$$. Our study shows that LLSs originate in a variety of galaxy environments and trace gaseous structures with a broad range of metallicities. 

   more » « less
4. Approximating the noise sensitivity of a monotone Boolean function

   Rubinfeld, Ronitt; Vasilyan, Arsen (January 2019, International Conference on Randomization and Computation (RANDOM 2019))

   The noise sensitivity of a Boolean function f:{0,1}n→{0,1} is one of its fundamental properties. A function of a positive noise parameter δ, it is denoted as NSδ[f]. Here we study the algorithmic problem of approximating it for monotone f, such that NSδ[f]≥1/nC for constant C, and where δ satisfies 1/n≤δ≤1/2. For such f and δ, we give a randomized algorithm performing O(min(1,n√δlog1.5n)NSδ[f]poly(1ϵ)) queries and approximating NSδ[f] to within a multiplicative factor of (1±ϵ). Given the same constraints on f and δ, we also prove a lower bound of Ω(min(1,n√δ)NSδ[f]⋅nξ) on the query complexity of any algorithm that approximates NSδ[f] to within any constant factor, where ξ can be any positive constant. Thus, our algorithm's query complexity is close to optimal in terms of its dependence on n. We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield previously unknown lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias. 

   more » « less
5. Approximating the noise sensitivity of a monotone Boolean function

   Rubinfeld, R.; Vasilyan, A. (January 2019, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019)

   The noise sensitivity of a Boolean function f: {0,1}^n - > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noise-sensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]). Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/- epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm's query complexity is close to optimal in terms of its dependence on n. We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias. 

   more » « less