The Experts below are selected from a list of 183 Experts worldwide ranked by ideXlab platform
Neeraj Kayal - One of the best experts on this subject based on the ideXlab platform.
-
efficient algorithms for some special cases of the polynomial equivalence problem
Symposium on Discrete Algorithms, 2011Co-Authors: Neeraj KayalAbstract:We consider the following computational problem. Let F be a field. Given two n-variate polynomials f(x1,.., xn) and g(x1,.., xn) over the field F, is there an Invertible Linear Transformation of the variables which sends f to g? In other words, can we substitute a Linear combination of the xi's for each xj appearing in f and obtain the polynomial g? This problem is known to be at least as difficult as the graph isomorphism problem even for homogeneous degree three polynomials. There is even a cryptographic authentication scheme (Patarin, 1996) based on the presumed average-case hardness of this problem. Here we show that at least in certain (interesting) special cases there is a polynomial-time randomized algorithm for determining this equivalence, if it exists. Somewhat surprisingly, the algorithms that we present are efficient even if the input polynomials are given as arithmetic circuits. As an application, we show that if in the key generation phase of Patarin's authentication scheme, a random multiLinear polynomial is used to generate the secret, then the scheme can be broken and the secret recovered in randomized polynomial-time.
-
SODA - Efficient algorithms for some special cases of the polynomial equivalence problem
2011Co-Authors: Neeraj KayalAbstract:We consider the following computational problem. Let F be a field. Given two n-variate polynomials f(x1,.., xn) and g(x1,.., xn) over the field F, is there an Invertible Linear Transformation of the variables which sends f to g? In other words, can we substitute a Linear combination of the xi's for each xj appearing in f and obtain the polynomial g? This problem is known to be at least as difficult as the graph isomorphism problem even for homogeneous degree three polynomials. There is even a cryptographic authentication scheme (Patarin, 1996) based on the presumed average-case hardness of this problem. Here we show that at least in certain (interesting) special cases there is a polynomial-time randomized algorithm for determining this equivalence, if it exists. Somewhat surprisingly, the algorithms that we present are efficient even if the input polynomials are given as arithmetic circuits. As an application, we show that if in the key generation phase of Patarin's authentication scheme, a random multiLinear polynomial is used to generate the secret, then the scheme can be broken and the secret recovered in randomized polynomial-time.
-
Algorithms for Arithmetic Circuits.
Electronic Colloquium on Computational Complexity, 2010Co-Authors: Neeraj KayalAbstract:Given a multivariate polynomial f(X) ∈ F[X] as an arithmetic circuit we would like to efficiently determine: 1. Identity Testing. Is f(X) identically zero? 2. Degree Computation. Is the degree of the polynomial f(X) at most a given integer d . 3. Polynomial Equivalence. Upto an Invertible Linear Transformation of its variables, is f(X) equal to a given polynomial g(X). The algorithmic complexity of these problems is studied. Some new algorithms are provided here while some known ones are simplified. For the first problem, a deterministic algorithm is presented for the special case where the input circuit is a ”sum of powers of sums of univariate polynomials” . For the second problem, a coRP-algorithm is presented. Finally, randomized polynomial-time algorithms are presented for certain special cases of the third problem.
László Fehér - One of the best experts on this subject based on the ideXlab platform.
-
Equivalence of two sets of deformed Calogero-Moser Hamiltonians
arXiv: Mathematical Physics, 2015Co-Authors: T. F. Gorbe, László FehérAbstract:The equivalence of two complete sets of Poisson commuting Hamiltonians of the (super)integrable rational BC(n) Ruijsenaars-Schneider-van Diejen system is established. Specifically, the commuting Hamiltonians constructed by van Diejen are shown to be Linear combinations of the Hamiltonians generated by the characteristic polynomial of the Lax matrix obtained recently by Pusztai, and the explicit formula of this Invertible Linear Transformation is found.
-
Equivalence of two sets of Hamiltonians associated with the rational BC(n) Ruijsenaars-Schneider-van Diejen system
arXiv: Mathematical Physics, 2015Co-Authors: T. F. Gorbe, László FehérAbstract:The equivalence of two complete sets of Poisson commuting Hamiltonians of the (super)integrable rational BC(n) Ruijsenaars-Schneider-van Diejen system is established. Specifically, the commuting Hamiltonians constructed by van Diejen are shown to be Linear combinations of the Hamiltonians generated by the characteristic polynomial of the Lax matrix obtained recently by Pusztai, and the explicit formula of this Invertible Linear Transformation is found.
-
Equivalence of two sets of Hamiltonians associated with the rational BCn Ruijsenaars–Schneider–van Diejen system
Physics Letters A, 2015Co-Authors: T. F. Gorbe, László FehérAbstract:Abstract The equivalence of two complete sets of Poisson commuting Hamiltonians of the (super)integrable rational BC n Ruijsenaars–Schneider–van Diejen system is established. Specifically, the commuting Hamiltonians constructed by van Diejen are shown to be Linear combinations of the Hamiltonians generated by the characteristic polynomial of the Lax matrix obtained recently by Pusztai, and the explicit formula of this Invertible Linear Transformation is found.
D.l. Nuehoff - One of the best experts on this subject based on the ideXlab platform.
-
On quantization with the Weaire-Phelan partition
IEEE Transactions on Information Theory, 2001Co-Authors: Navin Kashyap, D.l. NuehoffAbstract:Until recently, the solution to the Kelvin problem of finding a partition of R/sup 3/ into equal-volume cells with the least surface area was believed to be tessellation by the truncated octahedron. In 1994, D. Weaire and R. Phelan described a partition that outperformed the truncated octahedron partition in this respect. This raises the question of whether the Weaire-Phelan (WP) partition can outperform the truncated octahedron partition in terms of normalized moment of inertia (NMI), thus providing a counterexample to Gersho's conjecture that the truncated octahedron partition has the least NMI among all partitions of R/sup 3/. In this correspondence, we show that the effective NMI of the WP partition is larger than that of the truncated octahedron partition. We also show that if the WP partition is used as the partition of a three-dimensional (3-D) vector quantizer (VQ), with the corresponding codebook consisting of the centroids of the cells, then the resulting quantization error is white. We then show that the effective NMI of the WP partition cannot he reduced by passing it through an Invertible Linear Transformation. Another contribution of this correspondence is a proof of the fact that the quantization error corresponding to an optimal periodic partition is white, which generalizes a result of Zamir and Feder (1996).
T. F. Gorbe - One of the best experts on this subject based on the ideXlab platform.
-
Equivalence of two sets of deformed Calogero-Moser Hamiltonians
arXiv: Mathematical Physics, 2015Co-Authors: T. F. Gorbe, László FehérAbstract:The equivalence of two complete sets of Poisson commuting Hamiltonians of the (super)integrable rational BC(n) Ruijsenaars-Schneider-van Diejen system is established. Specifically, the commuting Hamiltonians constructed by van Diejen are shown to be Linear combinations of the Hamiltonians generated by the characteristic polynomial of the Lax matrix obtained recently by Pusztai, and the explicit formula of this Invertible Linear Transformation is found.
-
Equivalence of two sets of Hamiltonians associated with the rational BC(n) Ruijsenaars-Schneider-van Diejen system
arXiv: Mathematical Physics, 2015Co-Authors: T. F. Gorbe, László FehérAbstract:The equivalence of two complete sets of Poisson commuting Hamiltonians of the (super)integrable rational BC(n) Ruijsenaars-Schneider-van Diejen system is established. Specifically, the commuting Hamiltonians constructed by van Diejen are shown to be Linear combinations of the Hamiltonians generated by the characteristic polynomial of the Lax matrix obtained recently by Pusztai, and the explicit formula of this Invertible Linear Transformation is found.
-
Equivalence of two sets of Hamiltonians associated with the rational BCn Ruijsenaars–Schneider–van Diejen system
Physics Letters A, 2015Co-Authors: T. F. Gorbe, László FehérAbstract:Abstract The equivalence of two complete sets of Poisson commuting Hamiltonians of the (super)integrable rational BC n Ruijsenaars–Schneider–van Diejen system is established. Specifically, the commuting Hamiltonians constructed by van Diejen are shown to be Linear combinations of the Hamiltonians generated by the characteristic polynomial of the Lax matrix obtained recently by Pusztai, and the explicit formula of this Invertible Linear Transformation is found.
Navin Kashyap - One of the best experts on this subject based on the ideXlab platform.
-
On quantization with the Weaire-Phelan partition
IEEE Transactions on Information Theory, 2001Co-Authors: Navin Kashyap, D.l. NuehoffAbstract:Until recently, the solution to the Kelvin problem of finding a partition of R/sup 3/ into equal-volume cells with the least surface area was believed to be tessellation by the truncated octahedron. In 1994, D. Weaire and R. Phelan described a partition that outperformed the truncated octahedron partition in this respect. This raises the question of whether the Weaire-Phelan (WP) partition can outperform the truncated octahedron partition in terms of normalized moment of inertia (NMI), thus providing a counterexample to Gersho's conjecture that the truncated octahedron partition has the least NMI among all partitions of R/sup 3/. In this correspondence, we show that the effective NMI of the WP partition is larger than that of the truncated octahedron partition. We also show that if the WP partition is used as the partition of a three-dimensional (3-D) vector quantizer (VQ), with the corresponding codebook consisting of the centroids of the cells, then the resulting quantization error is white. We then show that the effective NMI of the WP partition cannot he reduced by passing it through an Invertible Linear Transformation. Another contribution of this correspondence is a proof of the fact that the quantization error corresponding to an optimal periodic partition is white, which generalizes a result of Zamir and Feder (1996).
-
On the potential optimality of the Weaire-Phelan partition
Proceedings. 2001 IEEE International Symposium on Information Theory (IEEE Cat. No.01CH37252), 1Co-Authors: Navin Kashyap, David L. NeuhoffAbstract:We show that the effective normalized moment of inertia of the Weaire-Phelan (1996) partition, as well as that of its image under any Invertible Linear Transformation, is larger than that of the truncated octahedron partition.
