scientific article; zbMATH DE number 1559537

zbMATH Open0962.68058MaRDI QIDQ4526985FDOQ4526985

Authors: Russell Impagliazzo, A. Wigderson

Publication date: 28 February 2001

Title of this publication is not available (Why is that?)

Recommendations

On circuit lower bounds from derandomization
scientific article; zbMATH DE number 7758304
Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
Three XOR-lemmas -- an exposition
Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
2-Xor revisited: satisfiability and probabilities of functions
Hardness hypotheses, derandomization, and circuit complexity
FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Tighter connections between derandomization and circuit lower bounds
A Pseudorandom Oracle Characterization of ${\text{BPP}}$

zbMATH Keywords

pseudo-random generator

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25)

Cited In (only showing first 100 items - show all)

Sorting noisy data with partial information
ON GENERIC COMPLEXITY OF THE DISCRETE LOGARITHM PROBLEM
On the possibilities and limitations of pseudodeterministic algorithms
Improved bounds for quantified derandomization of constant-depth circuits and polynomials
Zero knowledge and circuit minimization
Almost $k$-wise independence and hard Boolean functions.
Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
On the power of conditional samples in distribution testing
Learning and incentives in user-generated content: multi-armed bandits with endogenous arms
Tally NP sets and easy census functions.
Verification of quantum computation: an overview of existing approaches
Title not available (Why is that?)
Knapsack in graph groups
Agnostic Learning from Tolerant Natural Proofs
Evaluation of circuits over nilpotent and polycyclic groups
Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
Simplified derandomization of BPP using a hitting set generator
Non-convex matrix completion and related problems via strong duality
High-rate codes with sublinear-time decoding
Extracting all the randomness and reducing the error in Trevisan's extractors
Explicit list-decodable codes with optimal rate for computationally bounded channels
New affine-invariant codes from lifting
On approximating the eigenvalues of stochastic matrices in probabilistic logspace
An energy complexity model for algorithms
A Tight Analysis of Bethe Approximation for Permanent
A note on perfect correctness by derandomization
ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM
Reachability in graph timelines
The journey from NP to TFNP hardness
On zero error algorithms having oracle access to one query
Massive online teaching to bounded learners
(Nondeterministic) hardness vs. non-malleability
Title not available (Why is that?)
Simple extractors via constructions of cryptographic pseudo-random generators
A PCP characterization of AM
Jacobian hits circuits: hitting sets, lower bounds for depth-$D$ occur-$k$ formulas and depth-3 transcendence degree-$k$ circuits
On the optimal compression of sets in PSPACE
Characterizing the sample complexity of private learners
Towards hardness of approximation for polynomial time problems
Quantified Derandomization: How to Find Water in the Ocean
Catch them if you can
Generic hardness of the Boolean satisfiability problem
On derandomized composition of Boolean functions
An equational approach to secure multi-party computation
A note on perfect correctness by derandomization
Parallel identity testing for skew circuits with big powers and applications
Simple and efficient batch verification techniques for verifiable delay functions
Title not available (Why is that?)
ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM
Derandomization from Algebraic Hardness
Title not available (Why is that?)
Some results on derandomization
Title not available (Why is that?)
Runtime guarantees for regression problems
Does looking inside a circuit help?
Barriers in cryptography with weak, correlated and leaky sources
The generic complexity of the bounded problem of graphs clustering
Amplification and Derandomization without Slowdown
Is privacy compatible with truthfulness?
Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?
Geometric complexity theory. V: Efficient algorithms for Noether normalization
ON GENERIC COMPLEXITY OF THE VALIDITY PROBLEM FOR BOOLEAN FORMULAS
Resource-based corruptions and the combinatorics of hidden diversity
Publicly verifiable proofs of sequential work
Parallel identity testing for skew circuits with big powers and applications
Catalytic space: non-determinism and hierarchy
Title not available (Why is that?)
$H$-wise independence
Evaluating matrix circuits
Properties and applications of Boolean function composition
Time hierarchies for sampling distributions
The generic complexity of the graph triangulation problem
Title not available (Why is that?)
Title not available (Why is that?)
Fourier concentration from shrinkage
In search of an easy witness: Exponential time vs. probabilistic polynomial time.
Mining circuit lower bound proofs for meta-algorithms
Random oracles and non-uniformity
Pseudorandom generators for combinatorial checkerboards
Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
Avoiding simplicity is complex
Collapsing and separating completeness notions under average-case and worst-case hypotheses
The complexity of explicit constructions
Pseudo-random generators for all hardnesses
Metric structures and probabilistic computation
Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
The garden-hose model
Differentially private data analysis of social networks via restricted sensitivity
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
On the power of nonuniformity in proofs of security
Space-bounded communication complexity
Proving that $\mathrm{prBPP}=\mathrm{prP}$ is as hard as proving that ``almost NP is not contained in P/poly
On pseudorandomness and resource-bounded measure
The parameterized complexity of maximality and minimality problems
Approximation of boolean functions by combinatorial rectangles
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
Infeasibility of instance compression and succinct PCPs for NP
Streaming computations with a loquacious prover
Hardness vs randomness

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4526985)