Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-189 | 24th December 2020 11:39

Shadows of Newton polytopes

RSS-Feed




TR20-189
Authors: Pavel Hrubes, Amir Yehudayoff
Publication: 24th December 2020 15:17
Downloads: 799
Keywords: 


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.



ISSN 1433-8092 | Imprint