skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


This content will become publicly available on December 9, 2025

Title: In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in Rényi divergence (which implies TV, KL etc.). The proof departs from known approaches for polytime algorithms for the problem - we utilize a stochastic diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the stationary density.  more » « less
Award ID(s):
2106444
PAR ID:
10613754
Author(s) / Creator(s):
;
Publisher / Repository:
Neurips 2024
Date Published:
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, PLOS ONE)
    El_Allali, Achraf (Ed.)
    With mutations constantly accumulating in bacterial genomes, it is unclear whether the previously identified bacterial strains are really present in an extant sample. To address this question, we did a case study on the known strains of the bacterial speciesS.aureusandS.epidermisin 68 atopic dermatitis shotgun metagenomic samples. We evaluated the likelihood of the presence of all sixteen known strains predicted in the original study and by two popular tools in this study. We found that even with the same tool, only two known strains were predicted by the original study and this study. Moreover, none of the sixteen known strains was likely present in these 68 samples. Our study thus indicates the limitation of the known-strain-based studies, especially those on rapidly evolving bacterial species. It implies the unlikely presence of the previously identified known strains in a current environmental sample. It also called for de novo bacterial strain identification directly from shotgun metagenomic reads. 
    more » « less
  2. ; (, The Electronic Journal of Combinatorics)
    We prove that for all graphs with at most $(3.75-o(1))n$ edges there exists a 2-coloring of the edges such that every monochromatic path has order less than $$n$$.  This was previously known to be true for graphs with at most $2.5n-7.5$ edges. We also improve on the best-known lower bounds in the $$r$$-color case. 
    more » « less
  3. ; ; (, Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))
    Naor, Joseph; Buchbinder, Niv (Ed.)
    We consider the bilateral trade problem, in which two agents trade a single indivisible item. It is known that the only dominant-strategy truthful mechanism is the fixed-price mechanism: given commonly known distributions of the buyer's value B and the seller's value S, a price p is offered to both agents and trade occurs if S ≤ p ≤ B. The objective is to maximize either expected welfare or expected gains from trade . We improve the approximation ratios for several welfare maximization variants of this problem. When the agents' distributions are identical, we show that the optimal approximation ratio for welfare is . With just one prior sample from the common distribution, we show that a 3/4-approximation to welfare is achievable. When agents' distributions are not required to be identical, we show that a previously best-known (1–1/e)-approximation can be strictly improved, but 1–1/e is optimal if only the seller's distribution is known. 
    more » « less
  4. ; ; ; ; ; ; ; ; ; ; et al (, The Astronomical Journal)
    Abstract We have used data from the UKIRT Hemisphere Survey to search for substellar members of the Hyades cluster. Our search recovered several known substellar Hyades members, and two known brown dwarfs that we suggest may be members based on a new kinematic analysis. We uncovered thirteen new substellar Hyades candidates, and obtained near-infrared follow-up spectroscopy of each with IRTF/SpeX. Six candidates with spectral types between M7 and L0 are ruled out as potential members based on their photometric distances (≳100 pc). The remaining seven candidates, with spectral types between L5 and T4, are all potential Hyades members, with five showing strong membership probabilities based on BANYAN Σ and a convergent point analysis. Distances and radial velocities are still needed to confirm Hyades membership. If confirmed, these would be some of the lowest mass free-floating members of the Hyades yet known, with masses as low as ∼30 M Jup . An analysis of all known substellar Hyades candidates shows evidence that the full extent of the Hyades has yet to be probed for low-mass members, and more would likely be recovered with deeper photometric and astrometric investigations. 
    more » « less
  5. ; ; (, Geological Society of America)
    A set of 11 clinoamphibole standards with known Fe3+/ΣFe were analyzed for X-ray absorption spectra at the Advanced Photon Source at Argonne National Laboratory. Fe3+/ΣFe of each sample is known from Mössbauer data, and span from 0% to 100% Fe3+/ΣFe. Due to the extreme absorption anisotropy of crystals, we determined the orientation of clinoamphiboles crystals using single-crystal X-ray diffraction and spindle stage techniques. Clinoamphiboles crystal were then analyzed with the beam propagation and polarization axes along known direction relative to the crystallographic basis. Absorption anisotropy was then interpolated to predict the range of absorption magnitudes a clinoamphibole may exhibit at each energy. Partial least square fits for Fe3+/ΣFe indicate predictions are closest to the known Fe3+/ΣFe when comparing the same orientation of each sample in the dataset. Predictions including all orientations, while less accurate, still yield strong results with an R-squared of 0.9 and RMSE of 4.7. The results from this dataset demonstrate the efficacy of XAS as a microanalytical technique for crystalline materials, and functions as a reference dataset to research in oxybarometry. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email