Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Large-scale genome-wide association studies on a GPU cluster using a CUDA-accelerated PGAS programming model
2015
[Abstract] Detecting epistasis, such as 2-SNP interactions, in genome-wide association studies (GWAS) is an important but time consuming operation. Consequently, GPUs have already been used to accelerate these studies, reducing the runtime for moderately-sized datasets to less than 1 hour. However, single-GPU approaches cannot perform large-scale GWAS in reasonable time. In this work we present multiEpistSearch, a tool to detect epistasis that works on GPU clusters. While CUDA is used for parallelization within each GPU, the workload distribution among GPUs is performed with Unified Parallel C++ (UPC++), a novel extension of C++ that follows the Partitioned Global Address Space (PGAS) model…
The fixed angle scattering problem and wave equation inverse problems with two measurements
2019
We consider two formally determined inverse problems for the wave equation in more than one space dimension. Motivated by the fixed angle inverse scattering problem, we show that a compactly supported potential is uniquely determined by the far field pattern generated by plane waves coming from exactly two opposite directions. This implies that a reflection symmetric potential is uniquely determined by its fixed angle scattering data. We also prove a Lipschitz stability estimate for an associated problem. Motivated by the point source inverse problem in geophysics, we show that a compactly supported potential is uniquely determined from boundary measurements of the waves generated by exactl…
A sampling method for detecting buried objects using electromagnetic scattering
2005
We consider a simple (but fully three-dimensional) mathematical model for the electromagnetic exploration of buried, perfect electrically conducting objects within the soil underground. Moving an electric device parallel to the ground at constant height in order to generate a magnetic field, we measure the induced magnetic field within the device, and factor the underlying mathematics into a product of three operations which correspond to the primary excitation, some kind of reflection on the surface of the buried object(s) and the corresponding secondary excitation, respectively. Using this factorization we are able to give a justification of the so-called sampling method from inverse scat…
Checkpointing Workflows for Fail-Stop Errors
2017
International audience; We consider the problem of orchestrating the exe- cution of workflow applications structured as Directed Acyclic Graphs (DAGs) on parallel computing platforms that are subject to fail-stop failures. The objective is to minimize expected overall execution time, or makespan. A solution to this problem consists of a schedule of the workflow tasks on the available processors and of a decision of which application data to checkpoint to stable storage, so as to mitigate the impact of processor failures. For general DAGs this problem is hopelessly intractable. In fact, given a solution, computing its expected makespan is still a difficult problem. To address this challenge,…
An Efficient Traceable Attribute-Based Authentication Scheme with One-Time Attribute Trees
2015
Attribute-based authentication (ABA) is a way to authenticate signers by means of attributes and it requests proof of possessing required attributes from the one to be authenticated. To achieve the property of traceability, required attributes should be combined with the signer’s attribute private keys in order to generate a signature. In some schemes, signers’ attribute keys are related to attribute trees, so changing attribute trees will cause the regeneration of all related attribute keys. In this paper, we propose an efficient traceable ABA scheme, where the generation of signers’ attribute keys is independent from attribute trees. Thus the same set of attribute keys can be used with a …
Fast narrowing-driven partial evaluation for inductively sequential programs
2005
Narrowing-driven partial evaluation is a powerful technique for the specialization of (first-order) functional and functional logic programs. However, although it gives good results on small programs, it does not scale up well to realistic problems (e.g., interpreter specialization). In this work, we introduce a faster partial evaluation scheme by ensuring the termination of the process offline . For this purpose, we first characterize a class of programs which are quasi-terminating , i.e., the computations performed with needed narrowing—the symbolic computation mechanism of narrowing-driven partial evaluation—only contain finitely many different terms (and, thus, partial evaluation termi…
“Anti-Bayesian” flat and hierarchical clustering using symmetric quantiloids
2017
A myriad of works has been published for achieving data clustering based on the Bayesian paradigm, where the clustering sometimes resorts to Naive-Bayes decisions. Within the domain of clustering, the Bayesian principle corresponds to assigning the unlabelled samples to the cluster whose mean (or centroid) is the closest. Recently, Oommen and his co-authors have proposed a novel, counter-intuitive and pioneering PR scheme that is radically opposed to the Bayesian principle. The rational for this paradigm, referred to as the “Anti-Bayesian” (AB) paradigm, involves classification based on the non-central quantiles of the distributions. The first-reported work to achieve clustering using the A…
Upper bound on the communication complexity of private information retrieval
1997
We construct a scheme for private information retrieval with k databases and communication complexity O(n 1/(2k−1) ).
Multi-pass execution of functional logic programs
1994
An operational semantics for functional logic programs is presented. In such programs functional terms provide for reduction of expressions, provided that they ground. The semantics is based on multi-pass evaluation techniques originally developed for attribute grammars. Program execution is divided into two phases: (1) construction of an incomplete proof tree, and (2) its decoration into a complete proof tree. The construction phase applies a modified SLD-resolution scheme, and the decoration phase a partial (multi-pass) traversal over the tree. The phase partition is generated by static analysis where data dependencies are extracted for the functional elements of the program. The method g…
Embedding Evolution in Epidemic-Style Forwarding
2007
International audience; In this work, we introduce a framework to let forwarding schemes evolve in order to adapt to changing and a priori unknown environments. The framework is inspired by genetic algorithms: at each node a genotype describes the forwarding scheme used, a selection process fosters the diffusion of the fittest genotypes in the system and new genotypes are created by combining existing ones or applying random changes. A case study implementation is presented and its performance evaluated via numerical simulations.