When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one (Q1346613): Difference between revisions

@@ Property / cites work @@
+Depth reduction for circuits of unbounded fan-in
@@ Property / cites work: Depth reduction for circuits of unbounded fan-in / rank @@
+Normal rank
@@ Property / cites work @@
+Some connections between bounded query classes and non-uniform complexity.
+Normal rank
@@ Property / cites work @@
+The expressive power of voting polynomials
@@ Property / cites work: The expressive power of voting polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Random oracles separate PSPACE from the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+On ACC
@@ Property / cites work: On ACC / rank @@
+Normal rank
@@ Property / cites work @@
+PP is closed under intersection
@@ Property / cites work: PP is closed under intersection / rank @@
+Normal rank
@@ Property / cites work @@
+With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+PP is closed under truth-table reductions
@@ Property / cites work: PP is closed under truth-table reductions / rank @@
+Normal rank
@@ Property / cites work @@
+Rational approximation to \(|x|\)
@@ Property / cites work: Rational approximation to \(|x|\) / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating threshold circuits by rational functions
+Normal rank
@@ Property / cites work @@
+Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
+Normal rank