Standard

New upper bounds on the Boolean circuit complexity of symmetric functions. / Demenkov, E.; Kojevnikov, A.; Kulikov, A.; Yaroslavtsev, G.

In: Information Processing Letters, Vol. 110, No. 7, 01.03.2010, p. 264-267.

Research output: Contribution to journal › Article › peer-review

Harvard

Demenkov, E, Kojevnikov, A, Kulikov, A & Yaroslavtsev, G 2010, 'New upper bounds on the Boolean circuit complexity of symmetric functions', Information Processing Letters, vol. 110, no. 7, pp. 264-267. https://doi.org/10.1016/j.ipl.2010.01.007

APA

Demenkov, E., Kojevnikov, A., Kulikov, A., & Yaroslavtsev, G. (2010). New upper bounds on the Boolean circuit complexity of symmetric functions. Information Processing Letters, 110(7), 264-267. https://doi.org/10.1016/j.ipl.2010.01.007

Vancouver

Demenkov E, Kojevnikov A, Kulikov A, Yaroslavtsev G. New upper bounds on the Boolean circuit complexity of symmetric functions. Information Processing Letters. 2010 Mar 1;110(7):264-267. https://doi.org/10.1016/j.ipl.2010.01.007

Author

Demenkov, E. ; Kojevnikov, A. ; Kulikov, A. ; Yaroslavtsev, G. / New upper bounds on the Boolean circuit complexity of symmetric functions. In: Information Processing Letters. 2010 ; Vol. 110, No. 7. pp. 264-267.

BibTeX

@article{9fc58020c20344678df3e5051447309d,
title = "New upper bounds on the Boolean circuit complexity of symmetric functions",
abstract = "In this note, we present improved upper bounds on the circuit complexity of symmetric Boolean functions. In particular, we describe circuits of size 4.5 n + o (n) for any symmetric function of n variables, as well as circuits of size 3n for MOD3n function.",
keywords = "Boolean circuit complexity, Computational complexity, Modular functions, Symmetric functions, Upper bounds",
author = "E. Demenkov and A. Kojevnikov and A. Kulikov and G. Yaroslavtsev",
year = "2010",
month = mar,
day = "1",
doi = "10.1016/j.ipl.2010.01.007",
language = "English",
volume = "110",
pages = "264--267",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "7",

}

RIS

TY - JOUR

T1 - New upper bounds on the Boolean circuit complexity of symmetric functions

AU - Demenkov, E.

AU - Kojevnikov, A.

AU - Kulikov, A.

AU - Yaroslavtsev, G.

PY - 2010/3/1

Y1 - 2010/3/1

N2 - In this note, we present improved upper bounds on the circuit complexity of symmetric Boolean functions. In particular, we describe circuits of size 4.5 n + o (n) for any symmetric function of n variables, as well as circuits of size 3n for MOD3n function.

AB - In this note, we present improved upper bounds on the circuit complexity of symmetric Boolean functions. In particular, we describe circuits of size 4.5 n + o (n) for any symmetric function of n variables, as well as circuits of size 3n for MOD3n function.

KW - Boolean circuit complexity

KW - Computational complexity

KW - Modular functions

KW - Symmetric functions

KW - Upper bounds

UR - http://www.scopus.com/inward/record.url?scp=76849094975&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2010.01.007

DO - 10.1016/j.ipl.2010.01.007

M3 - Article

AN - SCOPUS:76849094975

VL - 110

SP - 264

EP - 267

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 7

ER -

ID: 49825441