scientific article; zbMATH DE number 1559537
From MaRDI portal
Publication:4526985
zbMath0962.68058MaRDI QIDQ4526985
Avi Wigderson, Russell Impagliazzo
Publication date: 28 February 2001
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
In search of an easy witness: Exponential time vs. probabilistic polynomial time., Uniformly hard languages., Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Circuit lower bounds from learning-theoretic approaches, A note on perfect correctness by derandomization, Random oracles and non-uniformity, Hardness assumptions in the foundations of theoretical computer science, Reconstructive dispersers and hitting set generators, Can we locally compute sparse connected subgraphs?, Improved hardness amplification in NP, The size of SPP, Derandomized parallel repetition theorems for free games, Zero knowledge and circuit minimization, Robust simulations and significant separations, Generic hardness of the Boolean satisfiability problem, On approximating the eigenvalues of stochastic matrices in probabilistic logspace, A broader view on the limitations of information processing and communication by nature, Parallel Identity Testing for Skew Circuits with Big Powers and Applications, Pseudorandom generators for combinatorial checkerboards, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Infeasibility of instance compression and succinct PCPs for NP, Hardness amplification within NP against deterministic algorithms, Approximation of boolean functions by combinatorial rectangles, Almost \(k\)-wise independence and hard Boolean functions., Query complexity in errorless hardness amplification, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Catalytic space: non-determinism and hierarchy, Knapsack in graph groups, On derandomizing Yao's weak-to-strong OWF construction, Simple and efficient batch verification techniques for verifiable delay functions, Low-depth witnesses are easy to find, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, Complexity of hard-core set proofs, Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs, Arthur and Merlin as oracles, Isolation, matching, and counting uniform and nonuniform upper bounds, 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, Relations between average-case and worst-case complexity, Randomness buys depth for approximate counting, Computation of best possible low degree expanders, The parameterized complexity of maximality and minimality problems, Evaluation of circuits over nilpotent and polycyclic groups, Small-bias is not enough to hit read-once CNF, Improved direct product theorems for randomized query complexity, Collapsing and separating completeness notions under average-case and worst-case hypotheses, The complexity of explicit constructions, Avoiding simplicity is complex, Metric structures and probabilistic computation, Lower bounds for non-black-box zero knowledge, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, Fourier concentration from shrinkage, Simple extractors via constructions of cryptographic pseudo-random generators, On zero error algorithms having oracle access to one query, Explicit list-decodable codes with optimal rate for computationally bounded channels, On derandomized composition of Boolean functions, Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits, Investigations Concerning the Structure of Complete Sets, Geometric complexity theory V: Efficient algorithms for Noether normalization, Improved bounds for quantified derandomization of constant-depth circuits and polynomials, Verification of quantum computation: an overview of existing approaches, Chernoff-type direct product theorems, Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, Computing (and Life) Is All about Tradeoffs, Book Review: Inevitable randomness in discrete mathematics, Tally NP sets and easy census functions., Randomness vs time: Derandomization under a uniform assumption, Mining circuit lower bound proofs for meta-algorithms, On optimal language compression for sets in PSPACE/poly, Randomness extraction in computability theory, Randomized and Symmetric Catalytic Computation, The Journey from NP to TFNP Hardness, Quantified Derandomization: How to Find Water in the Ocean, Unnamed Item, Derandomization from Algebraic Hardness, Evaluating Matrix Circuits, Entropy of Weight Distributions of Small-Bias Spaces and Pseudobinomiality, Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, Unnamed Item, Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error, (Nondeterministic) hardness vs. non-malleability, Effective guessing has unlikely consequences, Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?, The power of natural properties as oracles, Polyhedral techniques in combinatorial optimization: matchings and tours, Worst-case subexponential attacks on PRGs of constant degree or constant locality, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), Some games on Turing machines and power from random strings, Paradigms for Unconditional Pseudorandom Generators, Interactions of computational complexity theory and mathematics, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Amplification and Derandomization without Slowdown, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, 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, Agnostic Learning from Tolerant Natural Proofs, ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM, ON GENERIC COMPLEXITY OF THE VALIDITY PROBLEM FOR BOOLEAN FORMULAS, ON GENERIC COMPLEXITY OF THE DISCRETE LOGARITHM PROBLEM, ON GENERIC NP-COMPLETENESS OF THE BOOLEAN SATISFIABILITY PROBLEM, ON GENERIC COMPLEXITY OF THE PROBLEM OF FINDING ROOTS IN GROUPS OF RESIDUES, ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM, ON GENERIC COMPLEXITY OF THE PROBLEM OF REPRESENTATION OF NATURAL NUMBERS BY SUM OF TWO SQUARES, ON GENERIC COMPLEXITY OF THE EXISTENTIAL THEORIES, Pseudo-Derandomizing Learning and Approximation, A PCP Characterization of AM, On pseudorandomness and resource-bounded measure, Some Recent Results on Local Testing of Sparse Linear Codes, Pseudorandom generators without the XOR lemma, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Easiness assumptions and hardness tests: Trading time for zero error, Parallel identity testing for skew circuits with big powers and applications, Extracting all the randomness and reducing the error in Trevisan's extractors, Hardness amplification within NP, Pseudo-random generators for all hardnesses, Unnamed Item, Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification, Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More), Simplified Derandomization of BPP Using a Hitting Set Generator, In a World of P=BPP, On Yao’s XOR-Lemma, On the Optimal Compression of Sets in PSPACE, Unnamed Item, Typically-correct derandomization for small time and space, Does Looking Inside a Circuit Help, High-rate codes with sublinear-time decoding, Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace, Unnamed Item, A Tight Analysis of Bethe Approximation for Permanent, A Note on Perfect Correctness by Derandomization, The generic complexity of the bounded problem of graphs clustering, The generic complexity of the graph triangulation problem
