Search results for "Computer and Information Science"
showing 10 items of 1335 documents
Tighter Relations between Sensitivity and Other Complexity Measures
2014
The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004 [11].
Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
2013
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh [AKR05] uses \(O(\sqrt{N \log{N}})\) steps and finds a marked location with probability O(1 / logN) for grid of size \(\sqrt{N} \times \sqrt{N}\). This probability is small, thus [AKR05] needs amplitude amplification to get Θ(1) probability. The amplitude amplification adds an additional \(O(\sqrt{\log{N}})\) factor to the number of steps, making it \(O(\sqrt{N} \log{N})\).
The equidistribution of some Mahonian statistics over permutations avoiding a pattern of length three
2022
Abstract We prove the equidistribution of several multistatistics over some classes of permutations avoiding a 3-length pattern. We deduce the equidistribution, on the one hand of inv and foz e ″ statistics, and on the other hand that of maj and makl statistics, over these classes of pattern avoiding permutations. Here inv and maj are the celebrated Mahonian statistics, foz e ″ is one of the statistics defined in terms of generalized patterns in the 2000 pioneering paper of Babson and Steingrimsson, and makl is one of the statistics defined by Clarke, Steingrimsson and Zeng in (1997) [5] . These results solve several conjectures posed by Amini in (2018) [1] .
Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
2017
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly k or l of the n input bits given by an oracle are 1. We find an optimal algorithm (for some cases), and a nontrivial general lower and upper bound on the minimum number of queries to the black box.
The Global Research Collaboration of Network Meta-Analysis: A Social Network Analysis
2016
et al.
On the inductive inference of recursive real-valued functions
1999
AbstractWe combine traditional studies of inductive inference and classical continuous mathematics to produce a study of learning real-valued functions. We consider two possible ways to model the learning by example of functions with domain and range the real numbers. The first approach considers functions as represented by computable analytic functions. The second considers arbitrary computable functions of recursive real numbers. In each case we find natural examples of learnable classes of functions and unlearnable classes of functions.
Linear-size suffix tries
2016
Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w | , a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and lin…
Improving computation efficiency using input and architecture features for a virtual screening application
2023
Virtual screening is an early stage of the drug discovery process that selects the most promising candidates. In the urgent computing scenario it is critical to find a solution in a short time frame. In this paper, we focus on a real-world virtual screening application to evaluate out-of-kernel optimizations, that consider input and architecture features to improve the computation efficiency on GPU. Experiment results on a modern supercomputer node show that we can almost double the performance. Moreover, we implemented the optimization using SYCL and it provides a consistent benefit with the CUDA optimization. A virtual screening campaign can use this gain in performance to increase the nu…
Seam Puckering Objective Evaluation Method for Sewing Process
2015
The paper presents an automated method for the assessment and classification of puckering defects detected during the preproduction control stage of the sewing machine or product inspection. In this respect, we have presented the possible causes and remedies of the wrinkle nonconformities. Subjective factors related to the control environment and operators during the seams evaluation can be reduced using an automated system whose operation is based on image processing. Our implementation involves spectral image analysis using Fourier transform and an unsupervised neural network, the Kohonen Map, employed to classify material specimens, the input images, into five discrete degrees of quality…
Reduced Order Models for Pricing European and American Options under Stochastic Volatility and Jump-Diffusion Models
2016
European options can be priced by solving parabolic partial(-integro) differential equations under stochastic volatility and jump-diffusion models like the Heston, Merton, and Bates models. American option prices can be obtained by solving linear complementary problems (LCPs) with the same operators. A finite difference discretization leads to a so-called full order model (FOM). Reduced order models (ROMs) are derived employing proper orthogonal decomposition (POD). The early exercise constraint of American options is enforced by a penalty on subset of grid points. The presented numerical experiments demonstrate that pricing with ROMs can be orders of magnitude faster within a given model p…