Towards a tight hardness–randomness connection between permanent and arithmetic circuit identity testing
- 31 December 2012
- journal article
- research article
- Published by Elsevier in Information Processing Letters
- Vol. 112 (24) , 969-975
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- On Defining Integers And Proving Arithmetic Circuit Lower Boundscomputational complexity, 2009
- Proving Lower Bounds Via Pseudo-random Generators2005
- The Complexity of Factors of Multivariate PolynomialsFoundations of Computational Mathematics, 2004
- Cook's versus Valiant's hypothesisTheoretical Computer Science, 2000
- The complexity of matrix rank and feasible systems of linear equationscomputational complexity, 1999
- Combinatorial NullstellensatzCombinatorics, Probability and Computing, 1999
- On computing the determinant in small parallel time using a small number of processorsInformation Processing Letters, 1984
- Probabilistic Algorithms for Deciding Equivalence of Straight-Line ProgramsJournal of the ACM, 1983
- Testing polynomials which are easy to compute (Extended Abstract)1980
- A probabilistic remark on algebraic program testingInformation Processing Letters, 1978