Shadows of Newton polytopes

DOI10.1007/S11856-023-2510-ZMaRDI QIDQ6076195zbMATH OpenOpenAlexFDO

Authors Pavel Hrubeš, Amir Yehudayoff

Publication date 23 October 2023

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11856-023-2510-z

Mathematics Subject Classification ID

Polytopes and polyhedra (52Bxx) Theory of computing (68Qxx) Mathematical programming (90Cxx)

Cites work

• A \(\tau \)-conjecture for Newton polygons
• A framework for the greedy algorithm
• A lower bound for the shortest path problem
• Absolute irreducibility of polynomials via Newton polytopes
• Arithmetic circuits: a survey of recent results and open questions
• Arithmetic circuits: the chasm at depth four gets wider
• Balas formulation for the union of polytopes is optimal
• Communication Complexity
• Completeness and reduction in algebraic complexity theory
• Complexity of some parametric integer and network programming problems
• Disjunctive programming: Properties of the convex hull of feasible points
• Expressing combinatorial optimization problems by linear programs
• Extremal properties of 0/1-polytopes
• Fast Parallel Computation of Polynomials Using Few Processors
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Linear vs. semidefinite extended formulations
• Lower bounds for tropical circuits and dynamic programs
• Lower Bounds in a Parallel Model without Bit Operations
• Matroids and the greedy algorithm
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• Monotone projection lower bounds from extended formulation lower bounds
• Moser's shadow problem
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Negation can be exponentially powerful
• On a conjecture of Lindenstrauss
• On the depth complexity of formulas
• On the distribution of runners on a circle
• On the Number of Additions to Compute Specific Polynomials
• On the Parallel Evaluation of Multivariate Polynomials
• Optimal assignments in an ordered set: An application of matroid theory
• Some \(0/1\) polytopes need exponential size extended formulations
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Subtraction-free complexity, cluster transformations, and spanning trees
• The complexity of cutting complexes
• The monotone circuit complexity of Boolean functions
• The Parallel Evaluation of General Arithmetic Expressions

Cited in

(3)

• NP by Means of Lifts and Shadows
• Shadows of newton polytopes
• A survey of exact and approximation algorithms for linear-parametric optimization problems

This page was built for publication: Shadows of Newton polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076195)