Персона: Куприяшин, Михаил Андреевич
Email Address
Birth Date
Результаты поиска
Using statistical analysis to fine-tune the results of knapsack-based computational platform benchmarking
© 2019 IEEE In previous papers, we composed an algorithmic foundation for computational platform benchmarking of well-known exact algorithms for the Knapsack Problem. We suggested using the run time of these algorithms with fixed inputs as the performance estimates. We then derived a single performance estimate, equally impacted by each of the algorithms. Although this approach makes for a reasonable general-purpose benchmark, equalizing the impact of different algorithms is not completely legitimate, as they have different processing requirements. In this paper, we perform an in-depth analysis of algorithm operational requirements and try to fine-tune the integral estimates to describe special-purpose (e.g. data compression or encipherment/decipherment) platforms more accurately.
Overview of Lattice-Based Methods in Cryptanalysis
© 2020 IEEE.In this paper, we give a short introduction to the hard lattice problems and application of corresponding methods in cryptanalysis. We provide several examples of specialized lattices we may use to solve certain instances of the related tasks, such as the Knapsack Problem or the Learning with Errors Problem. In this study, we pay special attention to using lattice-based cryptanalysis with asymmetric Knapsack-based cipher systems.
Analysis and optimization of the packing tree search algorithm for the knapsack problem
© 2019 IEEE The Packing Tree Search algorithm proved to be one of the best exact algorithms for the Knapsack Problem in cryptography: while free from the memory-related limitations of the Horowitz-Sahni list merging algorithm, it still offers a significant performance boost if compared to the Exhaustive Search algorithm. The algorithm also seems to be scalable, albeit the parallel computation efficiency may be as low as 50-60%. In this paper, we consider improvements to the base algorithm to reduce its complexity. In particular, we study the dynamic packing weight calculation, the replacement of stack-based and linearization-based tree traversal techniques with faster step-based traversal routines and substitution of the original problem instance with the conjugate in case it reduces the complexity. In conclusion, we analyze the impact of these improvements on the acceleration and efficiency of parallel computation.
Statistical Analysis of Binary Vector Enumeration Methods in Combinatorial Optimization
© 2020 IEEE.In this paper, we review and analyze the efficiency of several binary vector enumeration algorithms we have been using in our work on the Knapsack Problem. As we keep in mind the possibility of massively parallel computation, we are interested in algorithms that are able to start the search from any vector (identified by ordinal number). In this case, it is possible to implement static load balancing efficiently. Apart from the actual implementation performance, we study the load balancing diagrams for each of the algorithms. We assume that every bit of the binary vector is associated with some fixed amount of work a computer must do and examine the resulting complexity of subtasks obtained by splitting the vector sequences into subsequences.
On using gray codes to improve the efficiency of the parallel exhaustive search algorithm for the knapsack problem
© 2019 IEEE In previous papers, we stated that splitting the lexicographic sequence into equal parts does not yield uniform workload distribution for a parallel computational system. One of the options we have considered is breaking the packing vectors space into classes based on the vectors' Hamming weight, and then split each of the classes into equal parts. In this paper, we investigate another load balancing technique based on using the Gray codes instead of the lexicographic sequence. As only one element of the packing changes on every step, we can calculate the packing weight dynamically. Thus, the time needed to weigh a packing becomes both shorter and more uniform. We study the properties of the Gray codes and analyze their impact on the algorithm run time and efficiency of parallel computation.