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

DOI10.1016/j.tcs.2014.01.005zbMath1285.68068OpenAlexW2140443719MaRDI 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 complexityarithmetic circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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