Natural Proofs versus Derandomization (Q2805512): Difference between revisions

@@ Property / cites work @@
+Q4474202
@@ Property / cites work: Q4474202 / rank @@
+Normal rank
@@ Property / cites work @@
+Power from Random Strings
@@ Property / cites work: Power from Random Strings / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
+Normal rank
@@ Property / cites work @@
+\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
+Normal rank
@@ Property / cites work @@
+Q4440438
@@ Property / cites work: Q4440438 / rank @@
+Normal rank
@@ Property / cites work @@
+On ACC
@@ Property / cites work: On ACC / rank @@
+Normal rank
@@ Property / cites work @@
+Unconditional Lower Bounds against Advice
@@ Property / cites work: Unconditional Lower Bounds against Advice / rank @@
+Normal rank
@@ Property / cites work @@
+Unbounded fan-in circuits and associative functions
+Normal rank
@@ Property / cites work @@
+The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data
+Normal rank
@@ Property / cites work @@
+Almost-natural proofs
@@ Property / cites work: Almost-natural proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Hierarchies for semantic classes
@@ Property / cites work: Hierarchies for semantic classes / rank @@
+Normal rank
@@ Property / cites work @@
+Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+Normal rank
@@ Property / cites work @@
+Randomness vs time: Derandomization under a uniform assumption
+Normal rank
@@ Property / cites work @@
+Q2904790
@@ Property / cites work: Q2904790 / rank @@
+Normal rank
@@ Property / cites work @@
+Easiness assumptions and hardness tests: Trading time for zero error
+Normal rank
@@ Property / cites work @@
+Circuit minimization problem
@@ Property / cites work: Circuit minimization problem / rank @@
+Normal rank
@@ Property / cites work @@
+Derandomizing polynomial identity tests means proving circuit lower bounds
+Normal rank
@@ Property / cites work @@
+Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+Some observations on the probabilistic algorithms and NP-hard problems
+Normal rank
@@ Property / cites work @@
+Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds
+Normal rank
@@ Property / cites work @@
+Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs
+Normal rank
@@ Property / cites work @@
+Q4938667
@@ Property / cites work: Q4938667 / rank @@
+Normal rank
@@ Property / cites work @@
+Number-theoretic constructions of efficient pseudo-random functions
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+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 @@
+Pseudo-random generators for all hardnesses
@@ Property / cites work: Pseudo-random generators for all hardnesses / rank @@
+Normal rank
@@ Property / cites work @@
+Improving Exhaustive Search Implies Superpolynomial Lower Bounds
+Normal rank
@@ Property / cites work @@
+A Turing machine time hierarchy
@@ Property / cites work: A Turing machine time hierarchy / rank @@
+Normal rank