Computational Complexity of Probabilistic Turing Machines
From MaRDI portal
Cited in
(only showing first 100 items - show all)- The complexity of power-index comparison
- Dimension extractors and optimal decompression
- Theory of one-tape linear-time Turing machines
- BPP and the polynomial hierarchy
- Space-bounded hierarchies and probabilistic computations
- Robust algorithms: a different approach to oracles
- Games against nature
- Relativized circuit complexity
- Randomized algorithms in combinatorial optimization: A survey
- Random generation of combinatorial structures from a uniform distribution
- Approximation to measurable functions and its relation to probabilistic computation
- The complexity of combinatorial problems with succinct input representation
- On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
- On helping by robust oracle machines
- Some observations on the connection between counting and recursion
- The complexity properties of probabilistic automata with isolated cut point
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- Complexity classes without machines: on complete languages for UP
- Minimum disclosure proofs of knowledge
- Relativized alternation and space-bounded computation
- On the relative complexity of hard problems for complexity classes without complete problems
- Probabilistic quantifiers and games
- Graph isomorphism is in the low hierarchy
- Approximate counting, uniform generation and rapidly mixing Markov chains
- The generation of random numbers that are probably prime
- Deterministic simulation of tape-bounded probabilistic Turing machine transducers
- Probabilistic automata
- On tape-bounded probabilistic Turing machine acceptors
- Division in idealized unit cost RAMs
- Some observations on the probabilistic algorithms and NP-hard problems
- Symmetric space-bounded computation
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On counting problems and the polynomial-time hierarchy
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- An introduction to randomized algorithms
- Which new RSA-signatures can be computed from certain given RSA- signatures!
- On independent random oracles
- Separating complexity classes with tally oracles
- Restricted relativizations of probabilistic polynomial time
- The complexity of stochastic games
- Turing machines with few accepting computations and low sets for PP
- A survey of space complexity
- On the necessity of Occam algorithms
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- Logarithmic advice classes
- A note on the permanent value problem
- An almost-constant round interactive zero-knowledge proof
- Lower bounds on the length of universal traversal sequences
- On read-once vs. multiple access to randomness in logspace
- On sparse hard sets for counting classes
- Graph isomorphism is low for PP
- A randomised heuristical algorithm for estimating the chromatic number of a graph
- Probabilistic complexity classes and lowness
- Properties of probabilistic pushdown automata
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- A note on two-dimensional probabilistic finite automata
- The complexity of the max word problem and the power of one-way interactive proof systems
- Gap-definable counting classes
- Simple characterizations of \(P(\# P)\) and complete problems
- The random oracle hypothesis is false
- Computational depth and reducibility
- On closure properties of GapP
- Computation times of NP sets of different densities
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Efficient simulations by a biased coin
- The statistics of state-spaces
- Recursion theoretic characterizations of complexity classes of counting functions
- Approximation of boolean functions by combinatorial rectangles
- A space lower bound for \(st\)-connectivity on node-named JAGs
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Circuits over PP and PL
- Voronoi-like nondeterministic partition of a lattice by collectives of finite automata
- Amplification of slight probabilistic advantage at absolutely no cost in space
- The computational complexity of calculating partition functions of optimal medians with Hamming distance
- The complexity of Bayesian networks specified by propositional and relational languages
- On the hardness of analyzing probabilistic programs
- A monad for randomized algorithms
- On the power of randomized multicounter machines
- A probabilistic model of computing with words
- Bounding stochastic dependence, joint mixability of matrices, and multidimensional bottleneck assignment problems
- Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines
- A note on two-dimensional probabilistic Turing machines
- A probabilistic approach to navigation in Hypertext
- Enumerative counting is hard
- Probabilistic game automata
- Randomised algorithms
- The time-precision tradeoff problem on on-line probabilistic Turing machines
- Complexity results for structure-based causality.
- Tally NP sets and easy census functions.
- Bayesian estimation and the Kalman filter
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Complexity limitations on quantum computation
- Space-bounded quantum complexity
- The hardest halfspace
- A thesis for interaction
- Structural control in weighted voting games
- On measure quantifiers in first-order arithmetic
- Confluent complement: an algorithm for the intersection of face ideals
- Probabilistic causes in Markov chains
This page was built for publication: Computational Complexity of Probabilistic Turing Machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4140967)
