In search of an easy witness: exponential time vs. probabilistic polynomial time

No abstract is available for this paper.

• Publication year

  2001

• Venue

  Proceedings 16th Annual IEEE Conference on Computational Complexity

• Publication date

  2001-06-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/CCC.2001.933865
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Derandomization: a brief overview

  2002cited by this paper
• Comparing notions of full derandomization

  2001cited by this paper
• Derandomizing Arthur—Merlin games under uniform assumptions

  2001cited by this paper
• How to go beyond the black-box simulation barrier

  2001cited by this paper
• Derandomizing Complexity Classes

  2001cited by this paper
• Handbook of randomized computing

  2001cited by this paper
• Easiness assumptions and hardness tests: trading time for zero error

  2000cited by this paper
• Efficiently Approximable Real-Valued Functions

  2000cited by this paper
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses

  1999cited by this paper
• Derandomizing Arthur–Merlin Games using Hitting Sets

  1999cited by this paper
• Pseudorandom generators without the XOR lemma

  1999cited by this paper
• Randomness vs. time: de-randomization under a uniform assumption

  1998cited by this paper
• A new general derandomization method

  1998cited by this paper
• Nonrelativizing separations

  1998cited by this paper
• Modern Cryptography, Probabilistic Proofs and Pseudorandomness

  1998cited by this paper
• P = BPP if E requires exponential circuits: derandomizing the XOR lemma

  1997cited by this paper
• Another proof that bpp?ph (and more)

  1997cited by this paper
• Hitting Properties of Hard Boolean Operators and their Consequences on BPP

  1996cited by this paper
• Natural proofs

  1994cited by this paper
• Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy

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

  1991cited by this paper
• Nondeterministic exponential time has two-prover interactive protocols

  1990cited by this paper
• Decision versus search problems in super-polynomial time

  1989cited by this paper
• Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes

  1988cited by this paper
• Hardness vs. randomness

  1988cited by this paper
• Decision trees and downward closures

  1988cited by this paper
• Trading group theory for randomness

  1985cited by this paper
• Sparse Sets in NP-P: EXPTIME versus NEXPTIME

  1985cited by this paper
• Sparse sets in NP-P: Exptime versus nexptime

  1983cited by this paper
• Theory and Applications of Trapdoor Functions (Extended Abstract)

  1982cited by this paper

• Equivalence Between Coding and Complexity Lower Bounds

  2025influential citation
• On the Structure of Learnability beyond P/poly

  2025cites this paper
• Upper and Lower Bounds for the Linear Ordering Principle

  2025cites this paper
• Simple general magnification of circuit lower bounds

  2025cites this paper
• Jump Operators, Interactive Proofs and Proof Complexity Generators

  2024cites this paper
• The status of the quantum PCP conjecture (games version)

  2024cites this paper
• On the Complexity of Avoiding Heavy Elements

  2024cites this paper
• Towards ACC Lower Bounds using Torus Polynomials

  2024cites this paper
• New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs

  2023cites this paper
• Derandomization with Minimal Memory Footprint

  2023cites this paper
• Symmetric Exponential Time Requires Near-Maximum Circuit Size

  2023influential citation
• Guest Column: New ways of studying the BPP = P conjecture

  2023cites this paper
• Bounded Relativization

  2023cites this paper
• On Oracles and Algorithmic Methods for Proving Lower Bounds

  2023influential citation
• On the Consistency of Circuit Lower Bounds for Non-deterministic Time

  2023cites this paper
• An Algorithmic Approach to Uniform Lower Bounds

  2023cites this paper
• Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols

  2023influential citation
• New ways of studying the BPP = P conjecture

  2023cites this paper
• When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems

  2023cites this paper
• Quantum and Probabilistic Computers Rigorously Powerful than Traditional Computers, and Derandomization

  2023cites this paper
• Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols

  2023cites this paper
• Characterizing the Power of (Persistent) Randomness in Log-space

  2023cites this paper
• Polynomial-Time Pseudodeterministic Construction of Primes

  2023cites this paper
• Leakage-Resilient Hardness v.s. Randomness

  2022cites this paper
• Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

  2022cites this paper
• Quantified Derandomization: How to Find Water in the Ocean

  2022cites this paper
• Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle

  2022cites this paper
• Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

  2022cites this paper
• On the Range Avoidance Problem for Circuits

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

  2022cites this paper
• Derandomization from time-space tradeoffs

  2022cites this paper
• Characterizing derandomization through hardness of Levin-Kolmogorov complexity

  2022cites this paper
• Pseudodeterminism: promises and lowerbounds

  2022cites this paper
