An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms

DOI10.1287/moor.2013.0629zbMath1335.65050OpenAlexW1997226282MaRDI QIDQ5244858

Uriel G. Rothblum, B. Curtis Eaves

Publication date: 31 March 2015

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.2013.0629

zbMATH Keywords

equivalencebijectionlinear problemsordered fieldspredicate languageinput-output pairsdata-solution pairsparametric Fourier quantifier eliminationrandomizing linear algorithms

Mathematics Subject Classification ID

Linear inequalities of matrices (15A39) Numerical solutions to equations with linear operators (65J10) Randomized algorithms (68W20) Ordered fields (12J15) Quantifier elimination, model completeness, and related topics (03C10)

Cites Work

• The complexity of linear problems in fields
• Dines-Fourier-Motzkin quantifier elimination and an application of corresponding transfer principles over ordered fields
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• A new decision method for elementary algebra
• Defining Integers
• A Theory on Extending Algorithms for Parametric Problems
• How to Pick Out the Integers in the Rationals: An Application of Number Theory to Logic
• Proof of Recursive Unsolvability of Hilbert's Tenth Problem
• A Decision Procedure for the First Order Theory of Real Addition with Order
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Definability and decision problems in arithmetic
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms