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/
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
This page was built for publication: On the Complexity of Numerical Analysis
