scientific article; zbMATH DE number 1559537
From MaRDI portal
Publication:4526985
zbMATH Open0962.68058MaRDI QIDQ4526985FDOQ4526985
A. Wigderson, Russell Impagliazzo
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}}$
Cited In (only showing first 100 items - show all)
- 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
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
- 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
- Adversary lower bound for the k-sum problem
- Streaming computations with a loquacious prover
- Hardness vs randomness
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- On Yao’s XOR-Lemma
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Hardness amplification within NP
- Uniformly hard languages.
- Low-depth witnesses are easy to find
- Improved hardness amplification in NP
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Easiness assumptions and hardness tests: Trading time for zero error
- The size of SPP
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- Complexity of hard-core set proofs
- ON GENERIC COMPLEXITY OF THE PROBLEM OF REPRESENTATION OF NATURAL NUMBERS BY SUM OF TWO SQUARES
- Title not available (Why is that?)
- Robust simulations and significant separations
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Pseudorandom generators without the XOR lemma
- A broader view on the limitations of information processing and communication by nature
- Learnability of DNF with representation-specific queries
- Competing provers protocols for circuit evaluation
- On the convergence of the Hegselmann-Krause system
- Welfare maximization and the supermodular degree
- Hardness amplification within NP against deterministic algorithms
- Chernoff-type direct product theorems
- Query complexity in errorless hardness amplification
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- Approaching utopia
- Lower bounds for non-black-box zero knowledge
- In a World of P=BPP
- Randomness vs time: Derandomization under a uniform assumption
- Randomness buys depth for approximate counting
- Robust optimization in the presence of uncertainty
- Derandomization from Algebraic Hardness
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Title not available (Why is that?)
- Improved direct product theorems for randomized query complexity
- Arthur and Merlin as oracles
- Relations between average-case and worst-case complexity
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
- Derandomized parallel repetition theorems for free games
- Small-bias is not enough to hit read-once CNF
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Investigations Concerning the Structure of Complete Sets
- Title not available (Why is that?)
- 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.
- H-wise independence
- On the power of conditional samples in distribution testing
- Properties and applications of boolean function composition
- Tally NP sets and easy census functions.
- Title not available (Why is that?)
- Evaluating Matrix Circuits
- A Note on Perfect Correctness by Derandomization
- 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
- On optimal language compression for sets in PSPACE/poly
- Does Looking Inside a Circuit Help
- 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
- Evasiveness through a circuit lens
- A Tight Analysis of Bethe Approximation for Permanent
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)
