More Like this

1. Local Access to Huge Random Objects Through Partial Sampling

   Biswas, Amartya Shankha ; Rubinfeld, Ronitt ; Yodpinyanee, Anak ( January 2020 , 11th Innovations in Theoretical Computer Science Conference, ITCS 2020)

   Consider an algorithm performing a computation on a huge random object (for example a random graph or a "long" random walk). Is it necessary to generate the entire object prior to the computation, or is it possible to provide query access to the object and sample it incrementally "on-the-fly" (as requested by the algorithm)? Such an implementation should emulate the random object by answering queries in a manner consistent with an instance of the random object sampled from the true distribution (or close to it). This paradigm is useful when the algorithm is sub-linear and thus, sampling the entire object up front would ruin its efficiency. Our first set of results focus on undirected graphs with independent edge probabilities, i.e. each edge is chosen as an independent Bernoulli random variable. We provide a general implementation for this model under certain assumptions. Then, we use this to obtain the first efficient local implementations for the Erdös-Rényi G(n,p) model for all values of p, and the Stochastic Block model. As in previous local-access implementations for random graphs, we support Vertex-Pair and Next-Neighbor queries. In addition, we introduce a new Random-Neighbor query. Next, we give the first local-access implementation for All-Neighbors queries inmore »the (sparse and directed) Kleinberg’s Small-World model. Our implementations require no pre-processing time, and answer each query using O(poly(log n)) time, random bits, and additional space. Next, we show how to implement random Catalan objects, specifically focusing on Dyck paths (balanced random walks on the integer line that are always non-negative). Here, we support Height queries to find the location of the walk, and First-Return queries to find the time when the walk returns to a specified location. This in turn can be used to implement Next-Neighbor queries on random rooted ordered trees, and Matching-Bracket queries on random well bracketed expressions (the Dyck language). Finally, we introduce two features to define a new model that: (1) allows multiple independent (and even simultaneous) instantiations of the same implementation, to be consistent with each other without the need for communication, (2) allows us to generate a richer class of random objects that do not have a succinct description. Specifically, we study uniformly random valid q-colorings of an input graph G with maximum degree Δ. This is in contrast to prior work in the area, where the relevant random objects are defined as a distribution with O(1) parameters (for example, n and p in the G(n,p) model). The distribution over valid colorings is instead specified via a "huge" input (the underlying graph G), that is far too large to be read by a sub-linear time algorithm. Instead, our implementation accesses G through local neighborhood probes, and is able to answer queries to the color of any given vertex in sub-linear time for q ≥ 9Δ, in a manner that is consistent with a specific random valid coloring of G. Furthermore, the implementation is memory-less, and can maintain consistency with non-communicating copies of itself.« less
