More Like this

1. Leibniz International Proceedings in Informatics (LIPIcs):36th International Symposium on Computational Geometry (SoCG 2020)

   https://doi.org/10.4230/LIPIcs.SoCG.2020.6  

   Ameer, Safwa; Gibson-Lopez, Matt; Krohn, Erik; Soderman, Sean; Wang, Qing (June 2020, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Cabello, Sergio; Chen, Danny Z. (Ed.)

   In this paper, we consider the Visibility Graph Recognition and Reconstruction problems in the context of terrains. Here, we are given a graph G with labeled vertices v₀, v₁, …, v_{n-1} such that the labeling corresponds with a Hamiltonian path H. G also may contain other edges. We are interested in determining if there is a terrain T with vertices p₀, p₁, …, p_{n-1} such that G is the visibility graph of T and the boundary of T corresponds with H. G is said to be persistent if and only if it satisfies the so-called X-property and Bar-property. It is known that every "pseudo-terrain" has a persistent visibility graph and that every persistent graph is the visibility graph for some pseudo-terrain. The connection is not as clear for (geometric) terrains. It is known that the visibility graph of any terrain T is persistent, but it has been unclear whether every persistent graph G has a terrain T such that G is the visibility graph of T. There actually have been several papers that claim this to be the case (although no formal proof has ever been published), and recent works made steps towards building a terrain reconstruction algorithm for any persistent graph. In this paper, we show that there exists a persistent graph G that is not the visibility graph for any terrain T. This means persistence is not enough by itself to characterize the visibility graphs of terrains, and implies that pseudo-terrains are not stretchable. 

   more » « less
2. Using Geographic Information to Analyze Wildland Firefighter Situational Awareness: Impacts of Spatial Resolution on Visibility Assessment

   https://doi.org/10.3390/fire5050151  

   Mistick, Katherine A.; Dennison, Philip E.; Campbell, Michael J.; Thompson, Matthew P. (October 2022, Fire)

   Wildland firefighters must be able to maintain situational awareness to ensure their safety. Crew members, including lookouts and crew building handlines, rely on visibility to assess risk and communicate changing conditions. Geographic information systems and remote sensing offer potential solutions for characterizing visibility using models incorporating terrain and vegetation height. Visibility can be assessed using viewshed algorithms, and while previous research has demonstrated the utility of these algorithms across multiple fields, their use in wildland firefighter safety has yet to be explored. The goals of this study were to develop an approach for assessing visibility at the handline level, quantify the effects of spatial resolution on a lidar-driven visibility analysis, and demonstrate a set of spatial metrics that can be used to inform handline safety. Comparisons were made between elevation models derived from airborne lidar at varying spatial resolutions and those derived from LANDFIRE, a US-wide 30 m product. Coarser resolution inputs overestimated visibility by as much as 223%, while the finest-scale resolution input was not practical due to extreme processing times. Canopy cover and slope had strong linear relationships with visibility, with R2 values of 0.806 and 0.718, respectively. Visibility analyses, when conducted at an appropriate spatial resolution, can provide useful information to inform situational awareness in a wildland fire context. Evaluating situational awareness at the handline level prior to engaging a fire may help firefighters evaluate potential safety risks and more effectively plan handlines. 

   more » « less
3. Pseudo-Bayesian Learning via Direct Loss Minimization with Applications to Sparse Gaussian Process Models

   Sheth, R; Khardon, R. (January 2020, Proceedings of Machine Learning Research)

   We propose that approximate Bayesian algorithms should optimize a new criterion, directly derived from the loss, to calculate their approximate posterior which we refer to as pseudo-posterior. Unlike standard variational inference which optimizes a lower bound on the log marginal likelihood, the new algorithms can be analyzed to provide loss guarantees on the predictions with the pseudo-posterior. Our criterion can be used to derive new sparse Gaussian process algorithms that have error guarantees applicable to various likelihoods. 

   more » « less
4. Search for the Epoch of Reionization with HERA: upper limits on the closure phase delay power spectrum

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

   Keller, Pascal M.; Nikolic, Bojan; Thyagarajan, Nithyanandan; Carilli, Chris L.; Bernardi, Gianni; Charles, Ntsikelelo; Bester, Landman; Smirnov, Oleg M.; Kern, Nicholas S.; Dillon, Joshua S.; et al (February 2023, Monthly Notices of the Royal Astronomical Society)

   ABSTRACT Radio interferometers aiming to measure the power spectrum of the redshifted 21 cm line during the Epoch of Reionization (EoR) need to achieve an unprecedented dynamic range to separate the weak signal from overwhelming foreground emissions. Calibration inaccuracies can compromise the sensitivity of these measurements to the effect that a detection of the EoR is precluded. An alternative to standard analysis techniques makes use of the closure phase, which allows one to bypass antenna-based direction-independent calibration. Similarly to standard approaches, we use a delay spectrum technique to search for the EoR signal. Using 94 nights of data observed with Phase I of the Hydrogen Epoch of Reionization Array (HERA), we place approximate constraints on the 21 cm power spectrum at z = 7.7. We find at 95 per cent confidence that the 21 cm EoR brightness temperature is ≤(372)2 ‘pseudo’ mK2 at 1.14 ‘pseudo’ h Mpc−1, where the ‘pseudo’ emphasizes that these limits are to be interpreted as approximations to the actual distance scales and brightness temperatures. Using a fiducial EoR model, we demonstrate the feasibility of detecting the EoR with the full array. Compared to standard methods, the closure phase processing is relatively simple, thereby providing an important independent check on results derived using visibility intensities, or related. 

   more » « less
5. On the Pseudo-Deterministic Query Complexity of NP Search Problems

   https://doi.org/10.4230/LIPIcs.CCC.2021.36  

   Goldwasser, Shafi and (August 2021, Leibniz international proceedings in informatics)

   Kabanets, Valentine (Ed.)

   We study pseudo-deterministic query complexity - randomized query algorithms that are required to output the same answer with high probability on all inputs. We prove Ω(√n) lower bounds on the pseudo-deterministic complexity of a large family of search problems based on unsatisfiable random CNF instances, and also for the promise problem (FIND1) of finding a 1 in a vector populated with at least half one’s. This gives an exponential separation between randomized query complexity and pseudo-deterministic complexity, which is tight in the quantum setting. As applications we partially solve a related combinatorial coloring problem, and we separate random tree-like Resolution from its pseudo-deterministic version. In contrast to our lower bound, we show, surprisingly, that in the zero-error, average case setting, the three notions (deterministic, randomized, pseudo-deterministic) collapse. 

   more » « less