Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing (Q1941704): 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.1016/j.ipl.2012.08.001
+Normal rank
@@ Property / OpenAlex ID @@
+W2068275484
@@ Property / OpenAlex ID: W2068275484 / rank @@
+Normal rank
@@ Property / cites work @@
+FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
+Normal rank
@@ Property / cites work @@
+The complexity of matrix rank and feasible systems of linear equations
+Normal rank
@@ Property / cites work @@
+Combinatorial Nullstellensatz
@@ Property / cites work: Combinatorial Nullstellensatz / rank @@
+Normal rank
@@ Property / cites work @@
+On computing the determinant in small parallel time using a small number of processors
+Normal rank
@@ Property / cites work @@
+Cook's versus Valiant's hypothesis
@@ Property / cites work: Cook's versus Valiant's hypothesis / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of factors of multivariate polynomials
+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 @@
+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 @@
+Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
+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 @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+On uniform circuit complexity
@@ Property / cites work: On uniform circuit complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Probabilistic Algorithms for Verification of Polynomial Identities
+Normal rank
@@ Property / cites work @@
+Complexity classes defined by counting quantifiers
+Normal rank
@@ Property / cites work @@
+The complexity of constructing pseudorandom generators from hard functions
+Normal rank
@@ Property / cites work @@
+The complexity of combinatorial problems with succinct input representation
+Normal rank
@@ Property / cites work @@
+Q3851616
@@ Property / cites work: Q3851616 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1941704