More Like this

1. Targeted Lossy Functions and Applications

   https://doi.org/10.1007/978-3-030-84259-8\15  

   Quach, Willy ; Waters, Brent ; Wichs, Daniel ( August 2021 , CRYPTO 2021)

   Lossy trapdoor functions, introduced by Peikert and Waters (STOC ’08), can be initialized in one of two indistinguishable modes: in injective mode, the function preserves all information about its input, and can be efficiently inverted given a trapdoor, while in lossy mode, the function loses some information about its input. Such functions have found countless applications in cryptography, and can be constructed from a variety of Cryptomania assumptions. In this work, we introduce targeted lossy functions (TLFs), which relax lossy trapdoor functions along two orthogonal dimensions. Firstly, they do not require an inversion trapdoor in injective mode. Secondly, the lossy mode of the function is initialized with some target input, and the function is only required to lose information about this particular target. The injective and lossy modes should be indistinguishable even given the target. We construct TLFs from Minicrypt assumptions, namely, injective pseudorandom generators, or even one-way functions under a natural relaxation of injectivity. We then generalize TLFs to incorporate branches, and construct all-injective-but-one and all-lossy-but-one variants. We show a wide variety of applications of targeted lossy functions. In several cases, we get the first Minicrypt constructions of primitives that were previously only known under Cryptomania assumptions. Our applications include: Pseudo-entropy functions from one-way functions. Deterministic leakage-resilient message-authentication codes and improved leakage-resilient symmetric-key encryption from one-way functions. Extractors for extractor-dependent sources from one-way functions. Selective-opening secure symmetric-key encryption from one-way functions. A new construction of CCA PKE from (exponentially secure) trapdoor functions and injective pseudorandom generators. We also discuss a fascinating connection to distributed point functions. 

   more » « less
2. A Collective Colony Migration Model with Hill Functions in Recruitment

   https://doi.org/10.1142/S0218127422502133  

   Wang, Lisha ; Qiu, Zhipeng ; Kang, Yun ( November 2022 , International Journal of Bifurcation and Chaos)

   Social insect colonies’ robust and efficient collective behaviors without any central control contribute greatly to their ecological success. Colony migration is a leading subject for studying collective decision-making in migration. In this paper, a general colony migration model with Hill functions in recruitment is proposed to investigate the underlying decision making mechanism and the related dynamical behaviors. Our analysis provides the existence and stability of equilibrium, and the global dynamical behavior of the system. To understand how piecewise functions and Hill functions in recruitment impact colony migration dynamics, the comparisons are performed in both analytic results and bifurcation analysis. Our theoretical results show that the dynamics of the migration system with Hill functions in recruitment differs from that of the migration system with piecewise functions in the following three aspects: (1) all population components in our colony migration model with Hill functions in recruitment are persistent; (2) the colony migration model with Hill functions in recruitment has saddle and saddle-node bifurcations, while the migration system with piecewise functions does not; (3) the system with Hill functions has only equilibrium dynamics, i.e. either has a global stability at one interior equilibrium or has bistablity among two locally stable interior equilibria. Bifurcation analysis shows that the geometrical shape of the Hill functions greatly impacts the dynamics: (1) the system with flatter Hill functions is less likely to exhibit bistability; (2) the system with steeper functions is prone to exhibit bistability, and the steady state of total active workers is closer to that of active workers in the system with piecewise function. 

   more » « less
3. Approximating the noise sensitivity of a monotone Boolean function

   Rubinfeld, R. ; Vasilyan, A. ( January 2019 , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019)

   The noise sensitivity of a Boolean function f: {0,1}^n - > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noise-sensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]). Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/- epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm's query complexity is close to optimal in terms of its dependence on n. We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias. 

   more » « less
4. DIFFUSE: predicting isoform functions from sequences and expression profiles via deep learning

   https://doi.org/10.1093/bioinformatics/btz367  

   Chen, Hao ; Shaw, Dipan ; Zeng, Jianyang ; Bu, Dongbo ; Jiang, Tao ( July 2019 , Bioinformatics)

   Alternative splicing generates multiple isoforms from a single gene, greatly increasing the functional diversity of a genome. Although gene functions have been well studied, little is known about the specific functions of isoforms, making accurate prediction of isoform functions highly desirable. However, the existing approaches to predicting isoform functions are far from satisfactory due to at least two reasons: (i) unlike genes, isoform-level functional annotations are scarce. (ii) The information of isoform functions is concealed in various types of data including isoform sequences, co-expression relationship among isoforms, etc.

   In this study, we present a novel approach, DIFFUSE (Deep learning-based prediction of IsoForm FUnctions from Sequences and Expression), to predict isoform functions. To integrate various types of data, our approach adopts a hybrid framework by first using a deep neural network (DNN) to predict the functions of isoforms from their genomic sequences and then refining the prediction using a conditional random field (CRF) based on co-expression relationship. To overcome the lack of isoform-level ground truth labels, we further propose an iterative semi-supervised learning algorithm to train both the DNN and CRF together. Our extensive computational experiments demonstrate that DIFFUSE could effectively predict the functions of isoforms and genes. It achieves an average area under the receiver operating characteristics curve of 0.840 and area under the precision–recall curve of 0.581 over 4184 GO functional categories, which are significantly higher than the state-of-the-art methods. We further validate the prediction results by analyzing the correlation between functional similarity, sequence similarity, expression similarity and structural similarity, as well as the consistency between the predicted functions and some well-studied functional features of isoform sequences.

   https://github.com/haochenucr/DIFFUSE.

   Supplementary data are available at Bioinformatics online.

    

   more » « less
5. Optimal Selection of Basis Functions for Minimum-Effort Tracking Control of Nonminimum Phase Systems Using Filtered Basis Functions

   https://doi.org/10.1115/1.4044355  

   Ramani, Keval S. ; Duan, Molong ; Okwudire, Chinedum E. ; Ulsoy, A. Galip ( November 2019 , Journal of Dynamic Systems, Measurement, and Control)

   Abstract Accurate tracking of nonminimum phase (NMP) systems is well known to require large amounts of control effort. It is, therefore, of practical value to minimize the effort needed to achieve a desired level of tracking accuracy for NMP systems. There is growing interest in the use of the filtered basis functions (FBF) approach for tracking the control of linear NMP systems because of distinct performance advantages it has over other methods. The FBF approach expresses the control input as a linear combination of user-defined basis functions. The basis functions are forward filtered through the dynamics of the plant, and the coefficients are selected such that the tracking error is minimized. There is a wide variety of basis functions that can be used with the FBF approach, but there has been no work to date on how to select the best set of basis functions. Toward selecting the best basis functions, the Frobenius norm of the lifted system representation (LSR) of dynamics is proposed as an excellent metric for evaluating the performance of linear time varying (LTV) discrete-time tracking controllers, like FBF, independent of the desired trajectory to be tracked. Using the metric, an optimal set of basis functions that minimize the control effort without sacrificing tracking accuracy is proposed. The optimal set of basis functions is shown in simulations and experiments to significantly reduce control effort while maintaining or improving tracking accuracy compared to popular basis functions, like B-splines. 

   more » « less