-
Cascaded Group Testing
Authors:
Waqar Mirza,
Nikhil Karamchandani,
Niranjan Balachandran
Abstract:
In this paper, we introduce a variation of the group testing problem where each test is specified by an ordered subset of items and returns the first defective item in the specified order or returns null if there are no defectives. We refer to this as cascaded group testing and the goal is to identify a small set of $K$ defective items amongst a collection of size $N$, using as few tests as possib…
▽ More
In this paper, we introduce a variation of the group testing problem where each test is specified by an ordered subset of items and returns the first defective item in the specified order or returns null if there are no defectives. We refer to this as cascaded group testing and the goal is to identify a small set of $K$ defective items amongst a collection of size $N$, using as few tests as possible for perfect recovery. For the adaptive testing regime, we show that a simple scheme can find all defective items in at most $K$ tests, which is optimal. For the non-adaptive setting, we first come up with a necessary and sufficient condition for any collection of tests to be feasible for recovering all the defectives. Using this, we show that any feasible non-adaptive strategy requires at least $Ω(K^2)$ tests. In terms of achievability, it is easy to show the existence of a feasible collection of $O(K^2 \log (N/K))$ tests. We show via carefully constructed explicit designs that one can do significantly better for constant $K$. While the cases $K = 1, 2$ are straightforward, the case $K=3$ is already non-trivial and we come up with an iterative design that is asymptotically optimal and requires $Θ(\log \log N)$ tests. Note that this is in contrast to standard binary group testing, where at least $Ω(\log N)$ tests are required. For constant $K \ge 3$, our iterative design requires only poly$(\log \log N)$ tests.
△ Less
Submitted 27 September, 2024; v1 submitted 28 May, 2024;
originally announced May 2024.
-
Theory of active self-organization of dense nematic structures in the actin cytoskeleton
Authors:
Waleed Mirza,
Marco De Corato,
Marco Pensalfini,
Guillermo Vilanova,
Alejandro Torres-Sánchez,
Marino Arroyo
Abstract:
The actin cytoskeleton is remarkably adaptable and multifunctional. It often organizes into nematic bundles such as contractile rings or stress fibers. However, how a uniform and isotropic actin gel self-organizes into dense nematic bundles is not fully understood. Here, using an active gel model accounting for nematic order and density variations, we identify an active patterning mechanism leadin…
▽ More
The actin cytoskeleton is remarkably adaptable and multifunctional. It often organizes into nematic bundles such as contractile rings or stress fibers. However, how a uniform and isotropic actin gel self-organizes into dense nematic bundles is not fully understood. Here, using an active gel model accounting for nematic order and density variations, we identify an active patterning mechanism leading to localized dense nematic structures. Linear stability analysis and nonlinear finite element simulations establish the conditions for nematic bundle self-assembly and how active gel parameters control the architecture, orientation, connectivity and dynamics of self-organized patterns. Finally, we substantiate with discrete network simulations the main requirements for nematic bundle formation according to our theory, namely increased active tension perpendicular to the nematic direction and generalized active forces conjugate to nematic order. Our work portrays actin gels a reconfigurable active materials with a spontaneous tendency to develop patterns of dense nematic bundles.
△ Less
Submitted 21 December, 2023; v1 submitted 27 June, 2023;
originally announced June 2023.
-
Variational formulation of active nematics: theory and simulation
Authors:
Waleed Mirza,
Alejandro Torres-Sánchez,
Guillermo Vilanova,
Marino Arroyo
Abstract:
The structure and dynamics of important biological quasi-two-dimensional systems, ranging from cytoskeletal gels to tissues, are controlled by nematic order, defects and activity. Continuum hydrodynamic descriptions combined with numerical simulations have been used to understand such complex systems, but the physical interpretation of different active nematic models and their applicability to spe…
▽ More
The structure and dynamics of important biological quasi-two-dimensional systems, ranging from cytoskeletal gels to tissues, are controlled by nematic order, defects and activity. Continuum hydrodynamic descriptions combined with numerical simulations have been used to understand such complex systems, but the physical interpretation of different active nematic models and their applicability to specific systems is often unclear. For instance, most works rely on theories for incompressible liquid crystals but important active 2D nematic systems are compressible due to density variations or turnover. Here, we propose a theoretical and computational framework for possibly compressible and density-dependent 2D active nematic systems. This framework is based on Onsager's variational formalism to irreversible thermodynamics, according to which the dynamics result from a competition between free-energy release, dissipation and activity. We particularize this framework to recover a standard incompressible active nematic model and further formulate an alternative model for density-dependent active nemato-hydrodynamics. We show that the variational principle enables a direct and transparent derivation not only of the governing equations, but also of the finite element numerical scheme. We exercise this model in two representative examples of active nematodynamics relevant to the actin cytoskeleton during wound healing and to the dynamics of confined colonies of elongated cells.
△ Less
Submitted 2 June, 2023;
originally announced June 2023.
-
Estimating Joint Probability Distribution With Low-Rank Tensor Decomposition, Radon Transforms and Dictionaries
Authors:
Pranava Singhal,
Waqar Mirza,
Ajit Rajwade,
Karthik S. Gurumoorthy
Abstract:
In this paper, we describe a method for estimating the joint probability density from data samples by assuming that the underlying distribution can be decomposed as a mixture of product densities with few mixture components. Prior works have used such a decomposition to estimate the joint density from lower-dimensional marginals, which can be estimated more reliably with the same number of samples…
▽ More
In this paper, we describe a method for estimating the joint probability density from data samples by assuming that the underlying distribution can be decomposed as a mixture of product densities with few mixture components. Prior works have used such a decomposition to estimate the joint density from lower-dimensional marginals, which can be estimated more reliably with the same number of samples. We combine two key ideas: dictionaries to represent 1-D densities, and random projections to estimate the joint distribution from 1-D marginals, explored separately in prior work. Our algorithm benefits from improved sample complexity over the previous dictionary-based approach by using 1-D marginals for reconstruction. We evaluate the performance of our method on estimating synthetic probability densities and compare it with the previous dictionary-based approach and Gaussian Mixture Models (GMMs). Our algorithm outperforms these other approaches in all the experimental settings.
△ Less
Submitted 18 April, 2023;
originally announced April 2023.