Monomials, multilinearity and identity testing in simple read-restricted circuits

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

zbMATH Keywords

computational complexity; arithmetic circuits

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Building above read-once polynomials: identity testing and hardness of representation

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