Natural Proofs versus Derandomization (Q2805512): Difference between revisions

← Older edit

@@ aliases / en / 0 / aliases / en / 0 @@
+Natural proofs versus derandomization
@@ description / en / description / en @@
-scientific article
+scientific article; zbMATH DE number 6326936
@@ Property / author @@
-R. Ryan Williams
@@ Property / author: R. Ryan Williams / rank @@
-Normal rank
@@ Property / title @@
+Natural proofs versus derandomization (English)
@@ Property / title: Natural proofs versus derandomization (English) / rank @@
+Normal rank
@@ Property / zbMATH Open document ID @@
+.68135
@@ Property / zbMATH Open document ID: 1293.68135 / rank @@
+Normal rank
@@ Property / DOI @@
+.1145/2488608.2488612
@@ Property / DOI: 10.1145/2488608.2488612 / rank @@
+Normal rank
@@ Property / published in @@
+Proceedings of the forty-fifth annual ACM symposium on Theory of Computing
+Normal rank
@@ Property / publication date @@
+August 2014Timestamp +2014-08-07T00:00:00Z
Timezone +00:00
Calendar Gregorian
Precision 1 day
Before 0
After 0
-Timestamp
++2014-08-07T00:00:00Z
-Timezone
++00:00
-Calendar
+Gregorian
-Precision
+day
 Before
 After
@@ Property / publication date: 7 August 2014 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6326936
@@ Property / zbMATH DE Number: 6326936 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+lower bounds
@@ Property / zbMATH Keywords: lower bounds / rank @@
+Normal rank
@@ Property / author @@
+R. Ryan Williams
@@ Property / author: R. Ryan Williams / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q113779157
@@ Property / Wikidata QID: Q113779157 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2343516500
@@ Property / OpenAlex ID: W2343516500 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2026704052
@@ Property / OpenAlex ID: W2026704052 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.1891
@@ Property / arXiv ID: 1212.1891 / rank @@
+Normal rank
@@ 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