Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(6)
Boolean Circuits
Boolean Function
Circuit Complexity
Function Representation
Large Classes
Lower Bound
Subscribe
Academic
Publications
Circuit Complexity and Multiplicative Complexity of Boolean Functions
Circuit Complexity and Multiplicative Complexity of Boolean Functions,10.1007/9783642139628_27,Arist Kojevnikov,Alexander S. Kulikov
Edit
Circuit Complexity and Multiplicative Complexity of Boolean Functions
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Arist Kojevnikov
,
Alexander S. Kulikov
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. 239245, 2010
DOI:
10.1007/9783642139628_27
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
adsabs.harvard.edu
)
(
logic.pdmi.ras.ru
)
(
dx.doi.org
)
More »
Citation Context
(1)
...• Kojevnikov and Kulikov [
10
] proved a 7n/3 − c lower bound for functions with high multiplicative complexity...
Evgeny Demenkov
,
et al.
An Elementary Proof of 3no(n) Lower Bound on the Circuit Complexity o...
References
(11)
On The Multiplicative Complexity of Boolean Functions over the Basis
(
Citations: 15
)
Joan Boyar
,
René Peralta
,
Denis Pochuev
Published in 1998.
An Explicit Lower Bound of 5n  o(n) for Boolean Circuits
(
Citations: 18
)
Kazuo Iwama
,
Hiroki Morizumi
Conference:
Mathematical Foundations of Computer Science  MFCS
, pp. 353364, 2002
A 2.5 nlower bound on the combinational complexity of Boolean functions
(
Citations: 15
)
Wolfgang J. Paul
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 2736, 1975
The Multiplicative Complexity of Boolean Functions
(
Citations: 2
)
Clauspeter Schnorr
,
Fachbereich Mathematik
Conference:
Applied Algebra, Algebraic Algorithms and ErrorCorrecting Codes  AAECC
, pp. 4558, 1988
On the Combinational Complexity of Certain Symmetric Boolean Functions
(
Citations: 14
)
Larry J. Stockmeyer
Journal:
Theory of Computing Systems / Mathematical Systems Theory  MST
, vol. 10, pp. 323336, 1977
Sort by:
Citations
(1)
An Elementary Proof of 3no(n) Lower Bound on the Circuit Complexity of Affine Dispersers
Evgeny Demenkov
,
Alexander S. Kulikov
Journal:
Electronic Colloquium on Computational Complexity  ECCC
, vol. 18, 2011