More Like this

1. Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds

   https://doi.org/10.4230/LIPIcs.DNA.30.2  

   Demaine, Erik D; Gomez, Timothy; Grizzell, Elise; Hecher, Markus; Lynch, Jayson; Schweller, Robert; Shalaby, Ahmed; Woods, Damien (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Seki, Shinnosuke; Stewart, Jaimie Marie (Ed.)

   Molecular programmers and nanostructure engineers use domain-level design to abstract away messy DNA/RNA sequence, chemical and geometric details. Such domain-level abstractions are enforced by sequence design principles and provide a key principle that allows scaling up of complex multistranded DNA/RNA programs and structures. Determining the most favoured secondary structure, or Minimum Free Energy (MFE), of a set of strands, is typically studied at the sequence level but has seen limited domain-level work. We analyse the computational complexity of MFE for multistranded systems in a simple setting were we allow only 1 or 2 domains per strand. On the one hand, with 2-domain strands, we find that the MFE decision problem is NP-complete, even without pseudoknots, and requires exponential time algorithms assuming SAT does. On the other hand, in the simplest case of 1-domain strands there are efficient MFE algorithms for various binding modes. However, even in this single-domain case, MFE is P-hard for promiscuous binding, where one domain may bind to multiple as experimentally used by Nikitin [Nat Chem., 2023], which in turn implies that strands consisting of a single domain efficiently implement arbitrary Boolean circuits. 

   more » « less
2. Batch Multivalid Conformal Prediction

   Jung, Christopher; Noarov, Georgy; Ramalingam, Ramya; Roth, Aaron (January 2023, International Conference on Learning Representations (ICLR))

   We develop fast distribution-free conformal prediction algorithms for obtaining multivalid coverage on exchangeable data in the batch setting. Multivalid coverage guarantees are stronger than marginal coverage guarantees in two ways: (1) They hold even conditional on group membership---that is, the target coverage level holds conditionally on membership in each of an arbitrary (potentially intersecting) group in a finite collection of regions in the feature space. (2) They hold even conditional on the value of the threshold used to produce the prediction set on a given example. In fact multivalid coverage guarantees hold even when conditioning on group membership and threshold value simultaneously. We give two algorithms: both take as input an arbitrary non-conformity score and an arbitrary collection of possibly intersecting groups , and then can equip arbitrary black-box predictors with prediction sets. Our first algorithm is a direct extension of quantile regression, needs to solve only a single convex minimization problem, and produces an estimator which has group-conditional guarantees for each group in . Our second algorithm is iterative, and gives the full guarantees of multivalid conformal prediction: prediction sets that are valid conditionally both on group membership and non-conformity threshold. We evaluate the performance of both of our algorithms in an extensive set of experiments. 

   more » « less
3. Extending the Benefits of Parallel Elasticity Across Multiple Actuation Tasks: A Geometric and Optimization-Based Approach

   https://doi.org/10.1109/TMECH.2025.3583658  

   Yang, Kang; Dickens, Myia; Schmiedeler, James; Bolívar-Nieto, Edgar (July 2025, IEEE/ASME Transactions on Mechatronics)

   Ibaraki, S; Chen, X (Ed.)

   A spring in parallel with an effort source (e.g., electric motor or human muscle) can reduce its energy consumption and effort (i.e., torque or force) depending on the spring stiffness, spring preload, and actuation task. However, selecting the spring stiffness and preload that guarantees effort or energy reduction for an arbitrary set of tasks is a design challenge. This work formulates a convex optimization problem to guarantee that a parallel spring reduces the root-mean-square source effort or energy consumption for multiple tasks. Specifically, we guarantee the benefits across multiple tasks by enforcing a set of convex quadratic constraints in our optimization variables, the parallel spring stiffness and preload. These quadratic constraints are equivalent to ellipses in the stiffness and preload plane; any combination of stiffness and preload inside the ellipse represents a parallel spring that minimizes effort source or energy consumption with respect to an actuator without a spring. This geometric interpretation intuitively guides the stiffness and preload selection process. We analytically and experimentally prove the convex quadratic function of the spring stiffness and preload. As applications, we analyze the stiffness and preload selection of a parallel spring for a knee exoskeleton using human muscle as the effort source and a prosthetic ankle powered by electric motors. The source code associated with our framework is available as supplemental open-source software. 

   more » « less
4. An analogue of polynomially integrable bodies in even-dimensional spaces

   https://doi.org/10.1016/j.jmaa.2023.127071  

   Agranovsky, M; Koldobsky, A; Ryabogin, D; Yaskin, V. (January 2024, Journal of mathematical analysis and applications)

   A bounded domain $$K \subset R^n$$ is called polynomially integrable ifthe $(n-1)$-dimensional volume of the intersection $$K$$ with a hyperplane $$\Pi$$ polynomially depends on the distance from $$\Pi$$ to the origin. It was proved in \cite{KMY} that there are no such domains with smooth boundary if $$n$$ is even, and if $$n$$ is odd then the only polynomially integrable domains with smooth boundary are ellipsoids. In this article, we modify the notion of polynomial integrability for even $$n$$ and consider bodies for which the sectional volume function is a polynomial up to a factor which is the square root of a quadratic polynomial, or, equivalently, the Hilbert transform of this function is a polynomial. We prove that ellipsoids in even dimensions are the only convex infinitely smooth bodies satisfying this property. 

   more » « less
5. Cosmology from the kinetic polarized Sunyaev Zel'dovich effect

   https://doi.org/10.1088/1475-7516/2022/10/026  

   Hotinli, Selim C.; Holder, Gilbert P.; Johnson, Matthew C.; Kamionkowski, Marc (October 2022, Journal of Cosmology and Astroparticle Physics)

   Abstract The cosmic microwave background (CMB) photons that scatter off free electrons in the large-scale structure induce a linear polarization pattern proportional to the remote CMB temperature quadrupole observed in the electrons' rest frame. The associated blackbody polarization anisotropies are known as the polarized Sunyaev Zel'dovich (pSZ) effect. Relativistic corrections to the remote quadrupole field give rise to a non-blackbody polarization anisotropy proportional to the square of the transverse peculiar velocity field; this is the kinetic polarized Sunyaev Zel'dovich (kpSZ) effect. In this paper, we forecast the ability of future CMB and galaxy surveys to detect the kpSZ effect, finding that a statistically significant detection is within the reach of planned experiments. We further introduce a quadratic estimator for the square of the peculiar velocity field based on a galaxy survey and CMB polarization. Finally, we outline how the kpSZ effect is a probe of cosmic birefringence and primordial non-Gaussianity, forecasting the reach of future experiments. 

   more » « less