We approximate d-variate periodic functions in weighted Korobov spaces with general weight parameters using n function values at lattice points. We do not limit n to be a prime number, as in currently available litera...
详细信息
We approximate d-variate periodic functions in weighted Korobov spaces with general weight parameters using n function values at lattice points. We do not limit n to be a prime number, as in currently available literature, but allow any number of points, including powers of 2, thus providing the fundamental theory for construction of embedded lattice sequences. Our results are constructive in that we provide a component-by-component algorithm which constructs a suitable generating vector for a given number of points or even a range of numbers of points. It does so without needing to construct the index set on which the functions will be represented. The resulting generating vector can then be used to approximate functions in the underlying weighted Korobov space. We analyse the approximation error in the worst-case setting under both the L2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_2$$\end{document} and L infinity\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_{\infty }$$\end{document} norms. Our component-by-component construction under the L2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_2$$\end{document} norm achieves the best possible rate of convergence for lattice-based algorithms, and the theory can be applied to lattice-based kernel methods and splines. Depending on the value of the smoothness parameter alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackag
The discrete time quantum walk is a quantum cellular automaton whose wavefunction comprises pairs of complex numbers assigned to uniformly spaced points on a line. The wavefunction evolves through the application of a...
详细信息
The discrete time quantum walk is a quantum cellular automaton whose wavefunction comprises pairs of complex numbers assigned to uniformly spaced points on a line. The wavefunction evolves through the application of an alternating sequence of unitary operators: streaming of wavefunction values to adjacent points, and a Hadamard-type unitary matrix to blend pairs of values at individual points. Each operator generates the exact evolution due to part of the Hamiltonian for the one-dimensional Dirac equation over a finite time step. Composing these operators thus creates a discrete approximation to the Dirac equation. However, the composition of two non-commuting operators creates a global splitting error proportional to the length of the time step. The global error can be reduced from first order to second order in the time step by a unitary pre-and post-processing of the initial conditions and final output. The algorithm then becomes equivalent to a symmetric composition, a Strang splitting, between the two operators. This paper describes a fourth-order accurate composition scheme using nine stages, the fewest possible when the lengths of the time steps employed in the different stages are constrained to be integer multiples of some base time step. Each stage is itself a symmetric composition between two operators. This fourth-order scheme produces quantitatively smaller errors for a typical benchmark problem on spatial lattices with 1024 or more points, and shows the expected fourth-order convergence on sufficiently fine lattices. It has greater accuracy, over sufficiently long times, than three better-known fourth-order composition schemes using fewer stages, but with lengths related by irrational coefficients. The truncation error for plane-wave solutions is due to an operator that separates into a resonant part proportional to the Hamiltonian, and a non-resonant part orthogonal to the Hamiltonian. The resonant part commutes with the exact evolution operator, so i
Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and epsilon > 0, a covering ...
详细信息
Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and epsilon > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an epsilon expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and epsilon-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the closest vector problem (CVP). It is known how to construct coverings of size nO(n)/epsilon (n 1)/2 for general convex bodies in Rn. In special cases, such as when the convex body is the l p unit ball, this bound has been improved to 2O(n)/epsilon(n 1)/2. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach-Mazur metric. Given a well-centered convex body K and an approximation parameter epsilon > 0, we show that there exists a polytope P consisting of 2O(n)/epsilon (n 1)/2 vertices (facets) such that K subset of P subset of K(1+epsilon). This bound is optimal in the worst case up to factors of 2O(n). (This bound has been established recently using different techniques, but our approach is arguably simpler and more elegant.) As an additional consequence, we obtain the fastest (1 + epsilon)-approximate CVP algorithm that works in any norm, with a running time of 2O(n)/epsilon (n 1)/2 up to polynomial factors in the input size, and we obtain the fastest (1 + epsilon)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors o
Since 1991, Schnorr has proposed methods using lattices for solving the integer factorization problem whose hardness supports the security of the RSA cryptosystem. In 2022, Yan et al. proposed a modification of Schnor...
详细信息
ISBN:
(数字)9789819777372
ISBN:
(纸本)9789819777365;9789819777372
Since 1991, Schnorr has proposed methods using lattices for solving the integer factorization problem whose hardness supports the security of the RSA cryptosystem. In 2022, Yan et al. proposed a modification of Schnorr's lattices and reported numerical experiments by an optimization method using quantum computation. After that, Yamaguchi et al. reported that they succeeded in factoring RSA-type composite numbers of at most 55 bits based on Yan et al.'s modification, using classical annealing calculation. In this paper, we report experimental results of integer factorization methods using lattices in classical computing. Specifically, we analyze the structure of Schnorr's lattices to select suitable parameters and apply existing lattice algorithms for finding smooth relations in the difference-of-squares method. We report the running time of integer factorization using lattices for RSA-type composite numbers of at most 90 bits and the success probability of finding a smooth relation from a lattice. We also discuss the time complexity of integer factorization methods using lattices based on experimental results.
Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and epsilon > 0, a covering ...
详细信息
ISBN:
(纸本)9781611977554
Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and epsilon > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an epsilon expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and epsilon-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the Closest Vector Problem (CVP). It is known how to construct coverings of size n(O(n))/epsilon((n-1)2) for general convex bodies in R-n. In special cases, such as when the convex body is the l(p) unit ball, this bound has been improved to 2O(n)/epsilon((n-1)/2). This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach-Mazur metric. Given a wellcentered convex body K and an approximation parameter epsilon > 0, we show that there exists a polytope P consisting of 2(O(n))/epsilon((n-1)/2) vertices (facets) such that K subset of P subset of K(1 + epsilon). This bound is optimal in the worst case up to factors of 2(O(n)). (This bound has been established recently using different techniques, but our approach is arguably simpler and more elegant.) As an additional consequence, we obtain the fastest (1 + epsilon)-approximate CVP algorithm that works in any norm, with a running time of 2(O(n)/epsilon(n-1)/2) up to polynomial factors in the input size, and we obtain the fastest (1 + epsilon)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up
We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time 2(0.802 n). This contrasts the corresponding 2(n) time, (gap)-SETH based lower bounds...
详细信息
ISBN:
(纸本)9783031069017;9783031069000
We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time 2(0.802 n). This contrasts the corresponding 2(n) time, (gap)-SETH based lower bounds for these problems that even apply for small constant approximation. For both problems, SVP and CVP, we reduce to the case of the Euclidean norm. A key technical ingredient in that reduction is a twist of Milman's construction of an M-ellipsoid which approximates any symmetric convex body K with an ellipsoid E so that 2(epsilon n) translates of a constant scaling of E can cover K and vice versa.
Let L be a distributive lattice and E(L) be the set of join endomorphisms of L. We consider the problem of finding f Pi(E(L)) g given L and f, g is an element of E(L) as inputs. (1) We show that it can be solved in ti...
详细信息
ISBN:
(纸本)9783030887018;9783030887001
Let L be a distributive lattice and E(L) be the set of join endomorphisms of L. We consider the problem of finding f Pi(E(L)) g given L and f, g is an element of E(L) as inputs. (1) We show that it can be solved in time O(n) where n = vertical bar L vertical bar. The previous upper bound was O(n(2)). (2) We characterize the standard notion of distributed knowledge of a group as the greatest lower bound of the join-endomorphisms representing the knowledge of each member of the group. (3) We show that deciding whether an agent has the distributed knowledge of two other agents can be computed in time O(n(2)) where n is the size of the underlying set of states. (4) For the special case of S5 knowledge, we show that it can be decided in time O(n alpha(n)) where alpha(n) is the inverse of the Ackermann function.
The problem of parametric autoregressive model-based estimation of a time-varying spectral density function of a multivariate nonstationary process is considered. It is shown that estimation results can be considerabl...
详细信息
The problem of parametric autoregressive model-based estimation of a time-varying spectral density function of a multivariate nonstationary process is considered. It is shown that estimation results can be considerably improved if identification of the autoregressive model is carried out using the two-sided doubly exponentially weighted lattice algorithm, which combines results yielded by two one-sided lattice algorithms running forward in time and backward in time, respectively. It is also shown that the model order and the most appropriate estimation bandwidth can be efficiently selected using the suitably modified Akaikes final prediction error criterion.
Structures involving a lattice and join-endomorphisms on it are ubiquitous in computer science. We study the cardinality of the set E(L) of all join-endomorphisms of a given finite lattice L. In particular, we show th...
详细信息
ISBN:
(数字)9783030435202
ISBN:
(纸本)9783030435202;9783030435196
Structures involving a lattice and join-endomorphisms on it are ubiquitous in computer science. We study the cardinality of the set E(L) of all join-endomorphisms of a given finite lattice L. In particular, we show that when L is M-n, the discrete order of n elements extended with top and bottom, vertical bar E(L)vertical bar = n!L-n(-1) + (n + 1)(2) where L-n(x) is the Laguerre polynomial of degree n. We also study the following problem: Given a lattice L of size n and a set S subset of E(L) of size m, find the greatest lower bound Pi S-E(L). The join-endomorphism Pi(E(L)) S has meaningful interpretations in epistemic logic, distributed systems, and Aumann structures. We show that this problem can be solved with worst-case time complexity in O(n + m log n) for powerset lattices, O(mn(2)) for lattices of sets, and O(mn + n(3)) for arbitrary lattices. The complexity is expressed in terms of the basic binary lattice operations performed by the algorithm.
Given (a, b) is an element of Z(2), Euclid's algorithm outputs the generator gcd(a, b) of the ideal aZ+ bZ. Computing a lattice basis is a high-dimensional generalization: given a(1), ... , a(n) is an element of Z...
详细信息
ISBN:
(纸本)9781450360845
Given (a, b) is an element of Z(2), Euclid's algorithm outputs the generator gcd(a, b) of the ideal aZ+ bZ. Computing a lattice basis is a high-dimensional generalization: given a(1), ... , a(n) is an element of Z(m), find a Z-basis of the lattice L = {Sigma(n)(i=1) x(i)a(i), x(i) is an element of Z} generated by the a(i)'s. The fastest algorithms known are HNF algorithms, but are not adapted to all applications, such as when the output should not be much longer than the input. We present an algorithm which extracts such a short basis within the same time as an HNF, by reduction to HNF. We also present an HNF-less algorithm, which reduces to Euclid's extended algorithm and can be generalized to quadratic forms. Both algorithms can extend primitive sets into bases.
暂无评论