Upper and lower bounds for some depth-3 circuit classes (Q1377575): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ 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 @@
+Non-uniform automata over groups
@@ Property / cites work: Non-uniform automata over groups / rank @@
+Normal rank
@@ Property / cites work @@
+Representing Boolean functions as polynomials modulo composite numbers
+Normal rank
@@ Property / cites work @@
+When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
+Normal rank
@@ Property / cites work @@
+On ACC
@@ Property / cites work: On ACC / rank @@
+Normal rank
@@ Property / cites work @@
+A note on a theorem of Barrington, Straubing and Thérien
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+A note on the power of majority gates and modular gates
+Normal rank
@@ Property / cites work @@
+An oracle separating \(\oplus P\) from \(PP^{PH}\)
+Normal rank
@@ Property / cites work @@
+A weight-size trade-off for circuits with MOD m gates
+Normal rank
@@ Property / cites work @@
+A guided tour of Chernoff bounds
@@ Property / cites work: A guided tour of Chernoff bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Threshold circuits of bounded depth
@@ Property / cites work: Threshold circuits of bounded depth / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of small-depth threshold circuits
@@ Property / cites work: On the power of small-depth threshold circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Some notes on threshold circuits, and multiplication in depth 4
+Normal rank
@@ Property / cites work @@
+On the computational power of depth-2 circuits with threshold and modulo gates
+Normal rank
@@ Property / cites work @@
+Threshold circuits of small majority-depth
@@ Property / cites work: Threshold circuits of small majority-depth / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
+Normal rank
@@ Property / cites work @@
+\(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
+Normal rank
@@ Property / cites work @@
+Circuits constructed with MOD\(_ q\) gates cannot compute ``and'' in sublinear size
+Normal rank