Standard

A 5n - o(n) lower bound on the circuit size over U 2 of a linear Boolean function. / Kulikov, Alexander S.; Melanich, Olga; Mihajlin, Ivan.

How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings. 2012. p. 432-439 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7318 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Kulikov, AS, Melanich, O & Mihajlin, I 2012, A 5n - o(n) lower bound on the circuit size over U 2 of a linear Boolean function. in How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7318 LNCS, pp. 432-439, Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, United Kingdom, 18/06/12. https://doi.org/10.1007/978-3-642-30870-3_44

APA

Kulikov, A. S., Melanich, O., & Mihajlin, I. (2012). A 5n - o(n) lower bound on the circuit size over U 2 of a linear Boolean function. In How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings (pp. 432-439). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7318 LNCS). https://doi.org/10.1007/978-3-642-30870-3_44

Vancouver

Kulikov AS, Melanich O, Mihajlin I. A 5n - o(n) lower bound on the circuit size over U 2 of a linear Boolean function. In How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings. 2012. p. 432-439. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-30870-3_44

Author

Kulikov, Alexander S. ; Melanich, Olga ; Mihajlin, Ivan. / A 5n - o(n) lower bound on the circuit size over U 2 of a linear Boolean function. How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings. 2012. pp. 432-439 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{18fec06c558a41a7ae9ad68f94af9362,
title = "A 5n - o(n) lower bound on the circuit size over U 2 of a linear Boolean function",
abstract = "We give a simple proof of a 5n - o(n) lower bound on the circuit size over U 2 of a linear function f(x) = Ax where A ε {0,1} log n x n (here, U 2 is the set of all Boolean binary functions except for parity and its complement).",
author = "Kulikov, {Alexander S.} and Olga Melanich and Ivan Mihajlin",
year = "2012",
month = jun,
day = "18",
doi = "10.1007/978-3-642-30870-3_44",
language = "English",
isbn = "9783642308697",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "432--439",
booktitle = "How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings",
note = "Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 ; Conference date: 18-06-2012 Through 23-06-2012",

}

RIS

TY - GEN

T1 - A 5n - o(n) lower bound on the circuit size over U 2 of a linear Boolean function

AU - Kulikov, Alexander S.

AU - Melanich, Olga

AU - Mihajlin, Ivan

PY - 2012/6/18

Y1 - 2012/6/18

N2 - We give a simple proof of a 5n - o(n) lower bound on the circuit size over U 2 of a linear function f(x) = Ax where A ε {0,1} log n x n (here, U 2 is the set of all Boolean binary functions except for parity and its complement).

AB - We give a simple proof of a 5n - o(n) lower bound on the circuit size over U 2 of a linear function f(x) = Ax where A ε {0,1} log n x n (here, U 2 is the set of all Boolean binary functions except for parity and its complement).

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

U2 - 10.1007/978-3-642-30870-3_44

DO - 10.1007/978-3-642-30870-3_44

M3 - Conference contribution

AN - SCOPUS:84862193996

SN - 9783642308697

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 432

EP - 439

BT - How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings

T2 - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012

Y2 - 18 June 2012 through 23 June 2012

ER -

ID: 49825851