Q5092470 (Q5092470): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Power from Random Strings
@@ Property / cites work: Power from Random Strings / rank @@
+Normal rank
@@ Property / cites work @@
+Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
+Normal rank
@@ Property / cites work @@
+Q5111269
@@ Property / cites work: Q5111269 / rank @@
+Normal rank
@@ Property / cites work @@
+New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
+Normal rank
@@ Property / cites work @@
+Amplifying lower bounds by means of self-reducibility
+Normal rank
@@ Property / cites work @@
+\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
+Normal rank
@@ Property / cites work @@
+How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
+Normal rank
@@ Property / cites work @@
+On Worst‐Case to Average‐Case Reductions for NP Problems
+Normal rank
@@ Property / cites work @@
+On lower bounds for read-\(k\)-times branching programs
+Normal rank
@@ Property / cites work @@
+Some results on derandomization
@@ Property / cites work: Some results on derandomization / rank @@
+Normal rank
@@ Property / cites work @@
+Q4256650
@@ Property / cites work: Q4256650 / rank @@
+Normal rank
@@ Property / cites work @@
+Learning algorithms from natural proofs
@@ Property / cites work: Learning algorithms from natural proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Q5875777
@@ Property / cites work: Q5875777 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5091189
@@ Property / cites work: Q5091189 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of promise problems with applications to public-key cryptography
+Normal rank
@@ Property / cites work @@
+Random-Self-Reducibility of Complete Sets
@@ Property / cites work: Random-Self-Reducibility of Complete Sets / rank @@
+Normal rank
@@ Property / cites work @@
+A Sample of Samplers: A Computational Perspective on Sampling
+Normal rank
@@ Property / cites work @@
+On derandomizing algorithms that err extremely rarely
+Normal rank
@@ Property / cites work @@
+A Pseudorandom Generator from any One-way Function
+Normal rank
@@ Property / cites work @@
+Using Nondeterminism to Amplify Hardness
@@ Property / cites work: Using Nondeterminism to Amplify Hardness / rank @@
+Normal rank
@@ Property / cites work @@
+Unexpected hardness results for Kolmogorov complexity under uniform reductions
+Normal rank
@@ Property / cites work @@
+Q5121893
@@ Property / cites work: Q5121893 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5111137
@@ Property / cites work: Q5111137 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5368752
@@ Property / cites work: Q5368752 / rank @@
+Normal rank
@@ Property / cites work @@
+On the NP-Completeness of the Minimum Circuit Size Problem.
+Normal rank
@@ Property / cites work @@
+Q4252738
@@ Property / cites work: Q4252738 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Circuit minimization problem
@@ Property / cites work: Circuit minimization problem / rank @@
+Normal rank
@@ Property / cites work @@
+Turing machines that take advice
@@ Property / cites work: Turing machines that take advice / rank @@
+Normal rank
@@ Property / cites work @@
+Boosting and hard-core set construction
@@ Property / cites work: Boosting and hard-core set construction / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+On the Complexity of Learning Minimum Time-Bounded Turing Machines
+Normal rank
@@ Property / cites work @@
+Randomness conservation inequalities; information and independence in mathematical theories
+Normal rank
@@ Property / cites work @@
+Average Case Complete Problems
@@ Property / cites work: Average Case Complete Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
+Normal rank
@@ Property / cites work @@
+Q5368903
@@ Property / cites work: Q5368903 / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators for space-bounded computation
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness magnification near state-of-the-art lower bounds
+Normal rank
@@ Property / cites work @@
+Some Results on Average-Case Hardness Within the Polynomial Hierarchy
+Normal rank
@@ Property / cites work @@
+Extracting all the randomness and reducing the error in Trevisan's extractors
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
+Normal rank
@@ Property / cites work @@
+Natural proofs
@@ Property / cites work: Natural proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness Amplification Proofs Require Majority
@@ Property / cites work: Hardness Amplification Proofs Require Majority / rank @@
+Normal rank
@@ Property / cites work @@
+Decoding of Reed Solomon codes beyond the error-correction bound
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators without the XOR lemma
@@ Property / cites work: Pseudorandom generators without the XOR lemma / rank @@
+Normal rank
@@ Property / cites work @@
+A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
+Normal rank
@@ Property / cites work @@
+Pseudorandomness and average-case complexity via uniform reductions
+Normal rank
@@ Property / cites work @@
+An Unconditional Study of Computational Zero Knowledge
+Normal rank
@@ Property / cites work @@
+Pseudorandomness
@@ Property / cites work: Pseudorandomness / rank @@
+Normal rank
@@ Property / cites work @@
+NP is as easy as detecting unique solutions
@@ Property / cites work: NP is as easy as detecting unique solutions / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of constructing pseudorandom generators from hard functions
+Normal rank
@@ Property / cites work @@
+Locally Decodable Codes
@@ Property / cites work: Locally Decodable Codes / rank @@
+Normal rank