scientific article; zbMATH DE number 1559537
From MaRDI portal
Publication:4526985
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)- On Yao's XOR-lemma
- Fourier concentration from shrinkage
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- scientific article; zbMATH DE number 1833418 (Why is no real title available?)
- Sorting noisy data with partial information
- On the possibilities and limitations of pseudodeterministic algorithms
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- Leakage resilience, targeted pseudorandom generators, and mild derandomization of Arthur-Merlin protocols
- Random oracles and non-uniformity
- Regularization of low error PCPs and an application to MCSP
- Pseudorandom generators for combinatorial checkerboards
- Mining circuit lower bound proofs for meta-algorithms
- One-way functions and pKt complexity
- On generic complexity of the graph clustering problem with bounded clusters
- Worst-case subexponential attacks on PRGs of constant degree or constant locality
- Pseudo-derandomizing learning and approximation
- The combinatorial game \textsc{Nofil} played on Steiner triple systems
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Almost \(k\)-wise independence and hard Boolean functions.
- Zero knowledge and circuit minimization
- On generic NP-completeness of the Boolean satisfiability problem
- Avoiding simplicity is complex
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- The complexity of explicit constructions
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Metric structures and probabilistic computation
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Pseudo-random generators for all hardnesses
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
- The garden-hose model
- Evasiveness through a circuit lens (extended abstract)
- 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
- Paradigms for Unconditional Pseudorandom Generators
- Some games on Turing machines and power from random strings
- Tally NP sets and easy census functions.
- Learning and incentives in user-generated content: multi-armed bandits with endogenous arms
- Approximation of boolean functions by combinatorial rectangles
- The parameterized complexity of maximality and minimality problems
- Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
- Infeasibility of instance compression and succinct PCPs for NP
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- On pseudorandomness and resource-bounded measure
- On generic complexity of the validity problem for Boolean formulas
- Verification of quantum computation: an overview of existing approaches
- Streaming computations with a loquacious prover
- Computation of best possible low degree expanders
- scientific article; zbMATH DE number 7561753 (Why is no real title available?)
- Knapsack in graph groups
- Some recent results on local testing of sparse linear codes
- On the generic complexity of the discrete logarithm problem in Lucas sequences
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Evaluation of circuits over nilpotent and polycyclic groups
- Hardness vs randomness
- Agnostic Learning from Tolerant Natural Proofs
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Uniformly hard languages.
- Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
- On optimal language compression for sets in PSPACE/poly
- Hardness amplification within NP
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- scientific article; zbMATH DE number 7561748 (Why is no real title available?)
- In a world of \(\mathrm{P}=\mathrm{BPP}\)
- Low-depth witnesses are easy to find
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Improved hardness amplification in NP
- Simplified derandomization of BPP using a hitting set generator
- The size of SPP
- Approaching utopia, strong truthfulness and externality-resistant mechanisms
- Non-convex matrix completion and related problems via strong duality
- Matrix completion and related problems via strong duality
- Explicit list-decodable codes with optimal rate for computationally bounded channels
- High-rate codes with sublinear-time decoding
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- Complexity of hard-core set proofs
- Easiness assumptions and hardness tests: Trading time for zero error
- Extracting all the randomness and reducing the error in Trevisan's extractors
- New affine-invariant codes from lifting
- Making evolution rigorous: the error threshold
- On generic complexity of the discrete logarithm problem
- Pseudorandomness when the odds are against you
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- On exponential-time hypotheses, derandomization, and circuit lower bounds
- An energy complexity model for algorithms
- On the power of many one-bit provers
- A note on perfect correctness by derandomization
- Symmetric exponential time requires near-maximum circuit size
- Effective guessing has unlikely consequences
- A Tight Analysis of Bethe Approximation for Permanent
- Randomness-Efficient Sampling Within NC 1
- Unambiguous, randomized, and symmetric catalytic computation
- Reachability in graph timelines
- Two combinatorial MA-complete problems
- Total functions in the polynomial hierarchy
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Book review of: Inevitable randomness in discrete mathematics, by József Beck
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)
