Exponential lower bound for bounded depth circuits with few threshold gates (Q413295): Difference between revisions

@@ Property / Mathematics Subject Classification ID @@
+Q17
@@ Property / Mathematics Subject Classification ID: 68Q17 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q15
@@ Property / Mathematics Subject Classification ID: 68Q15 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6030965
@@ Property / zbMATH DE Number: 6030965 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+computational complexity
@@ Property / zbMATH Keywords: computational complexity / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+Boolean circuit complexity
@@ Property / zbMATH Keywords: Boolean circuit complexity / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+threshold circuits
@@ Property / zbMATH Keywords: threshold circuits / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+threshold functions
@@ Property / zbMATH Keywords: threshold functions / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+bounded depth circuits
@@ Property / zbMATH Keywords: bounded depth circuits / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+lower bounds
@@ Property / zbMATH Keywords: lower bounds / 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.ipl.2011.12.011
+Normal rank
@@ Property / OpenAlex ID @@
+W1982984553
@@ Property / OpenAlex ID: W1982984553 / rank @@
+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 @@
+Complex polynomials and circuit lower bounds for modular counting
+Normal rank
@@ Property / cites work @@
+When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
+Normal rank
@@ Property / cites work @@
+PP is closed under intersection
@@ Property / cites work: PP is closed under intersection / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity measures and decision tree complexity: a survey.
+Normal rank
@@ Property / cites work @@
+Automata, Languages and Programming
@@ Property / cites work: Automata, Languages and Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Majority gates vs. general weighted threshold gates
+Normal rank
@@ Property / cites work @@
+Learning and Lower Bounds for AC 0 with Threshold Gates
+Normal rank
@@ Property / cites work @@
+Threshold circuits of bounded depth
@@ Property / cites work: Threshold circuits of bounded depth / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
+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 @@
+Natural proofs
@@ Property / cites work: Natural proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:413295