Journal articles on the topic 'Oracle based algorithms'
To see the other types of publications on this topic, follow the link: Oracle based algorithms.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Oracle based algorithms.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Zhao, Jiahao. "Possible Implementations of Oracles in Quantum Algorithms." Journal of Physics: Conference Series 2386, no. 1 (December 1, 2022): 012010. http://dx.doi.org/10.1088/1742-6596/2386/1/012010.
Full textAbstract:
Abstract Quantum computing is an inspiring technic on solving complicate problems, which shows the superiority over the classical computing. Contemporarily, the quantum-based algorithms were invented in many purposes on solving those problems. The thing is some of the algorithms were composed with oracles, which can be treated as a black box. It can be worked out/analyzed in theoretical mathematical expressions, but it can never fall in the ground without those actual implementations. Therefore, this paper will illustrate the idea and possible implementations on some quantum algorithm. Among various algorithms, this research will choose those relatively famous quantum algorithms, i.e., Deutsch-Jozsa Algorithm, Shor’s Algorithm, and Grover’s Algorithm. Different algorithms have the different intrinsic logics, which means there is no general description for all solution in this problem, but all of those can achieve the goal according to the same framework. Since those oracles are black boxes that can only be analyzed by its behavior with different cases, and then based on the behaviors and cases, and in IBM quantum platform, one can fill out the oracle by manipulate with different quantum operators. Lastly, the figures of some the possible implementation of those oracles with the three quantum algorithms will be shown in the IBM quantum platform, as well as the histograms of probability distributions that can justify the correctness of the implementations. These results shed light on guiding further exploration of the design and analysis on quantum algorithms.
2
Hou, Wenjun, and Marek Perkowski. "Quantum-based algorithm and circuit design for bounded Knapsack optimization problem." Quantum Information and Computation 20, no. 9&10 (August 2020): 766–86. http://dx.doi.org/10.26421/qic20.9-10-4.
Full textAbstract:
The Knapsack Problem is a prominent problem that is used in resource allocation and cryptography. This paper presents an oracle and a circuit design that verifies solutions to the decision problem form of the Bounded Knapsack Problem. This oracle can be used by Grover Search to solve the optimization problem form of the Bounded Knapsack Problem. This algorithm leverages the quadratic speed-up offered by Grover Search to achieve a quantum algorithm for the Knapsack Problem that shows improvement with regard to classical algorithms. The quantum circuits were designed using the Microsoft Q# Programming Language and verified on its local quantum simulator. The paper also provides analyses of the complexity and gate cost of the proposed oracle. The work in this paper is the first such proposed method for the Knapsack Optimization Problem.
3
Kämmerling, Nicolas, and Jannis Kurtz. "Oracle-based algorithms for binary two-stage robust optimization." Computational Optimization and Applications 77, no. 2 (June 23, 2020): 539–69. http://dx.doi.org/10.1007/s10589-020-00207-w.
Full textAbstract:
Abstract In this work we study binary two-stage robust optimization problems with objective uncertainty. We present an algorithm to calculate efficiently lower bounds for the binary two-stage robust problem by solving alternately the underlying deterministic problem and an adversarial problem. For the deterministic problem any oracle can be used which returns an optimal solution for every possible scenario. We show that the latter lower bound can be implemented in a branch and bound procedure, where the branching is performed only over the first-stage decision variables. All results even hold for non-linear objective functions which are concave in the uncertain parameters. As an alternative solution method we apply a column-and-constraint generation algorithm to the binary two-stage robust problem with objective uncertainty. We test both algorithms on benchmark instances of the uncapacitated single-allocation hub-location problem and of the capital budgeting problem. Our results show that the branch and bound procedure outperforms the column-and-constraint generation algorithm.
4
Zhandry, Mark. "Secure identity-based encryption in the quantum random oracle model." International Journal of Quantum Information 13, no. 04 (June 2015): 1550014. http://dx.doi.org/10.1142/s0219749915500148.
Full textAbstract:
We give the first proof of security for an identity-based encryption (IBE) scheme in the quantum random oracle model. This is the first proof of security for any scheme in this model that does not rely on the assumed existence of so-called quantum-secure pseudorandom functions (PRFs). Our techniques are quite general and we use them to obtain security proofs for two random oracle hierarchical IBE schemes and a random oracle signature scheme, all of which have previously resisted quantum security proofs, even assuming quantum-secure PRFs. We also explain how to remove quantum-secure PRFs from prior quantum random oracle model proofs. We accomplish these results by developing new tools for arguing that quantum algorithms cannot distinguish between two oracle distributions. Using a particular class of oracle distributions that we call semi-constant distributions, we argue that the aforementioned cryptosystems are secure against quantum adversaries.
5
Li, Liyi, Finn Voichick, Kesha Hietala, Yuxiang Peng, Xiaodi Wu, and Michael Hicks. "Verified compilation of Quantum oracles." Proceedings of the ACM on Programming Languages 6, OOPSLA2 (October 31, 2022): 589–615. http://dx.doi.org/10.1145/3563309.
Full textAbstract:
Quantum algorithms often apply classical operations, such as arithmetic or predicate checks, over a quantum superposition of classical data; these so-called oracles are often the largest components of a quantum program. To ease the construction of efficient, correct oracle functions, this paper presents VQO, a high-assurance framework implemented with the Coq proof assistant. The core of VQO is OQASM, the oracle quantum assembly language. OQASM operations move qubits between two different bases via the quantum Fourier transform, thus admitting important optimizations, but without inducing entanglement and the exponential blowup that comes with it. OQASM’s design enabled us to prove correct VQO’s compilers—from a simple imperative language called OQIMP to OQASM, and from OQASM to SQIR, a general-purpose quantum assembly language—and allowed us to efficiently test properties of OQASM programs using the QuickChick property-based testing framework. We have used VQO to implement a variety of arithmetic and geometric operators that are building blocks for important oracles, including those used in Shor’s and Grover’s algorithms. We found that VQO’s QFT-based arithmetic oracles require fewer qubits, sometimes substantially fewer, than those constructed using “classical” gates; VQO’s versions of the latter were nevertheless on par with or better than (in terms of both qubit and gate counts) oracles produced by Quipper, a state-of-the-art but unverified quantum programming platform.
6
Wang, Mengru, Yu Cai, Li Gao, Ruichen Feng, Qingju Jiao, Xiaolin Ma, and Yu Jia. "Study on the evolution of Chinese characters based on few-shot learning: From oracle bone inscriptions to regular script." PLOS ONE 17, no. 8 (August 19, 2022): e0272974. http://dx.doi.org/10.1371/journal.pone.0272974.
Full textAbstract:
Oracle bone inscriptions (OBIs) are ancient Chinese scripts originated in the Shang Dynasty of China, and now less than half of the existing OBIs are well deciphered. To date, interpreting OBIs mainly relies on professional historians using the rules of OBIs evolution, and the remaining part of the oracle’s deciphering work is stuck in a bottleneck period. Here, we systematically analyze the evolution process of oracle characters by using the Siamese network in Few-shot learning (FSL). We first establish a dataset containing Chinese characters which have finished a relatively complete evolution, including images in five periods: oracle bone inscriptions, bronze inscriptions, seal inscriptions, official script, and regular script. Then, we compare the performance of three typical algorithms, VGG16, ResNet, and AlexNet respectively, as the backbone feature extraction network of the Siamese network. The results show that the highest F1 value of 83.3% and the highest recognition accuracy of 82.67% are obtained by the combination of VGG16 and Siamese network. Based on the analysis, the typical structural performance of each period is evaluated and we identified that the optimized Siamese network is feasible to study the evolution of the OBIs. Our findings provide a new approach for oracle’s deciphering further.
7
Mirhosseini, Seyyed Mohsen, and Hassan Haghighi. "Application of the Shuffled Frog Leaping Algorithm (SFLA) in Constructing Fuzzy Classification Systems." International Journal of Computational Intelligence and Applications 18, no. 03 (September 2019): 1950019. http://dx.doi.org/10.1142/s1469026819500196.
Full textAbstract:
A Fuzzy Inference System (FIS) is a way of mapping an input space to an output space using the fuzzy logic. FISs are widely used to solve classification problems. The Shuffled Frog Leaping Algorithm (SFLA) is a metaheuristic inspired by the natural evolution of frogs in searching for the largest source of food. By using local and global searches simultaneously, SFLA is effective in solving various optimization problems. This paper first proposes a new method to create zero-order Sugeno Fuzzy Inference Systems using SFLA. Then, the paper introduces an approach to use resulting SFLA-based Fuzzy Inference Systems to build test oracles. Test oracle is a mechanism for determining whether a test on a software program has passed or failed. The experimental results show that SFLA creates fuzzy systems more efficiently than three other evolutionary algorithms, including Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO). Moreover, with respect to the accuracy and convergence speed criteria, SFLA and PSO outperform other evolutionary algorithms, while their performances are comparable to each other. At last, the experimental results indicate that SFLA-based FISs can be used to create test oracles with acceptable accuracy.
8
Paris, Matteo G. A., Claudia Benedetti, and Stefano Olivares. "Improving Quantum Search on Simple Graphs by Pretty Good Structured Oracles." Symmetry 13, no. 1 (January 7, 2021): 96. http://dx.doi.org/10.3390/sym13010096.
Full textAbstract:
Quantum search algorithms provide a way to speed up combinatorial search, and have found several applications in modern quantum technology. In particular, spatial search on graphs, based on continuous-time quantum walks (CTQW), represents a promising platform for the implementation of quantum search in condensed matter systems. CTQW-based algorithms, however, work exactly on complete graphs, while they are known to perform poorly on realistic graphs with low connectivity. In this paper, we put forward an alternative search algorithm, based on structuring the oracle operator, which allows one to improve the localization properties of the walker by tuning only the on-site energies of the graph, i.e., without altering its topology. As such, the proposed algorithm is suitable for implementation in systems with low connectivity, e.g., rings of quantum dots or superconducting circuits. Oracle parameters are determined by Hamiltonian constraints, without the need for numerical optimization.
9
Paris, Matteo G. A., Claudia Benedetti, and Stefano Olivares. "Improving Quantum Search on Simple Graphs by Pretty Good Structured Oracles." Symmetry 13, no. 1 (January 7, 2021): 96. http://dx.doi.org/10.3390/sym13010096.
Full textAbstract:
Quantum search algorithms provide a way to speed up combinatorial search, and have found several applications in modern quantum technology. In particular, spatial search on graphs, based on continuous-time quantum walks (CTQW), represents a promising platform for the implementation of quantum search in condensed matter systems. CTQW-based algorithms, however, work exactly on complete graphs, while they are known to perform poorly on realistic graphs with low connectivity. In this paper, we put forward an alternative search algorithm, based on structuring the oracle operator, which allows one to improve the localization properties of the walker by tuning only the on-site energies of the graph, i.e., without altering its topology. As such, the proposed algorithm is suitable for implementation in systems with low connectivity, e.g., rings of quantum dots or superconducting circuits. Oracle parameters are determined by Hamiltonian constraints, without the need for numerical optimization.
10
Yang, Zhen-Ping, Yuliang Wang, and Gui-Hua Lin. "Variance-Based Modified Backward-Forward Algorithm with Line Search for Stochastic Variational Inequality Problems and Its Applications." Asia-Pacific Journal of Operational Research 37, no. 03 (April 29, 2020): 2050011. http://dx.doi.org/10.1142/s0217595920500116.
Full textAbstract:
We propose a variance-based modified backward-forward algorithm with a stochastic approximation version of Armijo’s line search, which is robust with respect to an unknown Lipschitz constant, for solving a class of stochastic variational inequality problems. A salient feature of the proposed algorithm is to compute only one projection and two independent queries of a stochastic oracle at each iteration. We analyze the proposed algorithm for its asymptotic convergence, sublinear convergence rate in terms of the mean natural residual function, and optimal oracle complexity under moderate conditions. We also discuss the linear convergence rate with finite computational budget for the proposed algorithm without strong monotonicity. Preliminary numerical experiments indicate that the proposed algorithm is competitive with some existing algorithms. Furthermore, we consider an application in dealing with an equilibrium problem in stochastic natural gas trading market.
11
Shah, Dhruti, Tuhinangshu Choudhury, Nikhil Karamchandani, and Aditya Gopalan. "Sequential Mode Estimation with Oracle Queries." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 5644–51. http://dx.doi.org/10.1609/aaai.v34i04.6018.
Full textAbstract:
We consider the problem of adaptively PAC-learning a probability distribution 𝒫's mode by querying an oracle for information about a sequence of i.i.d. samples X1, X2, … generated from 𝒫. We consider two different query models: (a) each query is an index i for which the oracle reveals the value of the sample Xi, (b) each query is comprised of two indices i and j for which the oracle reveals if the samples Xi and Xj are the same or not. For these query models, we give sequential mode-estimation algorithms which, at each time t, either make a query to the corresponding oracle based on past observations, or decide to stop and output an estimate for the distribution's mode, required to be correct with a specified confidence. We analyze the query complexity of these algorithms for any underlying distribution 𝒫, and derive corresponding lower bounds on the optimal query complexity under the two querying models.
12
Yuan, Yunzhe, Yong Jiang, and Kewei Tu. "Bidirectional Transition-Based Dependency Parsing." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7434–41. http://dx.doi.org/10.1609/aaai.v33i01.33017434.
Full textAbstract:
Transition-based dependency parsing is a fast and effective approach for dependency parsing. Traditionally, a transitionbased dependency parser processes an input sentence and predicts a sequence of parsing actions in a left-to-right manner. During this process, an early prediction error may negatively impact the prediction of subsequent actions. In this paper, we propose a simple framework for bidirectional transitionbased parsing. During training, we learn a left-to-right parser and a right-to-left parser separately. To parse a sentence, we perform joint decoding with the two parsers. We propose three joint decoding algorithms that are based on joint scoring, dual decomposition, and dynamic oracle respectively. Empirical results show that our methods lead to competitive parsing accuracy and our method based on dynamic oracle consistently achieves the best performance.
13
Chen, Jian, Danni Wang, and Lin Qiao. "Implementation of micro application storage with high reliability based on Oracle 12c." MATEC Web of Conferences 272 (2019): 01053. http://dx.doi.org/10.1051/matecconf/201927201053.
Full textAbstract:
This paper proposes the implementation of data storage structure with high reliability based on the characteristics of Oracle 12c. On the basis of micro application platform, the main advantages of data structure works out active-active or multi-active problems of hardware storage device and ensures that the business can still be able to use data source to carry on data manipulation under the circumstances of one or multiple data sources corruption, so as to guarantee the whole business without interruption. This paper makes detailed introduction of each module in the system structure, conducts brief description, comparison and analysis on disseminating algorithm of data manipulation and comparison algorithm of the same data source, and carries on detailed proof and explanation of the use of various algorithms in the actual use procedure.
14
Addanki, Raghavendra, Sainyam Galhotra, and Barna Saha. "How to design robust algorithms using noisy comparison Oracle." Proceedings of the VLDB Endowment 14, no. 10 (June 2021): 1703–16. http://dx.doi.org/10.14778/3467861.3467862.
Full textAbstract:
Metric based comparison operations such as finding maximum, nearest and farthest neighbor are fundamental to studying various clustering techniques such as k -center clustering and agglomerative hierarchical clustering. These techniques crucially rely on accurate estimation of pairwise distance between records. However, computing exact features of the records, and their pairwise distances is often challenging, and sometimes not possible. We circumvent this challenge by leveraging weak supervision in the form of a comparison oracle that compares the relative distance between the queried points such as `Is point u closer to v or w closer to x ?'. However, it is possible that some queries are easier to answer than others using a comparison oracle. We capture this by introducing two different noise models called adversarial and probabilistic noise. In this paper, we study various problems that include finding maximum, nearest/farthest neighbor search under these noise models. Building upon the techniques we develop for these problems, we give robust algorithms for k -center clustering and agglomerative hierarchical clustering. We prove that our algorithms achieve good approximation guarantees with a high probability and analyze their query complexity. We evaluate the effectiveness and efficiency of our techniques empirically on various real-world datasets.
15
BEGGS, EDWIN J., JOSÉ FÉLIX COSTA, and JOHN V. TUCKER. "The impact of models of a physical oracle on computational power." Mathematical Structures in Computer Science 22, no. 5 (September 6, 2012): 853–79. http://dx.doi.org/10.1017/s0960129511000557.
Full textAbstract:
Using physical experiments as oracles for algorithms, we can characterise the computational power of classes of physical systems. Here we show that two different physical models of the apparatus for a single experiment can have different computational power. The experiment is thescatter machine experiment(SME), which was first presented in Beggs and Tucker (2007b). Our first physical model contained a wedge with a sharp vertex that made the experiment non-deterministic with constant runtime. We showed that Turing machines with polynomial time and an oracle based on a sharp wedge computed the non-uniform complexity classP/poly. Here we reconsider the experiment with a refined physical model where the sharp vertex of the wedge is replaced byanysuitable smooth curve with vertex at the same point. These smooth models of the experimental apparatus are deterministic. We show thatno matter what shape is chosen for the apparatus:(i)the time of detection of the scattered particles increases at least exponentially with the size of the query; and(ii)Turing machines with polynomial time and an oracle based on a smooth wedge compute the non-uniform complexity classP/log* ⫋P/poly.We discuss evidence that many experiments that measure quantities have exponential runtimes and a computational power ofP/log*.
16
Soni, Kapil Kumar, and Akhtar Rasool. "Quantum-effective exact multiple patterns matching algorithms for biological sequences." PeerJ Computer Science 8 (May 12, 2022): e957. http://dx.doi.org/10.7717/peerj-cs.957.
Full textAbstract:
This article presents efficient quantum solutions for exact multiple pattern matching to process the biological sequences. The classical solution takes Ο(mN) time for matching m patterns over N sized text database. The quantum search mechanism is a core for pattern matching, as this reduces time complexity and achieves computational speedup. Few quantum methods are available for multiple pattern matching, which executes search oracle for each pattern in successive iterations. Such solutions are likely acceptable because of classical equivalent quantum designs. However, these methods are constrained with the inclusion of multiplicative factor m in their complexities. An optimal quantum design is to execute multiple search oracle in parallel on the quantum processing unit with a single-core that completely removes the multiplicative factor m, however, this method is impractical to design. We have no effective quantum solutions to process multiple patterns at present. Therefore, we propose quantum algorithms using quantum processing unit with C quantum cores working on shared quantum memory. This quantum parallel design would be effective for searching all t exact occurrences of each pattern. To our knowledge, no attempts have been made to design multiple pattern matching algorithms on quantum multicore processor. Thus, some quantum remarkable exact single pattern matching algorithms are enhanced here with their equivalent versions, namely enhanced quantum memory processing based exact algorithm and enhanced quantum-based combined exact algorithm for multiple pattern matching. Our quantum solutions find all t exact occurrences of each pattern inside the biological sequence in $O((m/C)\sqrt{N})$ and $O((m/C)\sqrt{t})$ time complexities. This article shows the hybrid simulation of quantum algorithms to validate quantum solutions. Our theoretical–experimental results justify the significant improvements that these algorithms outperform over the existing classical solutions and are proven effective in quantum counterparts.
17
Chang, Seunghwan, Hyang-Sook Lee, Juhee Lee, and Seongan Lim. "Security Analysis of a Certificateless Signature from Lattices." Security and Communication Networks 2017 (2017): 1–7. http://dx.doi.org/10.1155/2017/3413567.
Full textAbstract:
Tian and Huang proposed a lattice-based CLS scheme based on the hardness of the SIS problem and proved, in the random oracle model, that the scheme is existentially unforgeable against strong adversaries. Their security proof uses the general forking lemma under the assumption that the underlying hash function H is a random oracle. We show that the hash function in the scheme is neither one-way nor collision-resistant in the view of a strong Type 1 adversary. We point out flaws in the security arguments and present attack algorithms that are successful in the strong Type 1 adversarial model using the weak properties of the hash function.
18
Shao, Changpeng. "Quantum speedup of training radial basis function networks." Quantum Information and Computation 19, no. 7&8 (June 2019): 609–25. http://dx.doi.org/10.26421/qic19.7-8-6.
Full textAbstract:
Radial basis function (RBF) network is a simple but useful neural network model that contains wide applications in machine learning. The training of an RBF network reduces to solve a linear system, which is time consuming classically. Based on HHL algorithm, we propose two quantum algorithms to train RBF networks. To apply the HHL algorithm, we choose using the Hamiltonian simulation algorithm proposed in [P. Rebentrost, A. Steffens, I. Marvian and S. Lloyd, Phys. Rev. A 97, 012327, 2018]. However, to use this result, an oracle to query the entries of the matrix of the network should be constructed. We apply the amplitude estimation technique to build this oracle. The final results indicate that if the centers of the RBF network are the training samples, then the quantum computer achieves exponential speedup at the number and the dimension of training samples over the classical computer; if the centers are determined by the K-means algorithm, then the quantum computer achieves quadratic speedup at the number of samples and exponential speedup at the dimension of samples.
19
Dohotaru, C., and P. Hoyer. "Exact quantum lower bound for Grover's problem." Quantum Information and Computation 9, no. 5&6 (May 2009): 533–40. http://dx.doi.org/10.26421/qic10.5-6-12.
Full textAbstract:
One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.
20
Dohotaru, C., and P. Hoyer. "Exact quantum lower bound for Grover's problem." Quantum Information and Computation 11, no. 5&6 (May 2009): 533–40. http://dx.doi.org/10.26421/qic9.5-6-12.
Full textAbstract:
One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.
21
Wang, Daochen, Xuchen You, Tongyang Li, and Andrew M. Childs. "Quantum Exploration Algorithms for Multi-Armed Bandits." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 11 (May 18, 2021): 10102–10. http://dx.doi.org/10.1609/aaai.v35i11.17212.
Full textAbstract:
Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we provide an algorithm to find the best arm with fixed confidence based on variable-time amplitude amplification and estimation. This algorithm gives a quadratic speedup compared to the best possible classical result in terms of query complexity. We also prove a matching quantum lower bound (up to poly-logarithmic factors).
22
Chakraborty, Sanjay, Soharab Hossain Shaikh, Sudhindu Bikash Mandal, Ranjan Ghosh, and Amlan Chakrabarti. "A study and analysis of a discrete quantum walk-based hybrid clustering approach using d-regular bipartite graph and 1D lattice." International Journal of Quantum Information 17, no. 02 (March 2019): 1950016. http://dx.doi.org/10.1142/s0219749919500163.
Full textAbstract:
Traditional machine learning shares several benefits with quantum information processing field. The study of machine learning with quantum mechanics is called quantum machine learning. Data clustering is an important tool for machine learning where quantum computing plays a vital role in its inherent speed up capability. In this paper, a hybrid quantum algorithm for data clustering (quantum walk-based hybrid clustering (QWBHC)) is introduced where one-dimensional discrete time quantum walks (DTQW) play the central role to update the positions of data points according to their probability distributions. A quantum oracle is also designed and it is mainly implemented on a finite [Formula: see text]-regular bipartite graph where data points are initially distributed as a predefined set of clusters. An overview of a quantum walk (QW) based clustering algorithm on 1D lattice structure is also introduced and described in this paper. In order to search the nearest neighbors, a unitary and reversible DTQW gives a quadratic speed up over the traditional classical random walk. This paper also demonstrates the comparisons of our proposed hybrid quantum clustering algorithm with some state-of-the-art clustering algorithms in terms of clustering accuracy and time complexity analysis. The proposed quantum oracle needs [Formula: see text] queries to mark the nearest data points among clusters and modify the existing clusters. Finally, the proposed QWBHC algorithm achieves [Formula: see text] performance.
23
Zhang, Youzhi, Bo An, and Jakub Černý. "Computing Ex Ante Coordinated Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 6 (May 18, 2021): 5813–21. http://dx.doi.org/10.1609/aaai.v35i6.16728.
Full textAbstract:
Computational game theory has many applications in the modern world in both adversarial situations and the optimization of social good. While there exist many algorithms for computing solutions in two-player interactions, finding optimal strategies in multiplayer interactions efficiently remains an open challenge. This paper focuses on computing the multiplayer Team-Maxmin Equilibrium with Coordination device (TMECor) in zero-sum extensive-form games. TMECor models scenarios when a team of players coordinates ex ante against an adversary. Such situations can be found in card games (e.g., in Bridge and Poker), when a team works together to beat a target player but communication is prohibited; and also in real world, e.g., in forest-protection operations, when coordinated groups have limited contact during interdicting illegal loggers. The existing algorithms struggle to find a TMECor efficiently because of their high computational costs. To compute a TMECor in larger games, we make the following key contributions: (1) we propose a hybrid-form strategy representation for the team, which preserves the set of equilibria; (2) we introduce a column-generation algorithm with a guaranteed finite-time convergence in the infinite strategy space based on a novel best-response oracle; (3) we develop an associated-representation technique for the exact representation of the multilinear terms in the best-response oracle; and (4) we experimentally show that our algorithm is several orders of magnitude faster than prior state-of-the-art algorithms in large games.
24
Teşileanu, Tiberiu, Siavash Golkar, Samaneh Nasiri, Anirvan M. Sengupta, and Dmitri B. Chklovskii. "Neural Circuits for Dynamics-Based Segmentation of Time Series." Neural Computation 34, no. 4 (March 23, 2022): 891–938. http://dx.doi.org/10.1162/neco_a_01476.
Full textAbstract:
Abstract The brain must extract behaviorally relevant latent variables from the signals streamed by the sensory organs. Such latent variables are often encoded in the dynamics that generated the signal rather than in the specific realization of the waveform. Therefore, one problem faced by the brain is to segment time series based on underlying dynamics. We present two algorithms for performing this segmentation task that are biologically plausible, which we define as acting in a streaming setting and all learning rules being local. One algorithm is model based and can be derived from an optimization problem involving a mixture of autoregressive processes. This algorithm relies on feedback in the form of a prediction error and can also be used for forecasting future samples. In some brain regions, such as the retina, the feedback connections necessary to use the prediction error for learning are absent. For this case, we propose a second, model-free algorithm that uses a running estimate of the autocorrelation structure of the signal to perform the segmentation. We show that both algorithms do well when tasked with segmenting signals drawn from autoregressive models with piecewise-constant parameters. In particular, the segmentation accuracy is similar to that obtained from oracle-like methods in which the ground-truth parameters of the autoregressive models are known. We also test our methods on data sets generated by alternating snippets of voice recordings. We provide implementations of our algorithms at https://github.com/ttesileanu/bio-time-series.
25
Ene, Alina, and Huy Lê Nguyễn. "Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 6 (June 28, 2022): 6559–67. http://dx.doi.org/10.1609/aaai.v36i6.20609.
Full textAbstract:
We develop new adaptive algorithms for variational inequalities with monotone operators, which capture many problems of interest, notably convex optimization and convex-concave saddle point problems. Our algorithms automatically adapt to unknown problem parameters such as the smoothness and the norm of the operator, and the variance of the stochastic evaluation oracle. We show that our algorithms are universal and simultaneously achieve the optimal convergence rates in the non-smooth, smooth, and stochastic settings. The convergence guarantees of our algorithms improve over existing adaptive methods and match the optimal non-adaptive algorithms. Additionally, prior works require that the optimization domain is bounded. In this work, we remove this restriction and give algorithms for unbounded domains that are adaptive and universal. Our general proof techniques can be used for many variants of the algorithm using one or two operator evaluations per iteration. The classical methods based on the ExtraGradient/MirrorProx algorithm require two operator evaluations per iteration, which is the dominant factor in the running time in many settings.
26
Hu, Yue, Daniel Harabor, Long Qin, and Quanjun Yin. "Regarding Goal Bounding and Jump Point Search." Journal of Artificial Intelligence Research 70 (February 10, 2021): 631–81. http://dx.doi.org/10.1613/jair.1.12255.
Full textAbstract:
Jump Point Search (JPS) is a well known symmetry-breaking algorithm that can substantially improve performance for grid-based optimal pathfinding. When the input grid is static further speedups can be obtained by combining JPS with goal bounding techniques such as Geometric Containers (instantiated as Bounding Boxes) and Compressed Path Databases. Two such methods, JPS+BB and Two-Oracle Path PlannING (Topping), are currently among the fastest known approaches for computing shortest paths on grids. The principal drawback for these algorithms is the overhead costs: each one requires an all-pairs precomputation step, the running time and subsequent storage costs of which can be prohibitive. In this work we consider an alternative approach where we precompute and store goal bounding data only for grid cells which are also jump points. Since the number of jump points is usually much smaller than the total number of grid cells, we can save up to orders of magnitude in preprocessing time and space.
Considerable precomputation savings do not necessarily mean performance degradation. For a second contribution we show how canonical orderings, partial expansion strategies and enhanced intermediate pruning can be leveraged to improve online query performance despite a reduction in preprocessed data. The combination of faster preprocessing and stronger online reasoning leads to three new and highly performant algorithms: JPS+BB+ and Two-Oracle Pathfinding Search (TOPS) based on search, and Topping+ based on path extraction. We give a theoretical analysis showing that each method is complete and optimal. We also report convincing gains in a comprehensive empirical evaluation that includes almost all current and cutting-edge algorithms for grid-based pathfinding.
27
Beggs, Edwin, José Félix Costa, Bruno Loff, and J. V. Tucker. "Computational complexity with experiments as oracles. II. Upper bounds." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, no. 2105 (February 25, 2009): 1453–65. http://dx.doi.org/10.1098/rspa.2008.0412.
Full textAbstract:
Earlier, to explore the idea of combining physical experiments with algorithms, we introduced a new form of analogue–digital (AD) Turing machine. We examined in detail a case study where an experimental procedure, based on Newtonian kinematics, is used as an oracle with classes of Turing machines. The physical cost of oracle calls was counted and three forms of AD queries were studied, in which physical parameters can be set exactly and approximately. Here, in this sequel, we complete the classification of the computational power of these AD Turing machines and determine precisely what they can compute, using non-uniform complexity classes and probabilities.
28
Dong, Minggang, Ning Wang, Xiaohui Cheng, and Chuanxian Jiang. "Composite Differential Evolution with Modified Oracle Penalty Method for Constrained Optimization Problems." Mathematical Problems in Engineering 2014 (2014): 1–15. http://dx.doi.org/10.1155/2014/617905.
Full textAbstract:
Motivated by recent advancements in differential evolution and constraints handling methods, this paper presents a novel modified oracle penalty function-based composite differential evolution (MOCoDE) for constrained optimization problems (COPs). More specifically, the original oracle penalty function approach is modified so as to satisfy the optimization criterion of COPs; then the modified oracle penalty function is incorporated in composite DE. Furthermore, in order to solve more complex COPs with discrete, integer, or binary variables, a discrete variable handling technique is introduced into MOCoDE to solve complex COPs with mix variables. This method is assessed on eleven constrained optimization benchmark functions and seven well-studied engineering problems in real life. Experimental results demonstrate that MOCoDE achieves competitive performance with respect to some other state-of-the-art approaches in constrained optimization evolutionary algorithms. Moreover, the strengths of the proposed method include few parameters and its ease of implementation, rendering it applicable to real life. Therefore, MOCoDE can be an efficient alternative to solving constrained optimization problems.
29
Asghar, Hassan Jameel, and Dali Kaafar. "Averaging Attacks on Bounded Noise-based Disclosure Control Algorithms." Proceedings on Privacy Enhancing Technologies 2020, no. 2 (April 1, 2020): 358–78. http://dx.doi.org/10.2478/popets-2020-0031.
Full textAbstract:
AbstractWe describe and evaluate an attack that reconstructs the histogram of any target attribute of a sensitive dataset which can only be queried through a specific class of real-world privacy-preserving algorithms which we call bounded perturbation algorithms. A defining property of such an algorithm is that it perturbs answers to the queries by adding zero-mean noise distributed within a bounded (possibly undisclosed) range. Other key properties of the algorithm include only allowing restricted queries (enforced via an online interface), suppressing answers to queries which are only satisfied by a small group of individuals (e.g., by returning a zero as an answer), and adding the same perturbation to two queries which are satisfied by the same set of individuals (to thwart differencing or averaging attacks). A real-world example of such an algorithm is the one deployed by the Australian Bureau of Statistics’ (ABS) online tool called TableBuilder, which allows users to create tables, graphs and maps of Australian census data [30]. We assume an attacker (say, a curious analyst) who is given oracle access to the algorithm via an interface. We describe two attacks on the algorithm. Both attacks are based on carefully constructing (different) queries that evaluate to the same answer. The first attack finds the hidden perturbation parameter r (if it is assumed not to be public knowledge). The second attack removes the noise to obtain the original answer of some (counting) query of choice. We also show how to use this attack to find the number of individuals in the dataset with a target attribute value a of any attribute A, and then for all attribute values ai ∈ A. None of the attacks presented here depend on any background information. Our attacks are a practical illustration of the (informal) fundamental law of information recovery which states that “overly accurate estimates of too many statistics completely destroys privacy” [9, 15].
30
Jarrar, Mustafa, and Anton Deik. "The Graph Signature." International Journal on Semantic Web and Information Systems 11, no. 2 (April 2015): 36–65. http://dx.doi.org/10.4018/ijswis.2015040102.
Full textAbstract:
Querying large data graphs has brought the attention of the research community. Many solutions were proposed, such as Oracle Semantic Technologies, Virtuoso, RDF3X, and C-Store, among others. Although such approaches have shown good performance in queries with medium complexity, they perform poorly when the complexity of the queries increases. In this paper, the authors propose the Graph Signature Index, a novel and scalable approach to index and query large data graphs. The idea is that they summarize a graph and instead of executing the query on the original graph, they execute it on the summaries. The authors' experiments with Yago (16M triples) have shown that e.g., a query with 4 levels costs 62 sec using Oracle but it only costs about 0.6 sec with their index. Their index can be implemented on top of any Graph database, but they chose to implement it as an extension to Oracle on top of the SEM_MATCH table function. The paper also introduces disk-based versions of the Trace Equivalence and Bisimilarity algorithms to summarize data graphs, and discusses their complexity and usability for RDF graphs.
31
Renner, Julian, Sven Puchinger, and Antonia Wachter-Zeh. "LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding." Designs, Codes and Cryptography 89, no. 6 (April 18, 2021): 1279–319. http://dx.doi.org/10.1007/s10623-021-00861-z.
Full textAbstract:
AbstractWe propose the new rank-metric code-based cryptosystem which is based on the hardness of list decoding and interleaved decoding of Gabidulin codes. is an improved variant of the Faure–Loidreau (FL) system, which was broken in a structural attack by Gaborit, Otmani, and Talé Kalachi (GOT, 2018). We keep the FL encryption and decryption algorithms, but modify the insecure key generation algorithm. Our crucial observation is that the GOT attack is equivalent to decoding an interleaved Gabidulin code. The new key generation algorithm constructs public keys for which all polynomial-time interleaved decoders fail—hence resists the GOT attack. We also prove that the public-key encryption version of is IND-CPA secure in the standard model and the key encapsulation mechanisms version is IND-CCA2 secure in the random oracle model, both under hardness assumptions of formally defined problems related to list decoding and interleaved decoding of Gabidulin codes. We propose and analyze various exponential-time attacks on these problems, calculate their work factors, and compare the resulting parameters to NIST proposals. The strengths of are short ciphertext sizes and (relatively) small key sizes. Further, guarantees correct decryption and has no decryption failure rate. It is not based on hiding the structure of a code. Since there are efficient and constant-time algorithms for encoding and decoding Gabidulin codes, timing attacks on the encryption and decryption algorithms can be easily prevented.
32
Dress, Andreas, Stefan Grünewald, and Zhenbing Zeng. "A cognitive network for oracle bone characters related to animals." International Journal of Modern Physics B 30, no. 04 (February 10, 2016): 1630001. http://dx.doi.org/10.1142/s0217979216300012.
Full textAbstract:
In this paper, we present an analysis of oracle bone characters for animals from a “cognitive” point of view. After some general remarks on oracle-bone characters presented in Sec. 1 and a short outline of the paper in Sec. 2, we collect various oracle-bone characters for animals from published resources in Sec. 3. In the next section, we begin analyzing a group of 60 ancient animal characters from www.zdic.net , a highly acclaimed internet dictionary of Chinese characters that is strictly based on historical sources, and introduce five categories of specific features regarding their (graphical) structure that will be used in Sec. 5 to associate corresponding feature vectors to these characters. In Sec. 6, these feature vectors will be used to investigate their dissimilarity in terms of a family of parameterized distance measures. And in the last section, we apply the SplitsTree method as encoded in the NeighborNet algorithms to construct a corresponding family of dissimilarity-based networks with the intention of elucidating how the ancient Chinese might have perceived the “animal world” in the late bronze age and to demonstrate that these pictographs reflect an intuitive understanding of this world and its inherent structure that predates its classification in the oldest surviving Chinese encyclopedia from approximately the third century BC, the Er Ya, as well as similar classification systems in the West by one to two millennia. We also present an English dictionary of 70 oracle bone characters for animals in Appendix A. In Appendix B, we list various variants of animal characters that were published in the Jia Gu Wen Bian (cf. 甲骨文编, A Complete Collection of Oracle Bone Characters, edited by the Institute of Archaeology of the Chinese Academy of Social Sciences, published by the Zhonghua Book Company in 1965). We recall the frequencies of the 521 most frequent oracle bone characters in Appendix C as reported in [T. Chen, Yin-Shang Jiaguwen Zixing Xitong Zai Yanjiu, (The Structural System of Oracle Inscriptions) (Shanghai Renmin Chubanshe, Shanghai, 2010); Jiaguwen Shiwen Yongzi Pinlü Biao (A Frequency List of Oracle Characters), Center for the Study and Application of Chinese Characters (East China Normal University, Shanghai, 2010), http://www.wenzi.cn/en/default.aspx . And in Appendix D, we list the animals registered in the last five chapters of the Er Ya.
33
Liu, Hui, Fukun Li, and Yilin Fan. "Optimizing the Quantum Circuit for Solving Boolean Equations Based on Grover Search Algorithm." Electronics 11, no. 15 (August 8, 2022): 2467. http://dx.doi.org/10.3390/electronics11152467.
Full textAbstract:
The solution of nonlinear Boolean equations in a binary field plays a crucial part in cryptanalysis and computational mathematics. To speed up the process of solving Boolean equations is an urgent task that needs to be addressed. In this paper, we propose a method for solving Boolean equations based on the Grover algorithm combined with preprocessing using classical algorithms, optimizing the quantum circuit for solving the equations, and implementing the automatic generation of quantum circuits. The method first converted Boolean equations into Boolean expressions to construct the oracle in the Grover algorithm. The quantum circuit was emulated based on the IBM Qiskit framework and then simulated the Grover algorithm on this basis. Finally, the solution of the Boolean equation was implemented. The experimental results proved the feasibility of using the Grover algorithm to solve nonlinear Boolean equations in a binary field, and the correct answer was successfully found under the conditions that the search space was 221 and three G iterations were used. The method in this paper increases the solving scale and solving speed of Boolean equations and enlarges the application area of the Grover algorithm.
34
Ben-David, Noa, and Sivan Sabato. "A Fast Algorithm for PAC Combinatorial Pure Exploration." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 6 (June 28, 2022): 6064–71. http://dx.doi.org/10.1609/aaai.v36i6.20553.
Full textAbstract:
We consider the problem of Combinatorial Pure Exploration (CPE), which deals with finding a combinatorial set of arms with a high reward, when the rewards of individual arms are unknown in advance and must be estimated using arm pulls. Previous algorithms for this problem, while obtaining sample complexity reductions in many cases, are highly computationally intensive, thus making them impractical even for mildly large problems. In this work, we propose a new CPE algorithm in the PAC setting, which is computationally light weight, and so can easily be applied to problems with tens of thousands of arms. This is achieved since the proposed algorithm requires a very small number of combinatorial oracle calls. The algorithm is based on successive acceptance of arms, along with elimination which is based on the combinatorial structure of the problem. We provide sample complexity guarantees for our algorithm, and demonstrate in experiments its usefulness on large problems, whereas previous algorithms are impractical to run on problems of even a few dozen arms. The code is provided at https://github.com/noabdavid/csale. The full version of this paper is available at https://arxiv.org/abs/2112.04197.
35
Ferrari, Davide, and Michele Amoretti. "Efficient and effective quantum compiling for entanglement-based machine learning on IBM Q devices." International Journal of Quantum Information 16, no. 08 (December 2018): 1840006. http://dx.doi.org/10.1142/s0219749918400063.
Full textAbstract:
Quantum compiling means fast, device-aware implementation of quantum algorithms (i.e. quantum circuits, in the quantum circuit model of computation). In this paper, we present a strategy for compiling IBM Q-aware, low-depth quantum circuits that generate Greenberger–Horne–Zeilinger (GHZ) entangled states. The resulting compiler can replace the QISKit compiler for the specific purpose of obtaining improved GHZ circuits. It is well known that GHZ states have several practical applications, including quantum machine learning. We illustrate our experience in implementing and querying a uniform quantum example oracle based on the GHZ circuit, for solving the classically hard problem of learning parity with noise.
36
MEER, KLAUS. "SOME INITIAL THOUGHTS ON BOUNDED QUERY COMPUTATIONS OVER THE REALS." International Journal of Foundations of Computer Science 23, no. 07 (November 2012): 1499–510. http://dx.doi.org/10.1142/s0129054112400618.
Full textAbstract:
A classical theme in recursion theory is the question whether for a set A and n given elements x1,…,xn, an oracle machine having access to an oracle B can determine which of the elements xi belong to A. And if yes, how many queries are necessary? Here, B = A is possible and leads to interesting special cases of the general question In the present paper we adapt classical notions in this area of bounded query computations to real number algorithms as formalized by Blum, Shub, and Smale and analyze them in the new framework. Among the results obtained we find: A real version of a non-speedup theorem based on real quantifier elimination, some basic properties about selective real sets, and a way to construct natural terse sets in ℝ by applying the implicit function theorem. The purpose of the paper is on presenting some interesting questions and basic results as an appertizer to intensify research into this direction.
37
Ye, Honghan, Xinyuan Wei, Xindong Zhuang, and Enming Miao. "An Improved Robust Thermal Error Prediction Approach for CNC Machine Tools." Machines 10, no. 8 (July 29, 2022): 624. http://dx.doi.org/10.3390/machines10080624.
Full textAbstract:
Thermal errors significantly affect the accurate performance of computer numerical control (CNC) machine tools. In this paper, an improved robust thermal error prediction approach is proposed for CNC machine tools based on the adaptive Least Absolute Shrinkage and Selection Operator (LASSO) and eXtreme Gradient Boosting (XGBoost) algorithms. Specifically, the adaptive LASSO method enjoys the oracle property of selecting temperature-sensitive variables. After the temperature-sensitive variable selection, the XGBoost algorithm is further adopted to model and predict thermal errors. Since the XGBoost algorithm is decision tree based, it has natural advantages to address the multicollinearity and provide interpretable results. Furthermore, based on the experimental data from the Vcenter-55 type 3-axis vertical machining center, the proposed algorithm is compared with benchmark methods to demonstrate its superior performance on prediction accuracy with 7.05 μm (over 14.5% improvement), robustness with 5.61 μm (over 12.9% improvement), worst-case scenario predictions with 16.49 μm (over 25.0% improvement), and percentage errors with 13.33% (over 10.7% improvement). Finally, the real-world applicability of the proposed model is verified through thermal error compensation experiments.
38
Riccio, Vincenzo, Gunel Jahangirova, Andrea Stocco, Nargiz Humbatova, Michael Weiss, and Paolo Tonella. "Testing machine learning based systems: a systematic mapping." Empirical Software Engineering 25, no. 6 (September 15, 2020): 5193–254. http://dx.doi.org/10.1007/s10664-020-09881-0.
Full textAbstract:
Abstract Context: A Machine Learning based System (MLS) is a software system including one or more components that learn how to perform a task from a given data set. The increasing adoption of MLSs in safety critical domains such as autonomous driving, healthcare, and finance has fostered much attention towards the quality assurance of such systems. Despite the advances in software testing, MLSs bring novel and unprecedented challenges, since their behaviour is defined jointly by the code that implements them and the data used for training them. Objective: To identify the existing solutions for functional testing of MLSs, and classify them from three different perspectives: (1) the context of the problem they address, (2) their features, and (3) their empirical evaluation. To report demographic information about the ongoing research. To identify open challenges for future research. Method: We conducted a systematic mapping study about testing techniques for MLSs driven by 33 research questions. We followed existing guidelines when defining our research protocol so as to increase the repeatability and reliability of our results. Results: We identified 70 relevant primary studies, mostly published in the last years. We identified 11 problems addressed in the literature. We investigated multiple aspects of the testing approaches, such as the used/proposed adequacy criteria, the algorithms for test input generation, and the test oracles. Conclusions: The most active research areas in MLS testing address automated scenario/input generation and test oracle creation. MLS testing is a rapidly growing and developing research area, with many open challenges, such as the generation of realistic inputs and the definition of reliable evaluation metrics and benchmarks.
39
Eufinger, Lars, Jannis Kurtz, Christoph Buchheim, and Uwe Clausen. "A Robust Approach to the Capacitated Vehicle Routing Problem with Uncertain Costs." INFORMS Journal on Optimization 2, no. 2 (January 2020): 79–95. http://dx.doi.org/10.1287/ijoo.2019.0021.
Full textAbstract:
We investigate a robust approach for solving the capacitated vehicle routing problem (CVRP) with uncertain travel times. It is based on the concept of K-adaptability, which allows one to calculate a set of k feasible solutions in a preprocessing phase before the scenario is revealed. Once a scenario occurs, the corresponding best solution may be picked out of the set of candidates. The aim is to determine the k candidates by hedging against the worst-case scenario, as is common in robust optimization. This idea leads to a min-max-min problem. In this paper, we propose an oracle-based algorithm for solving the resulting min-max-min CVRP, calling an exact algorithm for the deterministic problem in each iteration. Moreover, we adjust this approach such that heuristics for the CVRP can also be used. In this way, we derive a heuristic algorithm for the min-max-min problem, which turns out to yield good solutions in a short running time. All algorithms are tested on standard benchmark instances of the CVRP.
40
Van Aken, Dana, Dongsheng Yang, Sebastien Brillard, Ari Fiorino, Bohan Zhang, Christian Bilien, and Andrew Pavlo. "An inquiry into machine learning-based automatic configuration tuning services on real-world database management systems." Proceedings of the VLDB Endowment 14, no. 7 (March 2021): 1241–53. http://dx.doi.org/10.14778/3450980.3450992.
Full textAbstract:
Modern database management systems (DBMS) expose dozens of configurable knobs that control their runtime behavior. Setting these knobs correctly for an application's workload can improve the performance and efficiency of the DBMS. But because of their complexity, tuning a DBMS often requires considerable effort from experienced database administrators (DBAs). Recent work on automated tuning methods using machine learning (ML) have shown to achieve better performance compared with expert DBAs. These ML-based methods, however, were evaluated on synthetic workloads with limited tuning opportunities, and thus it is unknown whether they provide the same benefit in a production environment. To better understand ML-based tuning, we conducted a thorough evaluation of ML-based DBMS knob tuning methods on an enterprise database application. We use the OtterTune tuning service to compare three state-of-the-art ML algorithms on an Oracle installation with a real workload trace. Our results with OtterTune show that these algorithms generate knob configurations that improve performance by 45% over enterprise-grade configurations. We also identify deployment and measurement issues that were overlooked by previous research in automated DBMS tuning services.
41
Yang, Nan, and Youliang Tian. "Identity-Based Unidirectional Collusion-Resistant Proxy Re-Encryption from U-LWE." Security and Communication Networks 2023 (January 3, 2023): 1–9. http://dx.doi.org/10.1155/2023/3765934.
Full textAbstract:
Identity-based proxy re-encryption (IB-PRE) converts the ciphertext encrypted under the delegator’s identity to the one encrypted under the delegatee’s identity through a semitrusted proxy without leaking delegator’s private key and the underlying plaintext. At present, the security of most IB-PRE schemes relies on the hardness of the discrete logarithm solution or large integer decomposition and cannot resist attacks of the quantum algorithms. The majority of the IB-PRE schemes over lattice are secure only in the random oracle model. Aiming at such problems, the paper constructs a secure IB-PRE scheme over lattice in the standard model. In the scheme, the underlying encryption scheme proposed by Gentry et al. in EUROCRYPT 2010 is adopted to reduce the storage space of ciphertext. The proposed scheme is unidirectional collusion-resistant multihop and anonymous, and it is semantically secure against selective identity and chosen plaintext attack based on Decisional Learning With Errors with uniformly distributed errors (D-U-LWE) hard problem in the standard model.
42
Xie, Yi-Yang, Xiu-Bo Chen, and Yi-Xian Yang. "A New Lattice-Based Blind Ring Signature for Completely Anonymous Blockchain Transaction Systems." Security and Communication Networks 2022 (September 1, 2022): 1–12. http://dx.doi.org/10.1155/2022/4052029.
Full textAbstract:
Blockchain technology has been widely applied in numerous industries with its decentralization, verifiability, distributivity, and immutability. However, the identity privacy security of blockchain users is facing serious threats because of the openness of traditional blockchain transaction information. Moreover, numerous traditional cryptographic algorithms used by blockchain transaction networks are difficult to attack quantum computing. In this paper, we propose a new lattice-based blind ring signature scheme in allusion to completely anonymous blockchain transaction systems. There into, the blind ring signature can implement the complete anonymity of user identity privacy in blockchain transactions. Meanwhile, lattice cryptography can availably resist quantum computing attacks. Firstly, the proposed signature scheme has strong computational security based on the small integer solution (SIS) problem and a high sampling success rate by utilizing the techniques of rejection sampling from bimodal Gaussian distribution. Secondly, the proposed signature scheme can satisfy the correctness and security under the random oracle model, including anonymity, blindness, and one-more unforgeability. Thirdly, we construct a blockchain transaction system based on the proposed blind ring signature algorithm, which realizes the completely anonymous and antiquantum computing security of the blockchain users’ identity privacy. Finally, the performance evaluation results show that our proposed blind ring signature scheme has lower latency, smaller key size, and signature size than other similar schemes.
43
Huixian, Li, Gao Jin, Wang Lingyun, and Pang Liaojun2. "MPKC-based Threshold Proxy Signcryption Scheme." International Arab Journal of Information Technology 17, no. 2 (February 28, 2019): 196–206. http://dx.doi.org/10.34028/iajit/17/2/7.
Full textAbstract:
The threshold proxy signcryption can implement signature and encryption simultaneously in one logical step, and can be used to realize the decentralized protection of the group signature key, so it is an efficient technology for network security. Currently, most of the existing threshold proxy signcryption schemes are designed based on the traditional public key cryptosystems, and their security mainly depends on the difficulty of the large integer decomposition and the discrete logarithm. However, the traditional public key cryptosystems cannot resist the quantum computer attack, which makes the existing threshold proxy signcryption schemes based on traditional public key cryptosystems insecure against quantum attacks. Motivated by these concerns, we proposed a threshold proxy signcryption scheme based on Multivariate Public Key Cryptosystem (MPKC) which is one of the quantum attack-resistent public key algorithms. Under the premise of satisfying the threshold signcryption requirements of the threshold proxy, our scheme can not only realize the flexible participation of the proxy signcrypters but also resist the quantum computing attack. Finally, based on the assumption of Multivariate Quadratic (MQ) problem and Isomorphism Polynomial (IP) problem, the proof of the confidentiality and the unforgeability of the proposed scheme under the random oracle model is given.
44
Zhou, Xiaoli, Hongqiang Wang, Yongqiang Cheng, Yuliang Qin, and Haowen Chen. "Radar Coincidence Imaging for Off-Grid Target Using Frequency-Hopping Waveforms." International Journal of Antennas and Propagation 2016 (2016): 1–16. http://dx.doi.org/10.1155/2016/8523143.
Full textAbstract:
Radar coincidence imaging (RCI) is a high-resolution staring imaging technique without the limitation of the target relative motion. To achieve better imaging performance, sparse reconstruction is commonly used. While its performance is based on the assumption that the scatterers are located at the prediscretized grid-cell centers, otherwise, off-grid emerges and the performance of RCI degrades significantly. In this paper, RCI using frequency-hopping (FH) waveforms is considered. The off-grid effects are analyzed, and the corresponding constrained Cramér-Rao bound (CCRB) is derived based on the mean square error (MSE) of the “oracle” estimator. For off-grid RCI, the process is composed of two stages: grid matching and off-grid error (OGE) calibration, where two-dimension (2D) band-excluded locally optimized orthogonal matching pursuit (BLOOMP) and alternating iteration minimization (AIM) algorithms are proposed, respectively. Unlike traditional sparse recovery methods, BLOOMP realizes the recovery in the refinement grids by overwhelming the shortages of coherent dictionary and is robust to noise and OGE. AIM calibration algorithm adaptively adjusts the OGE and, meanwhile, seeks the optimal target reconstruction result.
45
Grottoli, Marco, Diane Cleij, Paolo Pretto, Yves Lemmens, Riender Happee, and Heinrich H. Bülthoff. "Objective evaluation of prediction strategies for optimization-based motion cueing." SIMULATION 95, no. 8 (December 6, 2018): 707–24. http://dx.doi.org/10.1177/0037549718815972.
Full textAbstract:
Optimization-based motion cueing algorithms based on model predictive control have been recently implemented to reproduce the motion of a car within the limited workspace of a driving simulator. These algorithms require a reference of the future vehicle motion to compute a prediction of the system response. Assumptions regarding the future reference signals must be made in order to develop effective prediction strategies. However, it remains unclear how the prediction of future vehicle dynamics influences the quality of the motion cueing. In this study two prediction strategies are considered. Oracle: the ideal prediction strategy that knows exactly what the future reference is going to be. Constant: a prediction strategy that ignores every future change and keeps the current vehicle’s linear accelerations and angular velocities constant. The two prediction strategies are used to reproduce a sequence of maneuvers between 0 and 50 km/h. A comparative analysis is carried out to objectively evaluate the influence of the prediction strategies on motion cueing quality. Dedicated indicators of correlation, delay and absolute error are used to compare the effects of the adopted prediction on simulator motion. Also the motion cueing mechanisms adopted by the different conditions are analyzed, together with the usage of simulator workspace. While the constant strategy provided reasonable cueing quality, the results show that knowledge of the future vehicle trajectory reduces the delay and improves correlation with the reference trajectory, it allows the combined usage of different motion cueing mechanisms and increases the usage of workspace.
46
Choudhury, Sanjiban, Mohak Bhardwaj, Sankalp Arora, Ashish Kapoor, Gireeja Ranade, Sebastian Scherer, and Debadeepta Dey. "Data-driven planning via imitation learning." International Journal of Robotics Research 37, no. 13-14 (July 12, 2018): 1632–72. http://dx.doi.org/10.1177/0278364918781001.
Full textAbstract:
Robot planning is the process of selecting a sequence of actions that optimize for a task=specific objective. For instance, the objective for a navigation task would be to find collision-free paths, whereas the objective for an exploration task would be to map unknown areas. The optimal solutions to such tasks are heavily influenced by the implicit structure in the environment, i.e. the configuration of objects in the world. State-of-the-art planning approaches, however, do not exploit this structure, thereby expending valuable effort searching the action space instead of focusing on potentially good actions. In this paper, we address the problem of enabling planners to adapt their search strategies by inferring such good actions in an efficient manner using only the information uncovered by the search up until that time. We formulate this as a problem of sequential decision making under uncertainty where at a given iteration a planning policy must map the state of the search to a planning action. Unfortunately, the training process for such partial-information-based policies is slow to converge and susceptible to poor local minima. Our key insight is that if we could fully observe the underlying world map, we would easily be able to disambiguate between good and bad actions. We hence present a novel data-driven imitation learning framework to efficiently train planning policies by imitating a clairvoyant oracle: an oracle that at train time has full knowledge about the world map and can compute optimal decisions. We leverage the fact that for planning problems, such oracles can be efficiently computed and derive performance guarantees for the learnt policy. We examine two important domains that rely on partial-information-based policies: informative path planning and search-based motion planning. We validate the approach on a spectrum of environments for both problem domains, including experiments on a real UAV, and show that the learnt policy consistently outperforms state-of-the-art algorithms. Our framework is able to train policies that achieve up to [Formula: see text] more reward than state-of-the art information-gathering heuristics and a [Formula: see text] speedup as compared with A* on search-based planning problems. Our approach paves the way forward for applying data-driven techniques to other such problem domains under the umbrella of robot planning.
47
GOMES, ANA SOFIA, JOSÉ JÚLIO ALFERES, and TERRANCE SWIFT. "A goal-directed implementation of query answering for hybrid MKNF knowledge bases." Theory and Practice of Logic Programming 14, no. 2 (January 18, 2013): 239–64. http://dx.doi.org/10.1017/s1471068412000439.
Full textAbstract:
AbstractOntologies and rules are usually loosely coupled in knowledge representation formalisms. In fact, ontologies use open-world reasoning, while the leading semantics for rules use non-monotonic, closed-world reasoning. One exception is the tightly coupled framework of Minimal Knowledge and Negation as Failure (MKNF), which allows statements about individuals to be jointly derived via entailment from ontology and inferences from rules. Nonetheless, the practical usefulness of MKNF has not always been clear, although recent work has formalized a general resolution-based method for querying MKNF when rules are taken to have the well-founded semantics, and the ontology is modeled by a general oracle. That work leaves open what algorithms should be used to relate the entailments of the ontology and the inferences of rules. In this paper we provide such algorithms, and describe the implementation of a query-driven system, CDF-Rules, for hybrid knowledge bases combining both (non-monotonic) rules under the well-founded semantics and a (monotonic) ontology, represented by the Coherent Description Framework Type-1 ($\mathcal{ALCQ}$) theory.
48
Li, Cheng, Wenxin Jiang, and Martin A. Tanner. "GENERAL INEQUALITIES FOR GIBBS POSTERIOR WITH NONADDITIVE EMPIRICAL RISK." Econometric Theory 30, no. 6 (April 16, 2014): 1247–71. http://dx.doi.org/10.1017/s0266466614000152.
Full textAbstract:
The Gibbs posterior is a useful tool for risk minimization, which adopts a Bayesian framework and can incorporate convenient computational algorithms such as Markov chain Monte Carlo. We derive risk bounds for the Gibbs posterior using some general nonasymptotic inequalities, which can be used to derive nearly optimal convergence rates and select models to optimally balance the approximation errors and the stochastic errors. These inequalities are formulated in a very general way that does not require the empirical risk to be a usual sample average over independent observations. We apply this framework to study the convergence rate of the GMM (generalized method of moments) risk and derive an oracle inequality for the ranking risk, where models are selected based on the Gibbs posterior with a nonadditive empirical risk.
49
Gao, Peng, Yiwei Li, Marek Perkowski, and Xiaoyu Song. "Realization of Quantum Oracles using Symmetries of Boolean Functions." Quantum Information and Computation 20, no. 5&6 (May 2020): 418–48. http://dx.doi.org/10.26421/qic20.5-6-4.
Full textAbstract:
Designing a quantum oracle is an important step in practical realization of Grover algorithm, therefore it is useful to create methodologies to design oracles. Lattice diagrams are regular two-dimensional structures that can be directly mapped onto a quantum circuit. We present a quantum oracle design methodology based on lattices. The oracles are designed with a proposed method using generalized Boolean symmetric functions realized with lattice diagrams. We also present a decomposition-based algorithm that transforms non-symmetric functions into symmetric or partially symmetric functions. Our method, which combines logic minimization, logic decomposition, and mapping, has lower quantum cost with fewer ancilla qubits. Overall, we obtain encouraging synthesis results superior to previously published data.
50
Hu, Huidan, Yuanjian Zhou, Zhenfu Cao, and Xiaolei Dong. "Efficient and HRA Secure Universal Conditional Proxy Re-Encryption for Cloud-Based Data Sharing." Applied Sciences 12, no. 19 (September 24, 2022): 9586. http://dx.doi.org/10.3390/app12199586.
Full textAbstract:
Cloud computing has become popular in data sharing mainly because it has huge storage capacity and computing power. Securing the privacy of sensitive data for cloud-based data sharing is vital. Currently, there are various conditional proxy re-encryption (UPRE) schemes that have been proposed to resolve the privacy issue. Nevertheless, the existing UPRE schemes cannot allow the proxy (e.g., the cloud server) to transfer the outsourced encrypted data under the data owner’s public key of any homomorphic encryption scheme into the encrypted data under the data user’s public key of a homomorphic encryption scheme (possibly different from the data owner). The transformation of outsourced encrypted data between homomorphic encryption schemes is more suitable for the real data sharing in clouds. Consequently, we present the notion of universal conditional proxy re-encryption (UCPRE) to solve the issue of flexible transformation of outsourced encrypted data between homomorphic encryption schemes in cloud-based data sharing. UCPRE is lightweight in the sense that it only requires the re-encrypted key generation and re-encryption algorithms. We give the definition of UCPRE and prove that it is HRA secure without random oracle. Finally, we show that our UCPRE is efficient and rational compared to other existing CPRE schemes by instantiating our UCPRE.