Academic
Publications
Circuit Complexity and Multiplicative Complexity of Boolean Functions

Circuit Complexity and Multiplicative Complexity of Boolean Functions,10.1007/978-3-642-13962-8_27,Arist Kojevnikov,Alexander S. Kulikov

Circuit Complexity and Multiplicative Complexity of Boolean Functions   (Citations: 1)
BibTex | RIS | RefWorks Download
In this note, we use lower bounds on Boolean multiplicative complexity to prove lower bounds on Boolean circuit complexity. We give a very simple proof of a 7n=3 c lower bound on the circuit complexity of a large class of functions representable by high degree polynomials over GF(2). The key idea of the proof is a circuit complexity measure assigning dierent weights to XOR and AND gates.
Conference: Conference on Computability in Europe - CIE , pp. 239-245, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: