检索结果-内蒙古大学图书馆

An Affine Equivalence algorithm for S-boxes based on Matrix Invariants

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hu, Xincheng Zeng, Xiao Liu, Zhaoqiang Yang, Guowu School of Computer Science and Engineering University of Electronic Science and Technology of China Chengdu611731 China

We investigate the affine equivalence (AE) problem of S-boxes. Given two S-boxes denoted as S1 and S2, we aim to seek two invertible AE transformations A,B such that S1 O A = B O S2 holds. Due to important applications in the analysis and design of block ciphers, the investigation of AE algorithms has performed growing significance. In this paper, we propose zeroization on S-box firstly, and the AE problem can be transformed into 2n linear equivalence problems by this zeroization oper- ation. Secondly, we propose standard orthogonal spatial matrix (SOSM), and the rank of the SOSM is invariant under AE transformations. Finally, based on the zeroization operation and the SOSM method, we propose a depth first search (DFS) method for determining AE of S-boxes, named the AE SOSM DFS algo- rithm. Using this matrix invariant, we optimize the temporal complexity of the algorithm to approximately 1 2n of the complexity without SOSM. Specifically, the complexity of our algorithm is O(23n). In addition, we also conducted exper- iments with non-invertible S-boxes, and the performance is similar to that of invertible S-boxes. Moreover, our proposed algorithm can effectively handle S- boxes with low algebraic degree or certain popular S-boxes such as namely AES and ARIA s2, which are difficult to be handled by the algorithm proposed by Dinur (2018). Using our algorithm, it only takes 5.5 seconds to find out that the seven popular S-boxes namely AES, ARIA s2, Camellia, Chiasmus, DBlock, SEED S0, and SMS4 are affine equivalent and the AE transformations of these S-boxes are provided. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

A Policy Iteration algorithm for N-player General-Sum Linear Quadratic Dynamic Games

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Guan, Yuxiang Salizzoni, Giulio Kamgarpour, Maryam Summers, Tyler H. The Control Optimization and Networks Lab University of Texas at Dallas United States The Systems Control and Multi-Agent Optimization Research Lab EPFL Switzerland

We present a policy iteration algorithm for the infinite-horizon N-player general-sum deterministic linear quadratic dynamic games and compare it to policy gradient methods. We demonstrate that the proposed policy iteration algorithm is distinct from the Gauss-Newton policy gradient method in the N-player game setting, in contrast to the single-player setting where under suitable choice of step size they are equivalent. We illustrate in numerical experiments that the convergence rate of the proposed policy iteration algorithm significantly surpasses that of the Gauss-Newton policy gradient method and other policy gradient variations. Furthermore, our numerical results indicate that, compared to policy gradient methods, the convergence performance of the proposed policy iteration algorithm is less sensitive to the initial policy and changes in the number of players. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

HEX: Hierarchical Emergence Exploitation in Self-Supervised algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kokilepersaud, Kiran Kim, Seulgi Prabhushankar, Mohit AlRegib, Ghassan OLIVES The Center for Signal and Information Processing CSIP School of Electrical and Computer Engineering Georgia Institute of Technology AtlantaGA United States

In this paper, we propose an algorithm that can be used on top of a wide variety of self-supervised (SSL) approaches to take advantage of hierarchical structures that emerge during training. SSL approaches typically work through some invariance term to ensure consistency between similar samples and a regularization term to prevent global dimensional collapse. Dimensional collapse refers to data representations spanning a lower-dimensional subspace. Recent work has demonstrated that the representation space of these algorithms gradually reflects a semantic hierarchical structure as training progresses. Data samples of the same hierarchical grouping tend to exhibit greater dimensional collapse locally compared to the dataset as a whole due to sharing features in common with each other. Ideally, SSL algorithms would take advantage of this hierarchical emergence to have an additional regularization term to account for this local dimensional collapse effect. However, the construction of existing SSL algorithms does not account for this property. To address this, we propose an adaptive algorithm that performs a weighted decomposition of the denominator of the InfoNCE loss into two terms: local hierarchical and global collapse regularization respectively. This decomposition is based on an adaptive threshold that gradually lowers to reflect the emerging hierarchical structure of the representation space throughout training. It is based on an analysis of the cosine similarity distribution of samples in a batch. We demonstrate that this hierarchical emergence exploitation (HEX) approach can be integrated across a wide variety of SSL algorithms. Empirically, we show performance improvements of up to 5.6% relative improvement over baseline SSL approaches on classification accuracy on Imagenet with 100 epochs of training. © 2024, CC BY.

关键词： consensus algorithm

Optimal bounds on a tree inference algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Gardiner, Jack Andrew, Lachlan L.H. Gan, Junhao Honorio, Jean Umboh, Seeun William School of Computing and Information Systems University of Melbourne Australia

This paper tightens the best known analysis of Hein’s 1989 algorithm to infer the topology of a weighted tree based on the lengths of paths between its leaves. It shows that the number of length queries required for a degree-k tree of n leaves is O(nk logk n), which is the lower bound. It also presents a family of trees for which the performance is asymptotically better, and shows that no such family exists for a competing O(nk logk n) algorithm. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

