16 research outputs found
Pinning down the Strong Wilber 1 Bound for Binary Search Trees
Full text linkThe dynamic optimality conjecture, postulating the existence of an O(1)-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. Despite extensive work and some notable progress, including, for example, the Tango Trees (Demaine et al., FOCS 2004), that give the best currently known O(log log n)-competitive algorithm, the conjecture remains widely open. One of the main hurdles towards settling the conjecture is that we currently do not have approximation algorithms achieving better than an O(log log n)-approximation, even in the offline setting. All known non-trivial algorithms for BST’s so far rely on comparing the algorithm’s cost with the so-called Wilber’s first bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right.
Our contribution is two-fold. First, we show that the gap between the WB-1 bound and the optimal solution value can be as large as Ω(log log n/ log log log n); in fact, we show that the gap holds even for several stronger variants of the bound. Second, we provide a simple algorithm, that, given an integer D > 0, obtains an O(D)-approximation in time exp (O (n^{1/2^{Ω(D)}}log n)). In particular, this yields a constant-factor approximation algorithm with sub-exponential running time. Moreover, we obtain a simpler and cleaner efficient O(log log n)-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call the Guillotine Bound, that is stronger than WB-1, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis
Improved ciphertext-policy time using short elliptic curve Diffie–Hellman
Get PDFCiphertext-policy attribute-based encryption (CP-ABE) is a suitable solution for the protection of data privacy and security in cloud storage services. In a CP-ABE scheme which provides an access structure with a set of attributes, users can decrypt messages only if they receive a key with the desired attributes. As the number of attributes increases, the security measures are strengthened proportionately, and they can be applied to longer messages as well. The decryption of these ciphertexts also requires a large decryption key which may increase the decryption time. In this paper, we proposed a new method for improving the access time to the CP using a new elliptic curve that enables a short key size to be distributed to the users that allows them to use the defined attributes for encryption and decryption. Each user has a specially created key which uses the defined attributes for encryption and decryption based on the Diffie-Hellman method. After the implement, the results show that this system saves nearly half of the execution time for encryption and decryption compared to previous methods. This proposed system provides guaranteed security by means of the elliptic curve discrete logarithmic problem
Comparative study of password storing using hash function with MD5, SHA1, SHA2, and SHA3 algorithm
Get PDFThe main purpose of passwords is to prevent unauthorized people from accessing the system. The rise in internet users has led to an increase in password hacking, which has resulted in a variety of problems. These issues include opponents stealing a company's or nation's private information and harming the economy or the organization's security. Password hacking is a common tool used by hackers for illegal purposes. Password security against hackers is essential. There are several ways to hack passwords, including traffic interception, social engineering, credential stuffing, and password spraying. In an attempt to prevent hacking, hashing algorithms are therefore mostly employed to hash passwords, making password cracking more difficult. In the suggested work, several hashing techniques, including message digest (MD5), secure hash algorithms (SHA1, SHA2, and SHA3) have been used. They have become vulnerable as a result of being used to store passwords. A rainbow table attack is conceivable. Passwords produced with different hash algorithms can have their hash values attacked with the help of the Hashcat program. It is proven that the SHA3 algorithm can help with more secure password storage when compared to other algorithms
Smart tourism application: towards software development for artificial intelligence in tourism management
Full text linkArtificial intelligence (AI) can manage tourism by optimizing, personalizing the experience, and enhancing user interactions. This research presents the Ayutthaya tourism platform independent model (ATPiM), an intelligent tourism application that integrates a domain-specific language (DSL) designed for chatbot development with machine learning algorithms that generate personalized recommendations based on user preferences, historical data, and real-time contextual influences. This pre-experimental design measures performance on parameters such as response time, recommendation accuracy, and system latency. The outcomes indicate that the mean time taken to respond to a user's query was 2.3 seconds, with 88.5% recommendation accuracy, and no latency. The AI-based recommendation system achieved 89.7% accuracy at destinations, 87.2% at accommodations, 90.3% at itineraries, and 85.6% at activities, with corresponding recalls of 85.4%, 83.5%, 88.1%, and 80.2% respectively. Although these results are promising, a 6.2% error rate for the advanced search, along with data security are some of the remaining issues. The findings reveal that the development of new user-centric and sustainable solutions for tourism, which leverage state-of-the-art natural language processing approaches, can enhance data security and provide additional new technologies, such as augmented reality (AR) and blockchain, for use in tourism
Are corruption, demographic pressures and brain drain damaging the quality of education? Evidence from Asia
No full textThe importance of education cannot be denied in any region of the world because it is the aspect on which the future and growth of the country is based. There are many aspects that are found to have impacts on quality of education, however in this study; the author has used corruption, demographic pressure and brain drain along with control variables i.e. population and per capita income and the impacts of all the above mentioned variables on quality of education have been studied. The approaches such as unit root test, cointegration test and coefficient estimation test have been used by the author for the data analysis purpose. The author has found out the order of integration, cointegrated relationships presence as well as their measurement by using all these approaches. The data in this case was collected from eight countries of Asian region for 26 years and the above-mentioned tests were run on it. The results obtained indicate that corruption and brain drain have significant impact on quality of education along with the control variables, population and per capita income. The author has also discussed some theoretical, practical and policy making implications and some of the limitations of this study
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: {C}lique, Dominating Set, and More
No full textWe consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms. The questions, which have been asked several times, are whether there is a nontrivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT)poly(N) time and outputs a solution of size f(OPT) for any computable functions t and f that are independent of N (for Clique, we want f (OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no nontrivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f (OPT)-FPT-approximation algorithm for DomSet for any function f. In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis [I. Dinur. ECCC, TR16-128, 2016; P. Manurangsi and P. Raghavendra, preprint, arXiv:1607.02986, 2016], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3 SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out nontrivial FPT-approximation for the Maximum Biclique problem, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs, and we rule out the k(o(1))-FPT-approximation algorithm for the Densest k-Subgraph problem.Peer reviewe
Simplicity in Eulerian circuits : Uniqueness and safety
No full textFunding Information: We are very grateful to the anonymous reviewers who helped improved the presentation of this paper. This work was partially funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 851093 , SAFEBIO) and partially by the Academy of Finland (grants No. 322595 , 328877 , 314284 and 335715 ). Publisher Copyright: © 2023 The Author(s)An Eulerian circuit in a directed graph is one of the most fundamental Graph Theory notions. Detecting if a graph G has a unique Eulerian circuit can be done in polynomial time via the BEST theorem by de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte (1941–1951) [15,16] (involving counting arborescences), or via a tailored characterization by Pevzner, 1989 (involving computing the intersection graph of simple cycles of G), both of which thus rely on overly complex notions for the simpler uniqueness problem. In this paper we give a new linear-time checkable characterization of directed graphs with a unique Eulerian circuit. This is based on a simple condition of when two edges must appear consecutively in all Eulerian circuits, in terms of cut nodes of the underlying undirected graph of G. As a by-product, we can also compute in linear-time all maximal safe walks appearing in all Eulerian circuits, for which Nagarajan and Pop proposed in 2009 [12] a polynomial-time algorithm based on Pevzner characterization.Peer reviewe
ColorMod: Recoloring 3D Printed Objects using Photochromic Inks
No full text© 2018 Copyright is held by the owner/author(s). Recent research has shown how to change the color of existing objects using photochromic materials. These materials can switch their appearance from transparent to colored when exposed to light of a certain wavelength. The color remains active even when the object is removed from the light source. The process is fully reversible allowing users to recolor the object as many times as they want. So far, these systems have been limited to single color changes, i.e. changes from transparent to colored. In this paper, we present ColorMod, a method to extend this approach to multi-color changes (e.g., red-to-yellow). We accomplish this using a multi-color pattern with one color per voxel across the surface of the object. When recoloring the object, our system locally activates only those voxels that have the desired color and turns all other voxels off. We describe ColorMod's hardware/software system and its user interface. The user interface comes with a conversion tool for 3D printing and a painting tool for matching physical voxels with the desired appearance. We also provide our own material formula for a 3D-printable photochromic ink.Japan Society for the Promotion of Science. Grant-in-Aid for Scientific Research (grant number 16J00049
A Deterministic {PTAS} for the Algebraic Rank of Bounded Degree Polynomials
No full textWe present a deterministic polynomial time approximation scheme (PTAS) for computing the algebraic rank of a set of bounded degree polynomials. The notion of algebraic rank naturally generalizes the notion of rank in linear algebra, i.e., instead of considering only the linear dependencies, we also consider higher degree algebraic dependencies among the input polynomials. More specifically, we give an algorithm that takes as input a set f:= {f1, . . ., fn} ⊂ F[x1, . . ., xm] of polynomials with degrees bounded by d, and a rational number > 0 and runs in time O((nmd )O(d 2) • M(n)), where M(n) is the time required to compute the rank of an n × n matrix (with field entries), and finally outputs a number r, such that r is at least (1 − ) times the algebraic rank of f. Our key contribution is a new technique which allows us to achieve the higher degree generalization of the results by Bläser, Jindal, Pandey (CCC’17) who gave a deterministic PTAS for computing the rank of a matrix with homogeneous linear entries. It is known that a deterministic algorithm for exactly computing the rank in the linear case is already equivalent to the celebrated Polynomial Identity Testing (PIT) problem which itself would imply circuit complexity lower bounds (Kabanets, Impagliazzo, STOC’03). Such a higher degree generalization is already known to a much stronger extent in the noncommutative world, where the more general case in which the entries of the matrix are given by poly-sized formulas reduces to the case where the entries are given by linear polynomials using Higman’s trick, and in the latter case, one can also compute the exact rank in polynomial time (Garg, Gurvits, Oliviera, Wigderson, FOCS’16, Ivanyos, Qiao, Subrahmanyam, ITCS’17). Higman’s trick only preserves the co-rank, hence it cannot be used to reduce the problem of rank approximation to the case when the matrix entries are linear polynomials. Thus our work can also be seen as a step towards bridging the knowledge gap between the non-commutative world and the commutative world.Peer reviewe
On the Complexity of Symmetric Polynomials
Full text linkThe fundamental theorem of symmetric polynomials states that for a symmetric polynomial f_{Sym} in C[x_1,x_2,...,x_n], there exists a unique "witness" f in C[y_1,y_2,...,y_n] such that f_{Sym}=f(e_1,e_2,...,e_n), where the e_i's are the elementary symmetric polynomials.
In this paper, we study the arithmetic complexity L(f) of the witness f as a function of the arithmetic complexity L(f_{Sym}) of f_{Sym}. We show that the arithmetic complexity L(f) of f is bounded by poly(L(f_{Sym}),deg(f),n). To the best of our knowledge, prior to this work only exponential upper bounds were known for L(f). The main ingredient in our result is an algebraic analogue of Newton's iteration on power series. As a corollary of this result, we show that if VP != VNP then there exist symmetric polynomial families which have super-polynomial arithmetic complexity.
Furthermore, we study the complexity of testing whether a function is symmetric. For polynomials, this question is equivalent to arithmetic circuit identity testing. In contrast to this, we show that it is hard for Boolean functions
