More Like this

1. Sparse Polynomial Interpolation With Arbitrary Orthogonal Polynomial Bases

   https://doi.org/10.1145/3208976.3208999  

   Imamoglu, Erdal; Kaltofen, Erich L.; Yang, Zhengfeng (January 2018, Proc. 2018 ACM International Symposium on Symbolic and Algebraic Computation)
2. Fast Sketching of Polynomial Kernels of Polynomial Degree

   Song, Zhao; Woodruff, David P.; Yu, Zheng; Zhang, Lichen (July 2021, Proceedings of Machine Learning Research)
3. Computing Solutions to the Polynomial-Polynomial Regulator Problem*

   https://doi.org/10.1109/CDC56724.2024.10885897  

   Corbin, Nicholas A; Kramer, Boris (December 2024, Proceedings of the IEEE Conference on Decision Control)

   We present a scalable approach to computing nonlinear balancing energy functions for control-affine systems with polynomial nonlinearities. Al’brekht’s powerseries method is used to solve the Hamilton–Jacobi– Bellman equations for polynomial approximations to the energy functions. The contribution of this article lies in the numerical implementation of the method based on the Kronecker product, enabling scalability to over 1000 state dimensions. The tensor structure and symmetries arising from the Kronecker product representation are key to the development of efficient and scalable algorithms.We derive the explicit algebraic structure for the equations, present rigorous theory for the solvability and algorithmic complexity of those equations, and provide general purpose open-source software implementations for the proposed algorithms. The method is illustrated on two simple academic models, followed by a high-dimensional semidiscretized PDE model of dimension as large as n = 1080. 

   more » « less
4. Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality

   https://doi.org/10.1007/s00224-023-10118-y  

   Grochow, Joshua A. (May 2023, Theory of Computing Systems)

   Abstract There is no single canonical polynomial-time version of the Axiom of Choice (AC); several statements of AC that are equivalent in Zermelo-Fraenkel (ZF) set theory are already inequivalent from a constructive point of view, and are similarly inequivalent from a complexity-theoretic point of view. In this paper we show that many classical formulations of AC, when restricted to polynomial time in natural ways, are equivalent to standard complexity-theoretic hypotheses, including several that were of interest to Selman. This provides a unified view of these hypotheses, and we hope provides additional motivation for studying some of the lesser-known hypotheses that appear here. Additionally, because several classical forms of AC are formulated in terms of cardinals, we develop a theory of polynomial-time cardinality. Nerode & Remmel (Contemp. Math.106, 1990 and Springer Lec. Notes Math. 1432, 1990) developed a related theory, but restricted to unary sets. Downey (Math. Reviews MR1071525) suggested that such a theory over larger alphabets could have interesting connections to more standard complexity questions, and we illustrate some of those connections here. The connections between AC, cardinality, and complexity questions also allow us to highlight some of Selman’s work. We hope this paper is more of a beginning than an end, introducing new concepts and raising many new questions, ripe for further research. 

   more » « less
5. Polynomial effective equidistribution

   https://doi.org/10.5802/crmath.411  

   Lindenstrauss, Elon; Mohammadi, Amir; Wang, Zhiren (January 2023, Comptes Rendus. Mathématique)