A Fully-dynamic Approximation algorithm for Maximum Weight b-Matchings in Graphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Brandt-Tumescheit, Fabian Gerharz, Frieda Meyerhenke, Henning Humboldt-Universität Berlin Germany

Matching nodes in a graph G = (V,E) is a well-studied algorithmic problem with many applications. The b-matching problem is a generalization that allows to match a node with up to b neighbors. This allows more flexible connectivity patterns whenever vertices may have multiple associations. The algorithm b-suitor [Khan et al., SISC 2016] is able to compute a (1/2)-approximation of a maximum weight b-matching in O(|E|) time. Since real-world graphs often change over time, fast dynamic methods for b-matching optimization are desirable. In this work, we propose Dyn-b-suitor, a dynamic algorithm for the weighted b-matching problem. As a non-trivial extension to the dynamic Suitor algorithm for 1-matchings [Angriman et al., JEA 2022], our approach computes (1/2)-approximate b-matchings by identifying and updating affected vertices without static recomputation. Our proposed algorithm is fully-dynamic, i. e., it supports both edge insertions and deletions, and we prove that it computes the same solution as its static counterpart. In extensive experiments on real-world benchmark graphs and generated instances, our dynamic algorithm yields significant savings compared to the sequential b-suitor, e. g., for batch updates with 103 edges with an average acceleration factor of 103×. When comparing our sequential dynamic algorithm with the parallel (static) b-suitor on a 128-core machine, our dynamic algorithm is still 59× to 104× faster. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

A SIMPLE UNIVERSAL algorithm FOR HIGH-DIMENSIONAL INTEGRATION

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Goda, Takashi Krieg, David Graduate School of Engineering The University of Tokyo Japan Department of Mathematics University of Passau Germany

We present a simple universal algorithm for high-dimensional integration which has the optimal error rate (independent of the dimension) in all weighted Korobov classes both in the randomized and the deterministic setting. Our theoretical findings are complemented by numerical *** Codes 65D30 (Primary) 41A25, 41A63, 46E35, 65C05 (Secondary) Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Maximum Nim and Josephus Problem algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Takahashi, Shoei Manabe, Hikaru Miyadera, Ryohei Sasaki, Yuji Tokuni, Yuki Keimei Gakuin Junior and High School Kobe Japan Graduate School of Advanced Science and Engineering Hiroshima University Higashi-Hiroshima City Japan Keio University Faculty of Environment and Information Studies Fujisawa Japan Graduate School of Information Science University of Hyogo Kobe Japan

Let k, n be positive integers such that n, k ≥ 2. We present a new algorithm to determine the last number that remains in the Josephus problem, where numbers 1, 2, . . ., n are arranged in a circle, and every k-th number is removed. We discovered a new formula that calculates the last number that remains in the Josephus problem, and this formula is based on a Maximum Nim of combinatorial game theory. When k ≤ n, the time complexity of our algorithm is O(k log n), which is on par with the existing O(k log n) algorithm. We do not have any recursion overhead or stack overflow because we do not use any recursion. Therefore, the space complexity of our algorithm is O(1), and ours is better than the existing O(k log n) algorithm in this respect. The algorithm is as follows. (i) We start with x = k − 1. (ii) We substitute x with x + ⌊jxk−1⌋ + 1 until we get x such nk − n ≤ x. (iii) Then, nk − x is the number that *** Codes 91A46, 91A05 © 2024, CC BY.

关键词： consensus algorithm

Hybrid Model using LOF and iForest algorithms for Detection of Insider Threats

学校读者我要写书评

暂无评论

TechRxiv

TechRxiv 2024年

作者： Mahajan, Anvita Ajay COEP Technological University Pune India

Insider threats, is one of the most challenging threats in cyberspace, usually responsible for causing significant loss to *** topic of insider threats has long been studied and many detection techniques were proposed to deal with insider threats. This paper focuses on using different anomaly detection algorithms- Locality Outlier Factor algorithm and Isolation forest algorithm and does a comparative analysis between their performance. A hybrid model incorporating advantages of both LOF algorithm and IF algorithm is proposed in this paper which gives better performance than the individual models for detecting insider threats. The hybrid model was able to achieve whooping 99.99% accuracy while detecting insider threats. © 2024, CC BY.

关键词： consensus algorithm

Eliminating Majority Illusion is Easy

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dippel, Jack la Tour, Max Dupré Niu, April Roy, Sanjukta Vetta, Adrian McGill University Canada University of Leeds United Kingdom

Majority Illusion is a phenomenon in social networks wherein the decision by the majority of the network is not the same as one's personal social circle's majority, leading to an incorrect perception of the majority in a large network. In this paper, we present polynomial-time algorithms which can eliminate majority illusion in a network by altering as few connections as possible. Additionally, we prove that the more general problem of ensuring all neighbourhoods in the network are at least a p-fraction of the majority is NP-hard for most values of p. © 2024, CC BY.

关键词： consensus algorithm