Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth (Q3012845): Difference between revisions

@@ 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.1007/978-3-642-22006-7_61
+Normal rank
@@ Property / OpenAlex ID @@
+W1580127749
@@ Property / OpenAlex ID: W1580127749 / rank @@
+Normal rank
@@ Property / cites work @@
+FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
+Normal rank
@@ Property / cites work @@
+PRIMES is in P
@@ Property / cites work: PRIMES is in P / rank @@
+Normal rank
@@ Property / cites work @@
+Q4267800
@@ Property / cites work: Q4267800 / rank @@
+Normal rank
@@ Property / cites work @@
+On uniformity within \(NC^ 1\)
@@ Property / cites work: On uniformity within \(NC^ 1\) / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of partial derivatives
@@ Property / cites work: The complexity of partial derivatives / rank @@
+Normal rank
@@ Property / cites work @@
+On defining integers and proving arithmetic circuit lower bounds
+Normal rank
@@ Property / cites work @@
+A probabilistic remark on algebraic program testing
+Normal rank
@@ Property / cites work @@
+Q4542578
@@ Property / cites work: Q4542578 / rank @@
+Normal rank
@@ Property / cites work @@
+Uniform constant-depth threshold circuits for division and iterated multiplication.
+Normal rank
@@ Property / cites work @@
+Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
+Normal rank
@@ Property / cites work @@
+Marginal hitting sets imply super-polynomial lower bounds for permanent
+Normal rank
@@ Property / cites work @@
+Derandomizing polynomial identity tests means proving circuit lower bounds
+Normal rank
@@ Property / cites work @@
+Interpolation in Valiant's theory
@@ Property / cites work: Interpolation in Valiant's theory / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002820
@@ Property / cites work: Q3002820 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds and separations for constant depth multilinear circuits
+Normal rank
@@ Property / cites work @@
+Fast Probabilistic Algorithms for Verification of Polynomial Identities
+Normal rank
@@ Property / cites work @@
+Depth-3 arithmetic circuits over fields of characteristic zero
+Normal rank
@@ Property / cites work @@
+PP is as Hard as the Polynomial-Time Hierarchy
@@ Property / cites work: PP is as Hard as the Polynomial-Time Hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity classes defined by counting quantifiers
+Normal rank
@@ Property / cites work @@
+The complexity of computing the permanent
@@ Property / cites work: The complexity of computing the permanent / rank @@
+Normal rank
@@ Property / cites work @@
+Q4393484
@@ Property / cites work: Q4393484 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of combinatorial problems with succinct input representation
+Normal rank
@@ Property / cites work @@
+#P-COMPLETENESS VIA MANY-ONE REDUCTIONS
@@ Property / cites work: #P-COMPLETENESS VIA MANY-ONE REDUCTIONS / rank @@
+Normal rank
@@ Property / cites work @@
+Q3851616
@@ Property / cites work: Q3851616 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:3012845