Hardness vs randomness
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3980487 (Why is no real title available?)
- scientific article; zbMATH DE number 3724342 (Why is no real title available?)
- A Note on Randomized Polynomial Time
- Alternation
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Probabilistic encryption
- Pseudorandom bits for constant depth circuits
- Pseudorandom number generation and space complexity
- Turing machines that take advice
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
Cited in
(only showing first 100 items - show all)- On Yao's XOR-lemma
- Satisfiability and derandomization for small polynomial threshold circuits
- Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
- 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?)
- Pseudo-deterministic proofs
- Pseudodeterministic constructions in subexponential time
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- scientific article; zbMATH DE number 7250153 (Why is no real title available?)
- Leakage resilience, targeted pseudorandom generators, and mild derandomization of Arthur-Merlin protocols
- Regularization of low error PCPs and an application to MCSP
- Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields
- Pseudorandom generators for combinatorial checkerboards
- Random walks on graphs and Monte Carlo methods
- Mining circuit lower bound proofs for meta-algorithms
- Hamming weight proofs of proximity with one-sided error
- On polynomial approximations to \(\mathrm{AC}^0\)
- 3SUM, 3XOR, triangles
- Underapproximation for model-checking based on universal circuits
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- Pseudorandom generators for low sensitivity functions
- Black-box separations for non-interactive classical commitments in a quantum world
- On the Symmetries of and Equivalence Test for Design Polynomials.
- 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
- The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
- Limitations of Hardness vs. Randomness under Uniform Reductions
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- The complexity of explicit constructions
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Circuit complexity before the dawn of the new millennium
- Deterministic function computation with chemical reaction networks
- A Selection of Lower Bounds for Arithmetic Circuits
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- Extractors: low entropy requirements colliding with non-malleability
- NL-printable sets and nondeterministic Kolmogorov complexity
- Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Efficient constructions of hitting sets for systems of linear functions
- Randomness and intractability in Kolmogorov complexity
- Pseudo-random generators for all hardnesses
- Cell-probe lower bounds for the partial match problem
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
- On randomized versus deterministic computation
- Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- On explicit constructions of designs
- Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
- 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
- On the volume of unit balls of finite-dimensional Lorentz spaces
- Entropy numbers of finite-dimensional embeddings
- Characterizing polynomial complexity classes by reducibilities
- scientific article; zbMATH DE number 1857655 (Why is no real title available?)
- Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
- Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- On pseudorandomness and resource-bounded measure
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
- A Survey of Data Structures in the Bitprobe Model
- Pseudorandom generators for space-bounded computation
- Feasibly constructive proofs of succinct weak circuit lower bounds
- On derandomization and average-case complexity of monotone functions
- Regarding two conjectures on clique and biclique partitions
- Expander-based cryptography meets natural proofs
- On closure properties of bounded two-sided error complexity classes
- Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
- ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
- Learning algorithms from circuit lower bounds
- scientific article; zbMATH DE number 4186980 (Why is no real title available?)
- Upward separations and weaker hypotheses in resource-bounded measure
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Random low-degree polynomials are hard to approximate
- Agnostic Learning from Tolerant Natural Proofs
- scientific article; zbMATH DE number 7758331 (Why is no real title available?)
- Pseudorandom bits and lower bounds for randomized Turing machines
- Uniformly hard languages.
- On optimal language compression for sets in PSPACE/poly
- On extracting space-bounded Kolmogorov complexity
- Hardness amplification within NP
- Hitting sets for orbits of circuit classes and polynomial families
- Pseudorandom Generators in Propositional Proof Complexity
- scientific article; zbMATH DE number 7561748 (Why is no real title available?)
- Lower bounds for the circuit size of partially homogeneous polynomials
- In a world of \(\mathrm{P}=\mathrm{BPP}\)
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Low-depth witnesses are easy to find
- Simple analysis of graph tests for linearity and PCP
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Efficient Construction of Rigid Matrices Using an NP Oracle
- Negation-limited formulas
- Comparing notions of computational entropy
- The size of SPP
- Arthur and Merlin as Oracles
- Explicit list-decodable codes with optimal rate for computationally bounded channels
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- Easiness assumptions and hardness tests: Trading time for zero error
This page was built for publication: Hardness vs randomness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1337458)
