Abstract We present a randomized approach for wait-free locks with strong bounds on time and fairness in a context in which any process can be arbitrarily delayed. Our approach supports a tryLock operation that is given a set of locks, and code to run when all the locks are acquired. A tryLock operation may fail if there is contention on the locks, in which case the code is not run. Given an upper bound$$\kappa $$ known to the algorithm on the point contention of any lock, and an upper boundLon the number of locks in a tryLock’s set, a tryLock will succeed in acquiring its locks and running the code with probability at least$$1/(\kappa L)$$ . It is thus fair. Furthermore, if the maximum step complexity for the code in any lock isT, the operation will take$$O(\kappa ^2 L^2 T)$$ steps, regardless of whether it succeeds or fails. The operations are independent, thus if the tryLock is repeatedly retried on failure, it will succeed in$$O(\kappa ^3 L^3 T)$$ expected steps. If the algorithm does not know the bounds$$\kappa $$ andL, we present a variant that can guarantee a probability of at least$$1/\kappa L\log (\kappa L T)$$ of success. We assume an oblivious adversarial scheduler, which does not make decisions based on the operations, but can predetermine any schedule for the processes, which is unknown to our algorithm. Furthermore, to account for applications that change their future requests based on the results of previous tryLock operations, we strengthen the adversary by allowing decisions of the start times and lock sets of tryLock operations to be made adaptively, given the history of the execution so far.
more »
« less
Multiscale transforms for signals on simplicial complexes
Abstract Our previous multiscale graph basis dictionaries/graph signal transforms—Generalized Haar-Walsh Transform (GHWT); Hierarchical Graph Laplacian Eigen Transform (HGLET); Natural Graph Wavelet Packets (NGWPs); and their relatives—were developed for analyzing data recorded on vertices of a given graph. In this article, we propose their generalization for analyzing data recorded on edges, faces (i.e., triangles), or more generally$$\kappa $$ -dimensional simplices of a simplicial complex (e.g., a triangle mesh of a manifold). The key idea is to use the Hodge Laplacians and their variants for hierarchical partitioning of a set of$$\kappa $$ -dimensional simplices in a given simplicial complex, and then build localized basis functions on these partitioned subsets. We demonstrate their usefulness for data representation on both illustrative synthetic examples and real-world simplicial complexes generated from a co-authorship/citation dataset and an ocean current/flow dataset.
more »
« less
- Award ID(s):
- 1912747
- PAR ID:
- 10478599
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Sampling Theory, Signal Processing, and Data Analysis
- Volume:
- 22
- Issue:
- 1
- ISSN:
- 2730-5716
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
AbstractPrevious theoretical and simulation results indicate that anisotropic porous materials have the potential to reduce turbulent skin friction in wall-bounded flows. This study experimentally investigates the influence of anisotropy on the drag response of porous substrates. A family of anisotropic periodic lattices was manufactured using 3D printing. Rod spacing in different directions was varied systematically to achieve different ratios of streamwise, wall-normal, and spanwise bulk permeabilities ($$\kappa _{xx}$$ ,$$\kappa _{yy}$$ , and$$\kappa _{zz}$$ ). The 3D printed materials were flush-mounted in a benchtop water channel. Pressure drop measurements were taken in the fully developed region of the flow to systematically characterize drag for materials with anisotropy ratios$$\frac{\kappa _{xx}}{\kappa _{yy}} \in [0.035,28.6]$$ . Results show that all materials lead to an increase in drag compared to the reference smooth wall case over the range of bulk Reynolds numbers tested ($$\hbox {Re}_b \in [500,4000]$$ ). However, the relative increase in drag is lower for streamwise-preferential materials. We estimate that the wall-normal permeability for all tested cases exceeded the threshold identified in previous literature ($$\sqrt{\kappa _{yy}}^+> 0.4$$ ) for the emergence of energetic spanwise rollers similar to Kelvin–Helmholtz vortices, which can increase drag. The results also indicate that porous walls exhibit a departure from laminar behavior at different values for bulk Reynolds numbers depending on the geometry. Graphical abstractmore » « less
-
Abstract We find the scaling limits of a general class of boundary-to-boundary connection probabilities and multiple interfaces in the critical planar FK-Ising model, thus verifying predictions from the physics literature. We also discuss conjectural formulas using Coulomb gas integrals for the corresponding quantities in general critical planar random-cluster models with cluster-weight$${q \in [1,4)}$$ . Thus far, proofs for convergence, including ours, rely on discrete complex analysis techniques and are beyond reach for other values ofqthan the FK-Ising model ($$q=2$$ ). Given the convergence of interfaces, the conjectural formulas for other values ofqcould be verified similarly with relatively minor technical work. The limit interfaces are variants of$$\text {SLE}_\kappa $$ curves (with$$\kappa = 16/3$$ for$$q=2$$ ). Their partition functions, that give the connection probabilities, also satisfy properties predicted for correlation functions in conformal field theory (CFT), expected to describe scaling limits of critical random-cluster models. We verify these properties for all$$q \in [1,4)$$ , thus providing further evidence of the expected CFT description of these models.more » « less
-
A<sc>bstract</sc> The charge-parity (CP) structure of the Yukawa interaction between the Higgs (H) boson and the top quark is measured in a data sample enriched in the t$$ \overline{\textrm{t}} $$ H and tH associated production, using 138 fb−1of data collected in proton-proton collisions at$$ \sqrt{s} $$ = 13 TeV by the CMS experiment at the CERN LHC. The study targets events where the H boson decays via H → WW or H →ττand the top quarks decay via t → Wb: the W bosons decay either leptonically or hadronically, and final states characterized by the presence of at least two leptons are studied. Machine learning techniques are applied to these final states to enhance the separation ofCP-even fromCP-odd scenarios. Two-dimensional confidence regions are set onκtand$$ \overset{\sim }{\kappa } $$ t, which are respectively defined as theCP-even andCP-odd top-Higgs Yukawa coupling modifiers. No significant fractionalCP-odd contributions, parameterized by the quantity|$$ {f}_{CP}^{\textrm{Htt}} $$ |are observed; the parameter is determined to be|$$ {f}_{CP}^{\textrm{Htt}} $$ |= 0.59 with an interval of (0.24,0.81) at 68% confidence level. The results are combined with previous results covering the H→ZZ and H→ γγdecay modes, yielding two- and one-dimensional confidence regions onκtand$$ \overset{\sim }{\kappa } $$ t, while|$$ {f}_{CP}^{\textrm{Htt}} $$ |is determined to be|$$ {f}_{CP}^{\textrm{Htt}} $$ |= 0.28 with an interval of|$$ {f}_{CP}^{\textrm{Htt}} $$ | <0.55 at 68% confidence level, in agreement with the standard modelCP-even prediction of|$$ {f}_{CP}^{\textrm{Htt}} $$ |= 0.more » « less
-
Abstract This article revisits the problem of global well-posedness for the generalized parabolic Anderson model on$$\mathbb {R}^+\times \mathbb {T}^2$$ within the framework of paracontrolled calculus (Gubinelli et al. in Forum Math, 2015). The model is given by the equation:$$\begin{aligned} (\partial _t-\Delta ) u=F(u)\eta \end{aligned}$$ where$$\eta \in C^{-1-\kappa }$$ with$$1/6>\kappa >0$$ , and$$F\in C_b^2(\mathbb {R})$$ . Assume that$$\eta \in C^{-1-\kappa }$$ and can be lifted to enhanced noise, we derive new a priori bounds. The key idea follows from the recent work by Chandra et al. (A priori bounds for 2-d generalised Parabolic Anderson Model,,2024), to represent the leading error term as a transport type term, and our techniques encompass the paracontrolled calculus, the maximum principle, and the localization approach (i.e. high-low frequency argument).more » « less
An official website of the United States government
