More Like this

1. 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
2. Applications of Polynomial Systems

   Cox, D; D'Andrea, C; Dickenstein, A; Hauenstein, J; Schenck, H; Sidman, J (January 2020, CBMS Lecture notes 134)

   null (Ed.)

   CBMS notes from a series of 10 Lectures by David Cox, with supplemental lectures by C. D'Andrea, A. Dickenstein, J. Hauenstein, H. Schenck, J. Sidman. Systems of polynomial equations can be used to model an astonishing variety of phenomena. This book explores the geometry and algebra of such systems and includes numerous applications. The book begins with elimination theory from Newton to the twenty-first century and then discusses the interaction between algebraic geometry and numerical computations, a subject now called numerical algebraic geometry. The final three chapters discuss applications to geometric modeling, rigidity theory, and chemical reaction networks in detail. Each chapter ends with a section written by a leading expert. 

   more » « less
3. 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)
4. Every real-rooted exponential polynomial is the restriction of a Lee-Yang polynomial

   https://doi.org/10.1016/j.jfa.2023.110226  

   Alon, Lior; Cohen, Alex; Vinzant, Cynthia (January 2024, Journal of Functional Analysis)
5. A note on sparse polynomial interpolation in Dickson polynomial basis

   https://doi.org/10.1145/3465002.3465003  

   Imamoglu, Erdal; Kaltofen, Erich L. (December 2020, ACM Communications in Computer Algebra)

   null (Ed.)