Standard

New Lower Bounds on Circuit Size of Multi-output Functions. / Demenkov, Evgeny; Kulikov, Alexander S.; Melanich, Olga; Mihajlin, Ivan.

в: Theory of Computing Systems, Том 56, № 4, 01.05.2015, стр. 630-642.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Demenkov, E, Kulikov, AS, Melanich, O & Mihajlin, I 2015, 'New Lower Bounds on Circuit Size of Multi-output Functions', Theory of Computing Systems, Том. 56, № 4, стр. 630-642. https://doi.org/10.1007/s00224-014-9590-4

APA

Demenkov, E., Kulikov, A. S., Melanich, O., & Mihajlin, I. (2015). New Lower Bounds on Circuit Size of Multi-output Functions. Theory of Computing Systems, 56(4), 630-642. https://doi.org/10.1007/s00224-014-9590-4

Vancouver

Demenkov E, Kulikov AS, Melanich O, Mihajlin I. New Lower Bounds on Circuit Size of Multi-output Functions. Theory of Computing Systems. 2015 Май 1;56(4):630-642. https://doi.org/10.1007/s00224-014-9590-4

Author

Demenkov, Evgeny ; Kulikov, Alexander S. ; Melanich, Olga ; Mihajlin, Ivan. / New Lower Bounds on Circuit Size of Multi-output Functions. в: Theory of Computing Systems. 2015 ; Том 56, № 4. стр. 630-642.

BibTeX

@article{45ebba6b07f74ff0b5782e6db7382363,
title = "New Lower Bounds on Circuit Size of Multi-output Functions",
abstract = "Let Bn, m be the set of all Boolean functions from {0, 1}n to {0, 1}m, Bn = Bn, 1 and U2 = B2∖{⊕, ≡}. In this paper, we prove the following two new lower bounds on the circuit size over U2.1.A lower bound (Formula presented.) for a linear function f ∈ Bn − 1,logn. The lower bound follows from the following more general result: for any matrix A ∈ {0, 1}m × n with n pairwise different non-zero columns and b ∈ {0, 1}m,(Formula presented.)2.A lower bound (Formula presented.) for f ∈ Bn, n. Again, this is a consequence of the following result: for any f ∈ Bn satisfying a certain simple property,(Formula presented.) where g(f) ∈ Bn, n is defined as follows: g(f) = (f ⊕ x1, … , f ⊕ xn) (to get a 7n − o(n) lower bound it remains to plug in a known function f ∈ Bn, 1 with (Formula presented.)).",
keywords = "Boolean functions, Circuit complexity, Gate elimination, Lower bounds",
author = "Evgeny Demenkov and Kulikov, {Alexander S.} and Olga Melanich and Ivan Mihajlin",
year = "2015",
month = may,
day = "1",
doi = "10.1007/s00224-014-9590-4",
language = "English",
volume = "56",
pages = "630--642",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer Nature",
number = "4",

}

RIS

TY - JOUR

T1 - New Lower Bounds on Circuit Size of Multi-output Functions

AU - Demenkov, Evgeny

AU - Kulikov, Alexander S.

AU - Melanich, Olga

AU - Mihajlin, Ivan

PY - 2015/5/1

Y1 - 2015/5/1

N2 - Let Bn, m be the set of all Boolean functions from {0, 1}n to {0, 1}m, Bn = Bn, 1 and U2 = B2∖{⊕, ≡}. In this paper, we prove the following two new lower bounds on the circuit size over U2.1.A lower bound (Formula presented.) for a linear function f ∈ Bn − 1,logn. The lower bound follows from the following more general result: for any matrix A ∈ {0, 1}m × n with n pairwise different non-zero columns and b ∈ {0, 1}m,(Formula presented.)2.A lower bound (Formula presented.) for f ∈ Bn, n. Again, this is a consequence of the following result: for any f ∈ Bn satisfying a certain simple property,(Formula presented.) where g(f) ∈ Bn, n is defined as follows: g(f) = (f ⊕ x1, … , f ⊕ xn) (to get a 7n − o(n) lower bound it remains to plug in a known function f ∈ Bn, 1 with (Formula presented.)).

AB - Let Bn, m be the set of all Boolean functions from {0, 1}n to {0, 1}m, Bn = Bn, 1 and U2 = B2∖{⊕, ≡}. In this paper, we prove the following two new lower bounds on the circuit size over U2.1.A lower bound (Formula presented.) for a linear function f ∈ Bn − 1,logn. The lower bound follows from the following more general result: for any matrix A ∈ {0, 1}m × n with n pairwise different non-zero columns and b ∈ {0, 1}m,(Formula presented.)2.A lower bound (Formula presented.) for f ∈ Bn, n. Again, this is a consequence of the following result: for any f ∈ Bn satisfying a certain simple property,(Formula presented.) where g(f) ∈ Bn, n is defined as follows: g(f) = (f ⊕ x1, … , f ⊕ xn) (to get a 7n − o(n) lower bound it remains to plug in a known function f ∈ Bn, 1 with (Formula presented.)).

KW - Boolean functions

KW - Circuit complexity

KW - Gate elimination

KW - Lower bounds

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

U2 - 10.1007/s00224-014-9590-4

DO - 10.1007/s00224-014-9590-4

M3 - Article

AN - SCOPUS:84939999354

VL - 56

SP - 630

EP - 642

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -

ID: 49824305