Search

Recent rank-based attacks have reduced the security of Rainbow, which is one of the multi-layer UOV signatures, below the NIST security requirements by speeding up iterative kernel-finding operations using classical mathematics techniques. If quantum algorithms are applied to perform these iterative operations, the rank-based attacks may be more threatening to multi-layer UOV, including Rainbow. In this paper, we propose a quantum rectangular MinRank attack called the Q-rMinRank attack, the first quantum approach to key recovery attacks on multi-layer UOV signatures. Our attack is a general model applicable to multi-layer UOV signature schemes, and in this paper, we provide examples of its application to Rainbow and the Korean TTA standard, HiMQ. We design two quantum oracle circuits to find the kernel in consideration of the depth-width trade-off of quantum circuits. One is to reduce the width of the quantum circuits using qubits as a minimum, and the other is to reduce the depth using parallelization instead of using a lot of qubits. By designing quantum circuits to find kernels with fewer quantum resources and complexity by adding mathematical techniques, we achieve quadratic speedup for the MinRank attack to recover the private keys of multi-layer UOV signatures. We also estimate quantum resources for the designed quantum circuits and analyze quantum complexity based on them. The width-optimized circuit recovers the private keys of Rainbow parameter set V with only 1089 logical qubits. The depth-optimized circuit recovers the private keys of Rainbow parameter set V with a quantum complexity of 2 174 , which is lower than the complexity of 2 221 recovering the secret key of AES-192, which provides the same security level as parameter set III. [ABSTRACT FROM AUTHOR]

The higher-order guaranteed lower eigenvalue bounds of the Laplacian in the recent work by Carstensen et al. (Numer Math 149(2):273–304, 2021) require a parameter C st , 1 that is found not robust as the polynomial degree p increases. This is related to the H 1 stability bound of the L 2 projection onto polynomials of degree at most p and its growth C st, 1 ∝ (p + 1) 1 / 2 as p → ∞ . A similar estimate for the Galerkin projection holds with a p-robust constant C st , 2 and C st , 2 ≤ 2 for right-isosceles triangles. This paper utilizes the new inequality with the constant C st , 2 to design a modified hybrid high-order eigensolver that directly computes guaranteed lower eigenvalue bounds under the idealized hypothesis of exact solve of the generalized algebraic eigenvalue problem and a mild explicit condition on the maximal mesh-size in the simplicial mesh. A key advance is a p-robust parameter selection. The analysis of the new method with a different fine-tuned volume stabilization allows for a priori quasi-best approximation and improved L 2 error estimates as well as a stabilization-free reliable and efficient a posteriori error control. The associated adaptive mesh-refining algorithm performs superior in computer benchmarks with striking numerical evidence for optimal higher empirical convergence rates. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) A = (A α β x α β) , where A α β is a 2 × 2 matrix over a field F and x α β is an indeterminate for α = 1 , 2 , ⋯ , μ and β = 1 , 2 , ⋯ , ν . This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (SIAM J Matrix Anal Appl 16(3):719–734, 1995). Recent interests in this problem lie in the connection with non-commutative Edmonds' problem by Ivanyos et al. (Comput Complex 27:561–593, 2018) and Garg et al. (Found. Comput. Math. 20:223–290, 2020), where a result by Iwata and Murota implicitly states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a simple and combinatorial O ((μ ν) 2 min { μ , ν }) -time algorithm for computing the symbolic rank of a (2 × 2) -type generic partitioned matrix of size 2 μ × 2 ν . Our algorithm is inspired by the Wong sequence algorithm by Ivanyos et al. for the nc-rank of a general symbolic matrix, and requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of A for an arbitrary field F . [ABSTRACT FROM AUTHOR]

Theory of quasi-orthogonal polynomials is significantly related to constructing vector Padé approximations. The present paper introduces an efficient procedure to compute adjacent families of quasi-orthogonal polynomials as defined in Sadaka (Appl. Numer. Math. 21:57–70, 1996) and Sadaka (Appl. Numer. Math. 24:483–499, 1997). The derived algorithm uses short recursive relations whose coefficients are written in terms of lower triangular block determinants. The strategy of computing such determinants is given and analyzed. [ABSTRACT FROM AUTHOR]

Traditional blood flow mapping algorithms are not effective enough when the region of interest contains the sources of artifacts. This paper examines the signatures of blood flow signals, as well as noise and artifact signals. Mathematical rules are proposed on the basis of these features to discriminate the blood flow signal from other signals, including the Doppler twinkling artifact. The diagnostic efficiency of the proposed decision rules is assessed using the previously collected database of raw ultrasound Doppler signals. The study results showed that taking account of the spatial stability of blood flow velocity can increase diagnostic efficiency to 91.6%. [ABSTRACT FROM AUTHOR]

A recent paper by Schulze et al. (Math Methods Oper Res 92(1):107–132, 2020) presented the Rectangular Knapsack Problem (Rkp) as a crucial subproblem in the study on the Cardinality-constrained Bi-objective Knapsack Problem (Cbkp). To this end, they started an investigation into its complexity and approximability. The key results are an NP -hardness proof for a more general scenario than Rkp, and a 4.5-approximation for Rkp, raising the question of improvements for either result. In this note we settle both questions conclusively: we show that (a) Rkp is indeed NP -hard in the considered setting (and even in more restricted settings), and (b) there exists both a pseudopolynomial algorithm and a fully-polynomial time approximation scheme (i.e., efficient approximability within any desired ratio α > 1 ) for Rkp. [ABSTRACT FROM AUTHOR]

This paper proposes an innovative statistical method to measure the impact of the class/school on student achievements in multiple subjects. We propose a semiparametric model for a bivariate response variable with random coefficients, that are assumed to follow a discrete distribution with an unknown number of support points, together with an Expectation-Maximization algorithm—called BSPEM algorithm—to estimate its parameters. In the case study, we apply the BSPEM algorithm to data about Italian middle schools, considering students nested within classes, and we identify subpopulations of classes, standing on their effects on student achievements in reading and mathematics. The proposed model is extremely informative in exploring the correlation between multiple class effects, which are typical of the educational production function. The estimated class effects on reading and mathematics student achievements are then explained in terms of various class and school level characteristics selected by means of a LASSO regression. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new iterative algorithm and analyze it in detail inasmuch as convergence, stability, and data dependency for the class of almost contraction mappings. We also consider another iterative algorithm called F ∗ iterative algorithm proposed by Ali et al. (Comp. Appl. Math. 39, 267 (2020)) and derive some new algorithms from this with the aim of giving an affirmative answer to an open question raised by the same authors. Our results considerably improve the corresponding results in Ali et al. (Comp. Appl. Math. 39, 267 (2020)). We submit some non-trivial numerical examples to illustrate the robustness, feasibility, and effectiveness of our findings. [ABSTRACT FROM AUTHOR]

The research of medical image in the field of anti-counterfeiting and authentication plays a crucial role in the development of hospital digitization. In this paper, a new fragile medical watermarking scheme is proposed using the prime number distribution theorem, chaotic mapping, and Hash. Firstly, an approximate pixel set is constructed according to the distribution of prime numbers, and then the parity of the pixel value is re-granted with chaotic mapping, and Hash. The embedding and extraction of the watermark are done by using logical operations to adjust the pixel value according to the parity of the pixel value and the number of prime numbers contained in the pixel value. The experimental results demonstrate that the proposed scheme is imperceptible, efficient, and safe. Compared with the existing methods, the proposed scheme achieves the binding of medical image and patient information, as well as exhibits excellent detection and positioning capability, and will have good application prospects in medical image content authentication and tampering detection. [ABSTRACT FROM AUTHOR]

While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretical results exist on how EAs solve permutation-based problems. To overcome the lack of permutation-based benchmark problems, we propose a general way to transfer the classic pseudo-Boolean benchmarks into benchmarks defined on sets of permutations. We then conduct a rigorous runtime analysis of the permutation-based (1 + 1) EA proposed by Scharnow et al. (J Math Model Algorithm 3:349–366, 2004) on the analogues of the LeadingOnes and Jump benchmarks. The latter shows that, different from bit-strings, it is not only the Hamming distance that determines how difficult it is to mutate a permutation σ into another one τ , but also the precise cycle structure of σ τ - 1 . For this reason, we also regard the more symmetric scramble mutation operator. We observe that it not only leads to simpler proofs, but also reduces the runtime on jump functions with odd jump size by a factor of Θ (n) . Finally, we show that a heavy-tailed version of the scramble operator, as in the bit-string case, leads to a speed-up of order m Θ (m) on jump functions with jump size m. A short empirical analysis confirms these findings, but also reveals that small implementation details like the rate of void mutations can make an important difference. [ABSTRACT FROM AUTHOR]

