Monomials, multilinearity and identity testing in simple read-restricted circuits
From MaRDI portal
Publication:2637354
DOI10.1016/j.tcs.2014.01.005zbMath1285.68068MaRDI QIDQ2637354
Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
Publication date: 11 February 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.01.005
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On enumerating monomials and other combinatorial structures by polynomial interpolation
- The complexity of computing the permanent
- The orbit problem is in the GapL hierarchy
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- The complexity of matrix rank and feasible systems of linear equations
- The complexity of two problems on arithmetic circuits
- Deterministic Black-Box Identity Testing $pi$-Ordered Algebraic Branching Programs
- Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs
- Problems complete for deterministic logarithmic space
- An Optimal Parallel Algorithm for Formula Evaluation
- Relationships among $PL$, $\#L$, and the determinant
- Computational Complexity
- Jacobian hits circuits
- Derandomizing polynomial identity tests means proving circuit lower bounds