Parity, circuits, and the polynomial-time hierarchy (Q3318683): Difference between revisions

← Older edit

@@ Property / Wikidata QID @@
+Q55967164
@@ Property / Wikidata QID: Q55967164 / rank @@
+Normal rank
@@ Property / cites work @@
+On counting problems and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+A second step toward the polynomial hierarchy
@@ Property / cites work: A second step toward the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Q3288996
@@ Property / cites work: Q3288996 / rank @@
+Normal rank
@@ Property / cites work @@
+Relativization of questions about log space computability
+Normal rank
@@ Property / cites work @@
+Q4172915
@@ Property / cites work: Q4172915 / rank @@
+Normal rank
@@ Property / cites work @@
+A 3n-lower bound on the network complexity of Boolean functions
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Q3662618
@@ Property / cites work: Q3662618 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4131648
@@ Property / cites work: Q4131648 / rank @@
+Normal rank
@@ Property / Recommended article @@
+Constant Depth Reducibility
@@ Property / Recommended article: Constant Depth Reducibility / rank @@
+Normal rank
@@ Property / Recommended article: Constant Depth Reducibility / qualifier @@
+Similarity Score: 0.86259735Amount 0.86259735
Unit 1
-Amount
+.86259735
 Unit
@@ Property / Recommended article: Constant Depth Reducibility / qualifier @@
+Recommender Run: Recommender Run 2
@@ Property / Recommended article @@
+Random oracles separate PSPACE from the polynomial-time hierarchy
+Normal rank
+Similarity Score: 0.83992994Amount 0.83992994
Unit 1
-Amount
+.83992994
 Unit
+Recommender Run: Recommender Run 2
@@ Property / Recommended article @@
+On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy
+Normal rank
+Similarity Score: 0.8369864Amount 0.8369864
Unit 1
-Amount
+.8369864
 Unit
+Recommender Run: Recommender Run 2
@@ Property / Recommended article @@
+Relating polynomial time to constant depth
+Normal rank
+Similarity Score: 0.8360082Amount 0.8360082
Unit 1
-Amount
+.8360082
 Unit
+Recommender Run: Recommender Run 2
@@ Property / Recommended article @@
+Exponential size lower bounds for some depth three circuits
+Normal rank
+Similarity Score: 0.83200085Amount 0.83200085
Unit 1
-Amount
+.83200085
 Unit
+Recommender Run: Recommender Run 2
@@ Property / Recommended article @@
+On the complexity and depth of circuits that realize partial Boolean functions
+Normal rank
+Similarity Score: 0.83094275Amount 0.83094275
Unit 1
-Amount
+.83094275
 Unit
+Recommender Run: Recommender Run 2
@@ Property / Recommended article @@
+Exponential lower bound for bounded depth circuits with few threshold gates
+Normal rank
+Similarity Score: 0.82757115Amount 0.82757115
Unit 1
-Amount
+.82757115
 Unit
+Recommender Run: Recommender Run 2
@@ Property / Recommended article @@
+Threshold circuits of small majority-depth
+Normal rank
+Similarity Score: 0.8251574Amount 0.8251574
Unit 1
-Amount
+.8251574
 Unit
+Recommender Run: Recommender Run 2
@@ Property / Recommended article @@
+Depth reduction for circuits of unbounded fan-in
+Normal rank
+Similarity Score: 0.82493395Amount 0.82493395
Unit 1
-Amount
+.82493395
 Unit
+Recommender Run: Recommender Run 2
@@ Property / Recommended article @@
+Breaking the minsky-papert barrier for constant-depth circuits
+Normal rank
+Similarity Score: 0.8219884Amount 0.8219884
Unit 1
-Amount
+.8219884
 Unit
+Recommender Run: Recommender Run 2
@@ Property / DBLP publication ID @@
+journals/mst/FurstSS84
@@ Property / DBLP publication ID: journals/mst/FurstSS84 / rank @@
+Normal rank