We address fully-defective asynchronous networks, in which all links are subject to an unlimited number of alteration errors, implying that all messages in the network may be completely corrupted. Despite the possible intuition that such a setting is too harsh for any reliable communication, we show how to simulate any algorithm for a noiseless setting over any fully-defective setting, given that the network is 2-edge connected. We prove that if the network is not 2-edge connected, no non-trivial computation in the fully-defective setting is possible. The key structural property of 2-edge-connected graphs that we leverage is the existence of an oriented (non-simple) cycle that goes through all nodes (Robbins, Am. Math. Mon., 1939). The core of our technical contribution is presenting a construction of such a Robbins cycle in fully-defective networks, and showing how to communicate over it despite total message corruption. These are obtained in a content-oblivious manner, since nodes must ignore the content of received messages. [ABSTRACT FROM AUTHOR]

We study the issue of numerically solving the nonnegative inverse eigenvalue problem (NIEP). At first, we reformulate the NIEP as a convex composite optimization problem on Riemannian manifolds. Then we develop a scheme of the Riemannian linearized proximal algorithm (R-LPA) to solve the NIEP. Under some mild conditions, the local and global convergence results of the R-LPA for the NIEP are established, respectively. Moreover, numerical experiments are presented. Compared with the Riemannian Newton-CG method in Z. Zhao et al. (Numer. Math. 140:827–855, 2018), this R-LPA owns better numerical performances for large scale problems and sparse matrix cases, which is due to the smaller dimension of the Riemannian manifold derived from the problem formulation of the NIEP as a convex composite optimization problem. [ABSTRACT FROM AUTHOR]

We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate between solving a master problem, which is a mixed-integer linear relaxation of the original problem, and a subproblem, which is designed to tighten the linear relaxation of the next master problem by using the Lipschitz information about the respective functions. By doing so, we follow the ideas of Schmidt, Sirvent, and Wollner (Math Program 178(1):449–483 (2019) and Optim Lett 16(5):1355-1372 (2022)) and improve the tackling of multivariate constraints. Although multivariate nonlinearities obviously increase modeling capabilities, their incorporation also significantly increases the computational burden of the proposed algorithm. We prove the correctness of our method and also derive a worst-case iteration bound. Finally, we show the generality of the addressed problem class and the proposed method by illustrating that both bilevel optimization problems with nonconvex and quadratic lower levels as well as nonlinear and mixed-integer models of gas transport can be tackled by our method. We provide the necessary theory for both applications and briefly illustrate the outcomes of the new method when applied to these two problems. [ABSTRACT FROM AUTHOR]

This research reflects on using mathematics for processing and interpreting data obtained from digital surveying. The experiments outlined in this study demonstrate how mathematical algorithms, which can be written in computational environments like Wolfram Mathematica, can reveal the geometric structure of an architectural artifact. [ABSTRACT FROM AUTHOR]

Motivated by several applications, we investigate the well-posedness of a switched system composed by a system of linear hyperbolic balance laws and by a system of linear algebraic differential equations. This setting includes networks and looped systems of hyperbolic balance laws. The obtained results are globally in time, provided that the inputs have finite (but not necessarily small) total variation. [ABSTRACT FROM AUTHOR]

Anzai skew-products are shown to be uniquely ergodic with respect to the fixed-point subalgebra if and only if there is a unique conditional expectation onto such a subalgebra which is invariant under the dynamics. For the particular case of skew-products, this solves a question raised by B. Abadie and K. Dykema in the wider context of C ∗ -dynamical systems. [ABSTRACT FROM AUTHOR]

Programming-based activities are becoming more widespread in curricula. Our theoretical and empirical investigation seeks to identify appropriate ways to connect computer programming and algorithmics to mathematical learning. We take the intermediate value theorem as our starting point, as it is covered by the French school curriculum, and because of its links with the bisection algorithm. We build upon the theory of mathematical working spaces, distinguishing between algorithmic and mathematical working spaces. Both working spaces are explored from the semiotic, instrumental, and discursive dimensions that support learning. Our two research questions focus on the suitable algorithmic and mathematical working spaces in which students develop an understanding of the intermediate value theorem, and the bisection algorithm. Our method starts at the reference level, with an epistemological and curricular analysis. Then, a series of tasks is designed for students working in adidacticity, and suitable working spaces are determined a priori. The tasks have been implemented in French classrooms with students aged 16–19. An analysis of their work supports an a posteriori examination of the working spaces. Our findings demonstrate that the students were able to make connections between algorithmics and mathematics in each of the three dimensions, semiotic, instrumental, and discursive, and point out the interplay between these dimensions. [ABSTRACT FROM AUTHOR]

