Proving simultaneous positivity of linear forms

From MaRDI portal
Publication:2265260

DOI10.1016/S0022-0000(72)80034-5zbMath0274.68022MaRDI QIDQ2265260

Michael O. Rabin

Publication date: 1972

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




Related Items

A note on Rabin's width of a complete proof, Selection problems via \(m\)-ary queries, On decision trees for orthants, A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems, On selecting the k largest with median tests, Randomization and the computational power of analytic and algebraic decision trees, Subquadratic algorithms for algebraic 3SUM, Discrete extremal problems, Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations, The complexity of selection and ranking in X+Y and matrices with sorted columns, On hardly linearly provable systems, Comparisons between linear functions can help, On selecting the \(k\) largest with restricted quadratic queries, Spira's theorems on complete linear proofs of systems of linear inequalities, 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, Lower bounds for arithmetic networks, On the complexity of computations under varying sets of primitives, 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, Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model, Decision trees: Old and new results., On the decisional complexity of problems over the reals, A randomized algorithm for finding maximum with \(O((\log n)^2)\) polynomial tests



Cites Work