Proving simultaneous positivity of linear forms

DOI10.1016/S0022-0000(72)80034-5MaRDI QIDQ2265260zbMATH OpenFDO

Authors Michael O. Rabin

Publication date 1972

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-0000(72)80034-5

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Mathematical programming (90C99)

Cites work

• Complete linear proofs of systems of linear inequalities

Cited in

(28)

• Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
• A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems
• On selecting the k largest with median tests
• Discrete extremal problems
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Comparisons between linear functions can help
• On selecting the k largest with restricted quadratic queries
• Test complexity of generic polynomials
• A nonlinear lower bound on linear search tree programs for solving knapsack-problems
• Relative complexity of checking and evaluating
• Lower bounds on the worst-case complexity of some oracle algorithms
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• On the complexity of computations under varying sets of primitives
• A randomized algorithm for finding maximum with O(( n)^2) polynomial tests
• A note on Rabin's width of a complete proof
• Randomization and the computational power of analytic and algebraic decision trees
• Lower bounds for arithmetic networks
• Decision trees: Old and new results.
• On the decisional complexity of problems over the reals
• Selection problems via \(m\)-ary queries
• Subquadratic algorithms for algebraic 3SUM
• Complete linear proofs of systems of linear inequalities
• On decision trees for orthants
• On hardly linearly provable systems
• Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations
• Spira's theorems on complete linear proofs of systems of linear inequalities
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Erzeugungsgrad, VC-dimension and neural networks with rational activation function

This page was built for publication: Proving simultaneous positivity of linear forms

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