• Constructive Separations and Their Consequences

  2022cites this paper
• New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method

  2022cites this paper
• Circuit Lower Bounds from Unconditional Derandomization of Restricted Merlin Arthur Protocols

  2022cites this paper
• Lifting for Constant-Depth Circuits and Applications to MCSP

  2021cites this paper
• Error reduction for weighted PRGs against read once branching programs

  2021cites this paper
• How to Find Water in the Ocean: A Survey on Quantified Derandomization

  2021cites this paper
• Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions

  2021cites this paper
• Complexity Lower Bounds from Algorithm Design

  2021influential citation
• Promise Problems Meet Pseudodeterminism

  2021cites this paper
• On Limiting & Limited Non-determinism in NEXP Lower Bounds

  2021influential citation
• Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs

  2020cites this paper
• On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract

  2020cites this paper
• Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity

  2020cites this paper
• Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

  2020cites this paper
• StoqMA meets distribution testing

  2020cites this paper
• Two Combinatorial MA-Complete Problems

  2020cites this paper
• Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs

  2020cites this paper
• On The Utility of Fine-Grained Complexity Theory

  2020cites this paper
• Pr − ZSUBEXP (cid:42) Pr − RP

  2020influential citation
• A combinatorial MA-complete problem

  2020cites this paper
• Karp-Lipton Style Theorems

  2020cites this paper
• Unique Properties, Lower bounds & Derandomization

  2020influential citation
• Some Estimated Likelihoods for Computational Complexity

  2019cites this paper
• Hardness-Randomness Tradeoffs for Algebraic Computation

  2019influential citation
• 27 : 2 Hardness Magnification near State-OfThe-Art Lower Bounds

  2019cites this paper
• Proof complexity

  2019cites this paper
• The Computational Complexity Column

  2019cites this paper
• Relations and equivalences between circuit lower bounds and karp-lipton theorems

  2019cites this paper
• Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits

  2019cites this paper
• Efficient Construction of Rigid Matrices Using an NP Oracle

  2019cites this paper
• Stoquastic PCP vs. Randomness

  2019cites this paper
• AC0[p] Lower Bounds against MCSP via the Coin Problem

  2019cites this paper
• Hardness magnification near state-of-the-art lower bounds

  2019cites this paper
• Proving that prBPP = prP is as hard as proving that "almost NP" is not contained in P/poly

  2019cites this paper
• On the impact of cryptography on complexity theory

  2019cites this paper
• Bounded Independence Plus Noise

  2019cites this paper
• Pseudorandomness and the Minimum Circuit Size Problem

  2019cites this paper
• New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems

  2019cites this paper
• Derandomization from Hardness CS 254 Final Paper March 2019

  2019cites this paper
• UTIME Easy-witness Lemma & Some Consequences

  2019cites this paper
• Mathematics and Computation

  2019cites this paper
• N ov 2 01 7 Quantified Derandomization of Linear Threshold Circuits

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

  2018influential citation
• The Power of Natural Properties as Oracles

  2018cites this paper
• Below P vs NP: fine-grained hardness for big data problems

  2018cites this paper
• Connections between circuit analysis problems and circuit lower bounds

  2018cites this paper
• Hardness Magnification for Natural Problems

  2018influential citation
• Proving that prBPP=prP is as hard as "almost" proving that P ≠ NP

  2018cites this paper
• Circuit lower bounds from learning-theoretic approaches

  2018cites this paper
• Pseudo-derandomizing learning and approximation

  2018cites this paper
• Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds

  2018cites this paper
• Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP

  2018cites this paper
• Local reduction

  2018cites this paper
• Hitting sets with near-optimal error for read-once branching programs

  2018cites this paper
• Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

  2018cites this paper
• Some ways of thinking algorithmically about impossibility

  2017cites this paper
• Towards Hardness of Approximation for Polynomial Time Problems

  2017cites this paper
• Some Results on Circuit Lower Bounds and Derandomization of Arthur-Merlin Problems

  2017cites this paper
• A MODERN APPROACH

  2017cites this paper
• Quantified derandomization of linear threshold circuits

  2017cites this paper
• Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

  2017cites this paper
• Completeness for First-order Properties on Sparse Structures with Algorithmic Applications

  2017cites this paper
• On Limited Nondeterminism and ACC Circuit Lower Bounds

  2016cites this paper
• Lower Bounds on Black-Box Reductions of Hitting to Density Estimation

  2016cites this paper
• Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace

  2016cites this paper
• Learning Algorithms from Natural Proofs

  2016cites this paper
• Pseudodeterministic constructions in subexponential time

  2016influential citation