The graph of multiplication is equivalent to counting

DOI10.1016/0020-0190(92)90180-4zbMath0748.68018OpenAlexW1997350267MaRDI QIDQ1190513

Samuel R. Buss

Publication date: 26 September 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90180-4

zbMATH Keywords

circuit complexitythreshold circuitsconstant depth circuitsgraph of multiplication

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Efficient data structures for Boolean functions, A lower bound for integer multiplication on randomized ordered read-once branching programs., A bounded arithmetic AID for Frege systems

Cites Work

• Unnamed Item
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Constant Depth Reducibility