To improve the MRPSS preconditioner developed by Cao et al. (BIT Numer Math 56:423–439, 2016), a generalized variant of the MRPSS (GMRPSS) preconditioner is proposed. The invertibility of the GMRPSS preconditioner, the convergence of the GMRPSS iteration method and some properties of the corresponding preconditioned matrix are presented. The degree of minimal polynomials of the preconditioned matrix is obtained. Simultaneously, the algorithm implementation and the selection of the parameter of the GMRPSS preconditioner are discussed. Numerical experiments are performed to illustrate the feasibility of the new preconditioner. [ABSTRACT FROM AUTHOR]

Tverberg's theorem states that for any k ≥ 2 and any set P ⊂ R d of at least (d + 1) (k - 1) + 1 points in d dimensions, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem of finding the partition lies in the complexity class CLS = PPAD ∩ PLS , but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa (SODA 2019) gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set P ⊂ R d and any k ∈ { 2 , ⋯ , n } in O (n d ⌈ log k ⌉) time a k-partition of P such that there is a ball of radius O ((k / n) diam (P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria's method (Israel Journal Math., 1992) to reduce the Tverberg problem to the colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem. [ABSTRACT FROM AUTHOR]

Motivated by Luo's (Commun Contemp Math 6:765–780, 2004) combinatorial Yamabe flow on closed surfaces and Guo's (Commun Contemp Math 13:827–842, 2011) combinatorial Yamabe flow on surfaces with boundary, we introduce combinatorial Calabi flow on ideally triangulated surfaces with boundary, aiming at finding hyperbolic metrics on surfaces with totally geodesic boundaries of given lengths. Then we prove the long time existence and global convergence of combinatorial Calabi flow on surfaces with boundary. We further introduce fractional combinatorial Calabi flow on surfaces with boundary, which unifies and generalizes the combinatorial Yamabe flow and the combinatorial Calabi flow on surfaces with boundary. The long time existence and global convergence of fractional combinatorial Calabi flow are also proved. These combinatorial curvature flows provide effective algorithms to construct hyperbolic surfaces with totally geodesic boundaries with prescribed lengths. [ABSTRACT FROM AUTHOR]

A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. We show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. An eulerian factor of a 2-edge-coloured graph is a collection of vertex-disjoint induced subgraphs which cover all the vertices of G such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test whether a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (trail-)colour-connected if it contains a pair of alternating (u, v)-paths ((u, v)-trails) whose union is an alternating closed walk for every pair of distinct vertices u, v. We prove that a 2-edge-coloured complete bipartite graph is supereulerian if and only if it is colour-connected and has an eulerian factor. A 2-edge-coloured graph is M-closed if xz is an edge of G whenever some vertex u is joined to both x and z by edges of the same colour. M-closed 2-edge-coloured graphs, introduced in Contreras-Balbuena et al. (Discret Math Theoret Comput Sci 21:1, 2019), form a rich generalization of 2-edge-coloured complete graphs. We show that if G is obtained from an M-closed 2-edge-coloured graph H by substituting independent sets for the vertices of H, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. Finally we discuss 2-edge-coloured complete multipartite graphs and show that such a graph may not be supereulerian even if it is trail-colour-connected and has an eulerian factor. [ABSTRACT FROM AUTHOR]

Chinese word segmentation is an important research direction in related research on elementary mathematics knowledge extraction. The speed of segmentation directly affects subsequent applications, and the accuracy of segmentation directly affects corresponding research in the next step. In the machine learning methods for extracting basic mathematical knowledge points, the Conditional Random Field (CRF) model implements new word discovery well, and is increasingly used in knowledge extraction of basic mathematics. This article first introduces the traditional CRF process of named entity recognition. Then, an improved algorithm CRF++for conditional field model is proposed. Since the recognition rate of named entities based on traditional machine learning methods is not high, a post-processing method for entity recognition that automatically generates a dictionary is proposed. After identifying mathematical entities, a pruning strategy combining Viterbi algorithm and rules is proposed to achieve a higher recognition rate of elementary mathematical entities. Finally, several methods of disambiguation after entity recognition are introduced. [ABSTRACT FROM AUTHOR]