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

DOI10.1016/S0022-0000(02)00024-7zbMath1059.68047OpenAlexW2158747250MaRDI QIDQ1872732

Valentine Kabanets, Avi Wigderson, Russell Impagliazzo

Publication date: 14 May 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(02)00024-7

zbMATH Keywords

search space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Local Reductions, Unnamed Item, Circuit lower bounds from learning-theoretic approaches, Quantified Derandomization: How to Find Water in the Ocean, A zero-one law for RP and derandomization of AM if NP is not small, Nonuniform ACC Circuit Lower Bounds, Amplifying circuit lower bounds against polynomial time, with applications, Is Valiant-Vazirani's isolation probability improvable?, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, Robust simulations and significant separations, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, Pseudorandom generators for combinatorial checkerboards, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, The power of natural properties as oracles, Unnamed Item, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, Massive online teaching to bounded learners, Learning mixtures of spherical gaussians, Low-weight halfspaces for sparse boolean vectors, Learnability of DNF with representation-specific queries, Can theories be tested?, Making evolution rigorous, On the convergence of the Hegselmann-Krause system, Is privacy compatible with truthfulness?, Differentially private data analysis of social networks via restricted sensitivity, Characterizing the sample complexity of private learners, Barriers in cryptography with weak, correlated and leaky sources, On the possibilities and limitations of pseudodeterministic algorithms, Evasiveness through a circuit lens, The garden-hose model, Space-bounded communication complexity, Towards an optimal query efficient PCP?, A characterization of approximation resistance for even k-partite CSPs, On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction, On the power of many one-bit provers, Approaching utopia, Learning and incentives in user-generated content, Welfare maximization and the supermodular degree, Reachability in graph timelines, Runtime guarantees for regression problems, An energy complexity model for algorithms, Streaming computations with a loquacious prover, Adversary lower bound for the k-sum problem, Stronger methods of making quantum interactive proofs perfectly complete, Active self-assembly of algorithmic shapes and patterns in polylogarithmic time, An equational approach to secure multi-party computation, Publicly verifiable proofs of sequential work, On the power of nonuniformity in proofs of security, Fast reductions from RAMs to delegatable succinct constraint satisfaction problems, Resource-based corruptions and the combinatorics of hidden diversity, Time hierarchies for sampling distributions, Properties and applications of boolean function composition, Pseudo-partitions, transversality and locality, Competing provers protocols for circuit evaluation, Catch them if you can, Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints, Robust optimization in the presence of uncertainty, Sorting noisy data with partial information, New affine-invariant codes from lifting, H-wise independence, Sparse extractor families for all the entropy, On the power of conditional samples in distribution testing, Relations between average-case and worst-case complexity, Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, New algorithms and lower bounds for circuits with linear threshold gates, On uniformity and circuit lower bounds, Upward separations and weaker hypotheses in resource-bounded measure, NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth, NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES, Avoiding simplicity is complex, Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, Unnamed Item, Pseudo-random generators for all hardnesses, Natural Proofs versus Derandomization, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, In a World of P=BPP, Unnamed Item, Relations and equivalences between circuit lower bounds and karp-lipton theorems, Hardness magnification near state-of-the-art lower bounds, Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly, Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, Complexity theory. Abstracts from the workshop held November 11--17, 2018, Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace, Unnamed Item, Efficient Construction of Rigid Matrices Using an NP Oracle, Mining circuit lower bound proofs for meta-algorithms

Cites Work