Keywords
Boolean functionMathematicsParity functionMultiplicative functionDiscrete mathematicsCircuit complexityCombinatoricsUpper and lower boundsBoolean circuitBoolean expressionFunction (biology)Exponential functionElectronic circuit
Affiliated Institutions
Related Publications
Elementary gates for quantum computation
We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values (x,y) to (x,x \\oplus y)) is universal ...
Quantum circuit complexity
We propose a complexity model of quantum circuits analogous to the standard (acyclic) Boolean circuit model. It is shown that any function computable in polynomial time by a qua...
Distributed Learning, Communication Complexity and Privacy
We consider the problem of PAC-learning from distributed data and analyze fundamental communication complexity questions involved. We provide general upper and lower bounds on t...
Genetic Programming: On the Programming of Computers by Means of Natural Selection
Background on genetic algorithms, LISP, and genetic programming hierarchical problem-solving introduction to automatically-defined functions - the two-boxes problem problems tha...
Optimal eavesdropping in quantum cryptography. I. Information bound and optimal strategy
We consider the Bennett-Brassard cryptographic scheme, which uses two conjugate quantum bases. An eavesdropper who attempts to obtain information on qubits sent in one of the ba...
Publication Info
- Year
- 2000
- Type
- article
- Volume
- 235
- Issue
- 1
- Pages
- 43-57
- Citations
- 93
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
93
OpenAlex
Cite This
Joan Boyar,
René Peralta,
Denis Pochuev
(2000).
On the multiplicative complexity of Boolean functions over the basis (∧,⊕,1).
Theoretical Computer Science
, 235
(1)
, 43-57.
https://doi.org/10.1016/s0304-3975(99)00182-6
Identifiers
- DOI
- 10.1016/s0304-3975(99)00182-6