An official website of the United States government
Abstract In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether at least one defective item is present. This problem is relevant in areas such as medical testing, DNA sequencing, communication protocols and many more. In this paper, we study (i) a sparsity-constrained version of the problem, in which the testing procedure is subjected to one of the following two constraints: items are finitely divisible and thus may participate in at most $$\gamma $$ tests; or tests are size-constrained to pool no more than $$\rho $$ items per test; and (ii) a noisy version of the problem, where each test outcome is independently flipped with some constant probability. Under each of these settings, considering the for-each recovery guarantee with asymptotically vanishing error probability, we introduce a fast splitting algorithm and establish its near-optimality not only in terms of the number of tests, but also in terms of the decoding time. While the most basic formulations of our algorithms require $$\varOmega (n)$$ storage for each algorithm, we also provide low-storage variants based on hashing, with similar recovery guarantees.
more »
« less
Emptiness instanton in quantum polytropic gas
The emptiness formation problem is addressed for a one-dimensional quantum polytropic gas characterized by an arbitrary polytropic index $$\gamma$$, which defines the equation of state $$P \sim \rho^\gamma$$, where $$P$$ is the pressure and $$\rho$$ is the density. The problem involves determining the probability of the spontaneous formation of an empty interval in the ground state of the gas. In the limit of a macroscopically large interval, this probability is dominated by an instanton configuration. By solving the hydrodynamic equations in imaginary time, we derive the analytic form of the emptiness instanton. This solution is expressed as an integral representation analogous to those used for correlation functions in Conformal Field Theory. Prominent features of the spatiotemporal profile of the instanton are obtained directly from this representation.
more »
« less
- Award ID(s):
- 2116767
- PAR ID:
- 10645977
- Publisher / Repository:
- SciPost Foundation
- Date Published:
- Journal Name:
- SciPost Physics
- Volume:
- 18
- Issue:
- 4
- ISSN:
- 2542-4653
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Suppose$$\mathcal {H}$$is an admissible Heegaard diagram for a balanced sutured manifold$$(M,\gamma )$$. We prove that the number of generators of the associated sutured Heegaard Floer complex is an upper bound on the dimension of the sutured instanton homology$$\mathit {SHI}(M,\gamma )$$. It follows, in particular, that strong L-spaces are instanton L-spaces.more » « less
-
Abstract In the supercritical range of the polytropic indices$$\gamma \in (1,\frac{4}{3})$$ we show the existence of smooth radially symmetric self-similar solutions to the gravitational Euler–Poisson system. These solutions exhibit gravitational collapse in the sense that the density blows up in finite time. Some of these solutions were numerically found by Yahil in 1983 and they can be thought of as polytropic analogues of the Larson–Penston collapsing solutions in the isothermal case$$\gamma =1$$ . They each contain a sonic point, which leads to numerous mathematical difficulties in the existence proof.more » « less
-
A well-known question in planar first-passage percolation concerns the convergence of the empirical distribution of weights as seen along geodesics. We demonstrate this convergence for an explicit model, directed last-passage percolation on\mathbb{Z}^{2}with i.i.d. exponential weights, and provide explicit formulae for the limiting distributions, which depend on the asymptotic direction. For example, for geodesics in the direction of the diagonal, the limiting weight distribution has density(1/4+x/2+x^{2}/8)e^{-x}, and so is a mixture of Gamma(1,1), Gamma(2,1), and Gamma(3,1) distributions with weights1/4,1/2, and1/4respectively. More generally, we study the local environment as seen from vertices along geodesics (including information about the shape of the path and about the weights on and off the path in a local neighborhood). We consider finite geodesics from(0,0)ton\boldsymbol{\rho}for some vector\boldsymbol{\rho}in the first quadrant, in the limit asn\to\infty, as well as semi-infinite geodesics in direction\boldsymbol{\rho}. We show almost sure convergence of the empirical distributions of the environments along these geodesics, as well as convergence of the distributions of the environment around a typical point in these geodesics, to the same limiting distribution, for which we give an explicit description.We make extensive use of a correspondence with TASEP as seen from an isolated second-class particle for which we prove new results concerning ergodicity and convergence to equilibrium. Our analysis relies on geometric arguments involving estimates for last-passage times, available from the integrable probability literature.more » « less
-
We show that any embedding $$\mathbb {R}^d \to \mathbb {R}^{2d+2^{\gamma (d)}-1}$$ inscribes a trapezoid or maps three points to a line, where $$2^{\gamma (d)}$$ is the smallest power of $$2$$ satisfying $$2^{\gamma (d)} \geq \rho (d)$$ , and $$\rho (d)$$ denotes the Hurwitz–Radon function. The proof is elementary and includes a novel application of nonsingular bilinear maps. As an application, we recover recent results on the nonexistence of affinely $$3$$ -regular maps, for infinitely many dimensions $$d$$ , without resorting to sophisticated algebraic techniques.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.21468/SciPostPhys.18.4.122
