On derandomization and average-case complexity of monotone functions (Q428873): Difference between revisions

@@ Property / DOI @@
-.1016/j.tcs.2012.02.017
@@ Property / DOI: 10.1016/j.tcs.2012.02.017 / rank @@
-Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q17
@@ Property / Mathematics Subject Classification ID: 68Q17 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q87
@@ Property / Mathematics Subject Classification ID: 68Q87 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+W20
@@ Property / Mathematics Subject Classification ID: 68W20 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q15
@@ Property / Mathematics Subject Classification ID: 68Q15 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6049393
@@ Property / zbMATH DE Number: 6049393 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+derandomization
@@ Property / zbMATH Keywords: derandomization / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+monotone circuits
@@ Property / zbMATH Keywords: monotone circuits / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+monotone functions
@@ Property / zbMATH Keywords: monotone functions / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+randomized algorithm
@@ Property / zbMATH Keywords: randomized algorithm / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+pseudorandom generators
@@ Property / zbMATH Keywords: pseudorandom generators / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+average-case complexity
@@ Property / zbMATH Keywords: average-case complexity / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2012.02.017
+Normal rank
@@ Property / OpenAlex ID @@
+W2047406446
@@ Property / OpenAlex ID: W2047406446 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal bounds for the approximation of Boolean functions and some applications
+Normal rank
@@ Property / cites work @@
+Q2784326
@@ Property / cites work: Q2784326 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4385519
@@ Property / cites work: Q4385519 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Fourier spectrum of monotone functions
@@ Property / cites work: On the Fourier spectrum of monotone functions / rank @@
+Normal rank
@@ Property / cites work @@
+General Pseudo-random Generators from Weaker Models of Computation
+Normal rank
@@ Property / cites work @@
+Derandomizing polynomial identity tests means proving circuit lower bounds
+Normal rank
@@ Property / cites work @@
+Space hierarchy results for randomized and other semantic models
+Normal rank
@@ Property / cites work @@
+Learning Boolean formulas
@@ Property / cites work: Learning Boolean formulas / rank @@
+Normal rank
@@ Property / cites work @@
+Monotone Boolean functions
@@ Property / cites work: Monotone Boolean functions / rank @@
+Normal rank
@@ Property / cites work @@
+Q4788614
@@ Property / cites work: Q4788614 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4938667
@@ Property / cites work: Q4938667 / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness amplification within NP
@@ Property / cites work: Hardness amplification within NP / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on monotone complexity of the logical permanent
+Normal rank
@@ Property / cites work @@
+Simple extractors for all min-entropies and a new pseudorandom generator
+Normal rank
@@ Property / cites work @@
+The gap between monotone and non-monotone circuit complexity is exponential
+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 @@
+Negation is Powerless for Boolean Slice Functions
@@ Property / cites work: Negation is Powerless for Boolean Slice Functions / rank @@
+Normal rank
@@ Property / DOI @@
+.1016/J.TCS.2012.02.017
@@ Property / DOI: 10.1016/J.TCS.2012.02.017 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:428873