LIPIcs.CCC.2021.9.pdf
- Filesize: 0.74 MB
- 23 pages
Document
Shadows of Newton Polytopes
Authors
-
Part of:
Volume:
36th Computational Complexity Conference (CCC 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computational Complexity Conference (CCC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-07-08
File
Document Identifiers
Acknowledgements
We thank Michael Forbes for pointing out the connection between shadow complexity and Conjecture 47.
Cite As Get BibTex
Pavel Hrubeš and Amir Yehudayoff. Shadows of Newton Polytopes. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CCC.2021.9
Abstract
We define the shadow complexity of a polytope P as the maximum number of vertices in a linear projection of P to the plane. We describe connections to algebraic complexity and to parametrized optimization. We also provide several basic examples and constructions, and develop tools for bounding shadow complexity.
Subject Classification
ACM Subject Classification
- Theory of computation → Algebraic complexity theory
Keywords
- Newton polytope
- Monotone arithmetic circuit
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads