LIPIcs.ITCS.2022.89.pdf
- Filesize: 0.74 MB
- 21 pages
Document
Almost-Orthogonal Bases for Inner Product Polynomials
Authors
-
Part of:
Volume:
13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-01-25
File
Document Identifiers
Acknowledgements
We would like to thank Goutham Rajendran for discussions and many comments on this work. We also thank Mrinalkanti Ghosh, Fernando Granha Jeronimo, and Madhur Tulsiani for early discussions on the polynomials in the context of Sum-of-Squares.
Cite As Get BibTex
Chris Jones and Aaron Potechin. Almost-Orthogonal Bases for Inner Product Polynomials. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 89:1-89:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.89
Abstract
In this paper, we consider low-degree polynomials of inner products between a collection of random vectors. We give an almost orthogonal basis for this vector space of polynomials when the random vectors are Gaussian, spherical, or Boolean. In all three cases, our basis admits an interesting combinatorial description based on the topology of the underlying graph of inner products. We also analyze the expected value of the product of two polynomials in our basis. In all three cases, we show that this expected value can be expressed in terms of collections of matchings on the underlying graph of inner products. In the Gaussian and Boolean cases, we show that this expected value is always non-negative. In the spherical case, we show that this expected value can be negative but we conjecture that if the underlying graph of inner products is planar then this expected value will always be non-negative.
Subject Classification
ACM Subject Classification
- Theory of computation → Randomness, geometry and discrete structures
Keywords
- Orthogonal polynomials
- Fourier analysis
- combinatorics
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Béla Bollobás. Evaluations of the circuit partition polynomial. J. Combin. Theory Ser. B, 85(2):261-268, 2002. URL: https://doi.org/10.1006/jctb.2001.2102.
-
Peter J. Cameron and Jason Semeraro. The cycle polynomial of a permutation group. Electron. J. Combin., 25(1):Paper No. 1.14, 13, 2018.
- Feng Dai and Yuan Xu. Approximation theory and harmonic analysis on spheres and balls. Springer Monographs in Mathematics. Springer, New York, 2013. URL: https://doi.org/10.1007/978-1-4614-6660-4.
- Charles F. Dunkl and Yuan Xu. Orthogonal polynomials of several variables, volume 155 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, second edition, 2014. URL: https://doi.org/10.1017/CBO9781107786134.
- Joanna A. Ellis-Monaghan. New results for the Martin polynomial. J. Combin. Theory Ser. B, 74(2):326-352, 1998. URL: https://doi.org/10.1006/jctb.1998.1853.
-
Yuval Filmus. An orthogonal basis for functions over a slice of the Boolean hypercube. Electron. J. Combin., 23(1):Paper 1.23, 27, 2016.
- Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran. Sum-of-squares lower bounds for sherrington-kirkpatrick via planted affine planes. CoRR, abs/2009.01874, 2020. URL: http://arxiv.org/abs/2009.01874.
- Ian Holyer. The NP-completeness of some edge-partition problems. SIAM J. Comput., 10(4):713-717, 1981. URL: https://doi.org/10.1137/0210054.
- Svante Janson. Gaussian Hilbert spaces, volume 129 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1997. URL: https://doi.org/10.1017/CBO9780511526169.
-
Pierre Martin. Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck. PhD thesis, University Joseph-Fourier, 1977. Ph. D. Thesis.
- Cristopher Moore and Alexander Russell. Circuit partitions and #p-complete products of inner products. CoRR, abs/1001.2314, 2010. URL: http://arxiv.org/abs/1001.2314.
-
Steven Roman. The umbral calculus. Springer, 2005.