Another proof that bpp?ph (and more)

No abstract is available for this paper.

• Publication year

  1997

• Venue

  Electronic Colloquium on Computational Complexity

• Publication date

  Unknown publication date

• Fields of study

  Mathematics

• Identifiers
  DOI 10.1007/978-3-642-22670-0_6
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Derandomizing Arthur–Merlin Games using Hitting Sets

  1999cited by this paper
• Symmetric alternation captures BPP

  1998influential reference
• P = BPP if E requires exponential circuits: derandomizing the XOR lemma

  1997cited by this paper
• A Sample of Samplers - A Computational Perspective on Sampling (survey)

  1997cited by this paper
• More on BPP and the Polynomial-Time Hierarchy

  1996cited by this paper
• BPP has subexponential time simulations unless EXPTIME has publishable proofs

  1991cited by this paper
• Simulating BPP using a general weak random source

  1991cited by this paper
• On Completeness and Soundness in Interactive Proof Systems

  1989cited by this paper
• The Knowledge Complexity of Interactive Proof Systems

  1989cited by this paper
• Does co-NP Have Short Interactive Proofs?

  1987cited by this paper
• Probabalistic Quantifiers vs. Distrustful Adversaries

  1987cited by this paper
• Private coins versus public coins in interactive proof systems

  1986cited by this paper
• A Decisive Characterization of BPP

  1986influential reference
• Trading group theory for randomness

  1985influential reference
• BPP and the Polynomial Hierarchy

  1983cited by this paper
• A complexity theoretic approach to randomness

  1983cited by this paper

• Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems

  2025cites this paper
• Complexity of geometrically local stoquastic Hamiltonians

  2024cites this paper
• LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic

  2022cites this paper
• Pseudodeterminism: promises and lowerbounds

  2022cites this paper
• Promise Problems Meet Pseudodeterminism

  2021cites this paper
• Two Combinatorial MA-Complete Problems

  2020cites this paper
• A combinatorial MA-complete problem

  2020cites this paper
• Consistency of circuit lower bounds with bounded theories

  2019cites this paper
• Stoquastic PCP vs. Randomness

  2019cites this paper
• The Power of Natural Properties as Oracles

  2018cites this paper
• Quantum proofs, the local Hamiltonian problem and applications. (Preuves quantiques, le problème des Hamiltoniens locaux et applications)

  2018cites this paper
• The Landscape of Communication Complexity Classes

  2018cites this paper
• Easy Witnesses and Hard Circuit Lower Bounds

  2018cites this paper
• Promise problems

  2017influential citation
• Quantum hashing is maximally secure against classical leakage

  2017cites this paper
• Quantum-Proof Extractors: Optimal up to Constant Factors

  2016cites this paper
• A Linear Time Algorithm for Quantum 2-SAT

  2015cites this paper
• Unconditional Lower Bounds in Complexity Theory

  2015cites this paper
• On Learning, Lower Bounds and (un)Keeping Promises

  2014cites this paper
• Constructing Hard Functions Using Learning Algorithms

  2013cites this paper
• Constructing Hard Functions Using Learning Algorithms

  2013cites this paper
• CAREER: A Unified Theory of Pseudorandomness

  2013cites this paper
• Towards Perfect Completeness in QMA

  2012cites this paper
• Approximation, Proof Systems, and Correlations in a Quantum World

  2012influential citation
• Stronger methods of making quantum interactive proofs perfectly complete

  2012cites this paper
• Simplified Derandomization of BPP Using a Hitting Set Generator

  2011cites this paper
• Applications of Derandomization Theory in Coding

  2011cites this paper
• Achieving perfect completeness in classical-witness quantum merlin-arthur proof systems

  2011cites this paper
• Fast amplification of QMA

  2009cites this paper
• Finding Irrefutable Certificates for S2p via Arthur and Merlin

  2008cites this paper
• Arthur and Merlin as Oracles

  2008cites this paper
• On perfect completeness for QMA

  2008cites this paper
• On Approximate Majority and Probabilistic Time

  2007cites this paper
• Explicit Logspace Constructions of Weak DesignsTzvika Hartmany RanR z

  2007cites this paper
• S p 2 ⊆ ZPP NP

  2007cites this paper
• 2 Better Tradeoffs 2 . 1 Hardness amplification via error-correcting codes

  2007cites this paper
• Circuit lower bounds for Merlin-Arthur classes

  2007cites this paper
• Lower Bounds for Swapping Arthur and Merlin

  2007cites this paper
• A Survey of Lower Bounds for Satisfiability and Related Problems

  2007cites this paper
• The Complexity of Propositional Proofs

  2007cites this paper
• The complexity of hardness amplification and derandomization

  2006cites this paper
• On zero error algorithms having oracle access to one query

  2006influential citation
• Oblivious Symmetric Alternation

  2006cites this paper
• On Probabilistic Time versus Alternating Time

  2005cites this paper
• Derandomization, hard functions, and average-case complexity (דה-רנדומיזציה, פונקציות קשות וסיבוכיות ממוצעת.)

  2005cites this paper
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games

  2003cites this paper
• Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

  2003cites this paper
• Recent Developments in Explicit Constructions of Extractors

  2002cites this paper
• Pseudorandomness and Average-Case Complexity Via Uniform Reductions

  2002cites this paper
• On Higher Arthur-Merlin Classes

  2002cites this paper
• Derandomization: a brief overview

  2002cites this paper
• O ct 2 00 2 Quantum NPA Survey

  2002cites this paper
• Quantum NP - A Survey

  2002cites this paper
• S/sub 2/ ZPP/sup NP/

  2001cites this paper
• Extractors and pseudorandom generators

  2001cites this paper
• On pseudorandomness and resource-bounded measure

  2001cites this paper
• Extractors from Reed-Muller codes

  2001cites this paper
• In search of an easy witness: exponential time vs. probabilistic polynomial time

  2001cites this paper
• Simple extractors for all min-entropies and a new pseudo-random generator

  2001cites this paper
• Pseudorandom generators in propositional proof complexity

  2000cites this paper
• The Computational Complexity of Equivalence and Isomorphism Problems

  2000cites this paper
• Extracting all the randomness and reducing the error in Trevisan's extractors

  1999cites this paper
• Improved Derandomization of BPP Using a Hitting Set Generator

  1999cites this paper
• Hardness of Approximating p 2 Minimization Problems

  1999cites this paper
• A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes

  1999cites this paper
• Construction of extractors using pseudo-random generators (extended abstract)

  1999cites this paper
• Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy

  1999cites this paper
• Hardness of approximating /spl Sigma//sub 2//sup p/ minimization problems

  1999cites this paper
• Extracting All the Randomness from a Weakly Random Source

  1998cites this paper
• Almost Optimal Dispersers

  1998cites this paper
• Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

  1998cites this paper
• Probabilistic martingales and BPTIME classes

  1998cites this paper
• A Faster Algorithm for 0 - 1 Integer Programming from Communication Complexity

  year unknowninfluential citation
• S p 2

  year unknowncites this paper