| viXra.org > Data Structures and Algorithms > 2307 |
 |
 |
| viXra.org > Data Structures and Algorithms > 2307 |
|
|
[5] viXra:2307.0148 [pdf] submitted on 2023-07-27 12:41:11
Authors: Matthew Stephenson
Comments: 11 Pages.
The core reasoning task for datalog engines is materialization, the evaluation of a datalog program over a database alongside its physical incorporation into the database itself. The de-facto method of computing it, is through the recursive application of inference rules. Due to it being a costly operation, it is a must for datalog engines to provide incremental materialization, that is, to adjustthe computation to new data, instead of restarting from scratch. One of the major caveats, is that deleting data is notoriously more involved than adding, since one has to take into account all possible data that has been entailed from what is being deleted. DifferentialDataflow is a computational model that provides efficient incremental maintenance, notoriously with equal performance between additions and deletions, and work distribution, of iterative dataflows. In this paper we investigate the performance of materialization with three reference datalog implementations, out of which one is built on top of a lightweight relational engine, and the two others are differential-dataflow and non-differential versions of the same rewrite algorithm, with the same optimizations.
Category: Data Structures and Algorithms
[4] viXra:2307.0103 [pdf] submitted on 2023-07-19 09:08:03
Authors: Antonio Viggiano
Comments: 5 Pages. DeFi Security Summit, July 15-16, 2023, Paris, France
This study presents a comparative analysis of randomized testing algorithms, commonly known as fuzzers, with a specific emphasis on their effectiveness in catching bugs in Solidity smart contracts. We employ the non-parametric Mann-Whitney U-test to gauge performance, defined as the ``time to break invariants per mutant'', using altered versions of the widely-forked Uniswap v2 protocol. We conduct 30 tests, each with a maximum duration of 24 hours or 4,294,967,295 runs, and evaluate the speed at which the fuzzers Foundry and Echidna can breach any of the 22 protocol's invariant properties for each of the 12 mutants, created both with mutation testing tools and with manual bug injection methods. The research shows significant performance variabilities between runs for both Foundry and Echidna depending on the instances of mutated code. Our analysis indicates that Foundry was able to break invariants faster in 9 out of 12 tests, while Echidna in 1 out of 12 tests, and in the remaining 2 tests, the difference in performance between the two fuzzers was not statistically significant. The paper concludes by emphasizing the necessity for further research to incorporate additional fuzzers and real-world bugs, and paves ground for further developments of more precise and rigorous evaluations of fuzzer effectiveness.
Category: Data Structures and Algorithms
[3] viXra:2307.0088 [pdf] submitted on 2023-07-17 15:06:38
Authors: Mirzakhmet Syzdykov
Comments: 2 Pages.
We present the continuation of studying Extended Regular Expression (ERE) on the view ofmodified subset construction within the overridden operators like intersection, subtraction, and re-written complement. As before we have stated that in this case the complexity has a decreasing nature and tendency. We will give the strict definition of the operational part of this modified subset construction which is due to Rabin and Scott. The complexity of algorithm remains a magnitude less than NP-hard problems for which we have given the strict proof of equivalence in the prior work, so this work continues the studying of the comparable proof for a variety of problems to be computationally complex, however, explainable in terms of unified approach like operational calculus. In this calculus the general points of research are given to the representation of modified subset construction with at least two operands which are to be computed by subsetconstruction and in terms of complexity of the effective algorithm they are computed using modified subset construction.
Category: Data Structures and Algorithms
[2] viXra:2307.0061 [pdf] submitted on 2023-07-12 17:31:17
Authors: Mirzakhmet Syzdykov
Comments: 1 Page.
We present a polynomial time algorithm for producing the final graph where the minimal Hamiltonian cycle exists. Thus, proving that P = NP.
Category: Data Structures and Algorithms
[1] viXra:2307.0031 [pdf] submitted on 2023-07-07 03:24:16
Authors: Sunny Daniels
Comments: 5 Pages. "Complexity Theory" would almost certainly be the best arXiv category for this paper, but there doesn't seem to be any corresponding viXra category.
I appreciate the acknowledgement by Fortnow[1] of my, historically significant, I believe, first ever constructive proof of Kannan’s theorem[2], which I think was acknowledged as "folklore" (I thank Watanabe for this) in Watanabe[3] (I don’t think I currently have access to any university library system so I don’t think I currently have access to the full text of this). If I am not mistaken, I now have a much simpler construction (I thought of this years ago if I remember rightly but was a bit too busy with an IT job unrelated to complexity theory until recently to have the time to publish it) giving a constructive proof of Kannan’s theorem, based upon a particular type of universal Turing machine. The fact that this construction (if I am not mistaken) works is an easy consequence of either my earlier constructive proof[2] or Watanabe’s later proof of the same result as discussed by Fortnow[1]. (I know that my presentations here of this construction and proof are quite sketchy at present; I would appreciate some feedback from others before attempting to write up more detailed versions of them). Also, I think it can be used as the basis of a much simpler constructive proof of Kannan’s theorem: I also discuss this here.
Category: Data Structures and Algorithms
| Third-Party Links: |
|