On the Complexity of Numerical Analysis
From MaRDI portal
Publication:3642872
DOI10.1137/070697926zbMath1191.68329OpenAlexW2040721698WikidataQ56067400 ScholiaQ56067400MaRDI QIDQ3642872
Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen, Eric W. Allender
Publication date: 6 November 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2006/613/
straight-line programsBlum-Shub-Smale modelarithmetic circuitscounting hierarchyBPPsum of square roots problem
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations, The Odds of Staying on Budget, Computing equilibria: a computational complexity perspective, Computing discrete logarithms using \(\mathcal{O}((\log q)^2)\) operations from \(\{+,-,\times,\div,\&\}\), Complexity of Equivalence and Learning for Multiplicity Tree Automata, Evaluating Matrix Circuits, A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing, Emptiness problems for integer circuits, Minimisation of Multiplicity Tree Automata, On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1, Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem, On the Order of Power Series and the Sum of Square Roots Problem, An improved approximation algorithm for the \(k\)-prize-collecting minimum power cover problem, A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes, Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\), Interpolation in Valiant's theory, Unnamed Item, Constraint Satisfaction Problems over Numeric Domains, On Faster Integer Calculations Using Non-arithmetic Primitives, On Probabilistic Parallel Programs with Process Creation and Synchronisation, The complexity of two problems on arithmetic circuits, Tree compression using string grammars, Evaluation of circuits over nilpotent and polycyclic groups, Tractability conditions for numeric CSPs, Analyzing probabilistic pushdown automata, Fixed points, Nash equilibria, and the existential theory of the reals, Language equivalence of probabilistic pushdown automata, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, Efficient algorithms for sparse cyclotomic integer zero testing, Unnamed Item, The complexity of tensor rank, On the metric-based approximate minimization of Markov chains, On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant, The Complexity of Nash Equilibria in Limit-Average Games, Algebraic Complexity Classes, Exotic quantifiers, complexity classes, and complete problems, On the Complexity of Value Iteration, Decision Problems for Nash Equilibria in Stochastic Games, Probabilistic Automata of Bounded Ambiguity, Efficient Analysis of Probabilistic Programs with an Unbounded Counter, Approximation algorithms for solving the line-capacitated minimum Steiner tree problem, Monomials in arithmetic circuits: complete problems in the counting hierarchy, Three-monotone interpolation, Computational complexity of multi-player evolutionarily stable strategies