2. Sampling Random Spanning Trees Faster than Matrix Multiplication

   https://doi.org/10.1145/3055399.3055499  

   Durfee, David ; Kyng, Rasmus ; Peebles, John ( June 2017 , Proceedings of the annual ACM Symposium on Theory of Computing)

   We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in \Otil(n^{5/3 }m^{1/3}) time\footnote{The \Otil(\cdot) notation hides \poly(\log n) factors}. The tree is sampled from a distribution where the probability of each tree is proportional to the product of its edge weights. This improves upon the previous best algorithm due to Colbourn et al. that runs in matrix multiplication time, O(n^\omega). For the special case of unweighted graphs, this improves upon the best previously known running time of \tilde{O}(\min\{n^{\omega},m\sqrt{n},m^{4/3}\}) for m >> n^{7/4} (Colbourn et al. '96, Kelner-Madry '09, Madry et al. '15). The effective resistance metric is essential to our algorithm, as in the work of Madry et al., but we eschew determinant-based and random walk-based techniques used by previous algorithms. Instead, our algorithm is based on Gaussian elimination, and the fact that effective resistance is preserved in the graph resulting from eliminating a subset of vertices (called a Schur complement). As part of our algorithm, we show how to compute \eps-approximate effective resistances for a set SS of vertex pairs via approximate Schur complements in \Otil(m+(n + |S|)\eps^{-2}) time, without using the Johnson-Lindenstrauss lemma which requires \Otil( \min\{(m + |S|)\eps^{-2},more »m+n\eps^{-4} +|S|\eps^{-2}\}) time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn't sufficiently accurate.« less
3. Smoothed Analysis of Information Spreading in Dynamic Networks

   Dinitz, Michael ; Fineman, Jeremy ; Gilbert, Seth ; Newport, Calvin ( October 2022 , Leibniz international proceedings in informatics)

   The best known solutions for k-message broadcast in dynamic networks of size n require Ω(nk) rounds. In this paper, we see if these bounds can be improved by smoothed analysis. To do so, we study perhaps the most natural randomized algorithm for disseminating tokens in this setting: at every time step, choose a token to broadcast randomly from the set of tokens you know. We show that with even a small amount of smoothing (i.e., one random edge added per round), this natural strategy solves k-message broadcast in Õ(n+k³) rounds, with high probability, beating the best known bounds for k = o(√n) and matching the Ω(n+k) lower bound for static networks for k = O(n^{1/3}) (ignoring logarithmic factors). In fact, the main result we show is even stronger and more general: given 𝓁-smoothing (i.e., 𝓁 random edges added per round), this simple strategy terminates in O(kn^{2/3}log^{1/3}(n)𝓁^{-1/3}) rounds. We then prove this analysis close to tight with an almost-matching lower bound. To better understand the impact of smoothing on information spreading, we next turn our attention to static networks, proving a tight bound of Õ(k√n) rounds to solve k-message broadcast, which is better than what our strategy can achieve in themore »dynamic setting. This confirms the intuition that although smoothed analysis reduces the difficulties induced by changing graph structures, it does not eliminate them altogether. Finally, we apply tools developed to support our smoothed analysis to prove an optimal result for k-message broadcast in so-called well-mixed networks in the absence of smoothing. By comparing this result to an existing lower bound for well-mixed networks, we establish a formal separation between oblivious and strongly adaptive adversaries with respect to well-mixed token spreading, partially resolving an open question on the impact of adversary strength on the k-message broadcast problem.« less
4. Streaming algorithms for the missing item finding problem

   Manuel Stoeckl ( January 2023 , SODA 2023)

   Many problems on data streams have been studied at two extremes of difficulty: either allowing randomized algorithms, in the static setting (where they should err with bounded probability on the worst case stream); or when only deterministic and infallible algorithms are required. Some recent works have considered the adversarial setting, in which a randomized streaming algorithm must succeed even on data streams provided by an adaptive adversary that can see the intermediate outputs of the algorithm. In order to better understand the differences between these models, we study a streaming task called “Missing Item Finding”. In this problem, for r < n, one is given a data stream a1 , . . . , ar of elements in [n], (possibly with repetitions), and must output some x ∈ [n] which does not equal any of the ai. We prove that, for r = nΘ(1) and δ = 1/poly(n), the space required for randomized algorithms that solve this problem in the static setting with error δ is Θ(polylog(n)); for algorithms in the adversarial setting with error δ, Θ((1 + r2/n)polylog(n)); and for deterministic algorithms, Θ(r/polylog(n)). Because our adversarially robust algorithm relies on free access to a string of O(r log n)more »random bits, we investigate a “random start” model of streaming algorithms where all random bits used are included in the space cost. Here we find a conditional lower bound on the space usage, which depends on the space that would be needed for a pseudo-deterministic algorithm to solve the problem. We also prove an Ω(r/polylog(n)) lower bound for the space needed by a streaming algorithm with < 1/2polylog(n) error against “white-box” adversaries that can see the internal state of the algorithm, but not predict its future random decisions.« less
5. M giants with IGRINS: I. Stellar parameters and α -abundance trends of the solar neighborhood population

   https://doi.org/10.1051/0004-6361/202346149  

   Nandakumar, G. ; Ryde, N. ; Casagrande, L. ; Mace, G. ( July 2023 , Astronomy & Astrophysics)

   Context. Cool stars, such as M giants, can only be analyzed in the near-infrared (NIR) regime due to the ubiquitous titanium oxide features in optical spectra of stars with T eff  < 4000 K. In dust-obscured regions, the inner bulge and Galactic center region, the intrinsically bright M giants observed in the NIR are an optimal option for studying stellar abundances and the chemical evolution of stellar populations. Because of the uncertainties in photometric methods, a method for determining the stellar parameters for M giants from the NIR spectra themselves is needed. Aims. We develop a method for determining the stellar parameters for M giants from the NIR spectra. We validate the method by deriving the stellar parameters for nearby well-studied M giants with spectra from the spectral library of the Immersion GRating INfrared Spectrograph (IGRINS). We demonstrate the accuracy and precision of our method by determining the stellar parameters and α -element trends versus metallicity for solar neighborhood M giants. Methods. We carried out new observations of 44 M giant stars with IGRINS mounted on the Gemini South telescope. We also obtained the full H and K band IGRINS spectra of six nearby well-studied M giants at a spectral resolvingmore »power of R  = 45 000 from the IGRINS spectral library. We used the tool called spectroscopy made easy in combination with one-dimensional (1D) model atmospheres in a radiative and convective scheme (MARCS) stellar atmosphere models to model the synthetic spectrum that fits the observed spectrum best. Results. The effective temperatures that we derive from our new method (tested for 3400 ≲  T eff  ≲ 4000 K here) agree excellently with those of the six nearby well-studied M giants, which indicates that the accuracy is indeed high. For the 43 solar neighborhood M giants, our T eff , log g , [Fe/H], ξ micro , [C/Fe], [N/Fe], and [O/Fe] agree with APOGEE with mean differences and a scatter (our method – APOGEE) of −67±33 K, −0.31±0.15 dex, 0.02±0.05 dex, 0.22±0.13 km s −1 , −0.05±0.06 dex, 0.06±0.06 dex, and 0.02±0.09 dex, respectively. Furthermore, the tight offset with a small dispersion compared to the APOGEE T eff indicates a high precision in our derived temperatures and those derived from the APOGEE pipeline. The typical uncertainties in the stellar parameters are found to be ±100 K in T eff , ±0.2 dex in log g , ±0.1 dex in [Fe/H], and ±0.1 km s −1 in ξ micro . The α -element trends versus metallicity for Mg, Si, Ca, and Ti are consistent with the APOGEE DR17 trends for the same stars and with the GILD optical trends. We also find a clear enhancement in the abundances for thick-disk stars.« less