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

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

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

Faculty of Mathemathics and Computer Sciences

DOI

https://doi.org/10.1007/978-3-642-30870-3_44
Final published version

Alexander S. Kulikov
Olga Melanich
Ivan Mihajlin

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

Original language	English
Title of host publication	How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings
Pages	432-439
Number of pages	8
DOIs	https://doi.org/10.1007/978-3-642-30870-3_44
State	Published - 18 Jun 2012
Event	Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 - Cambridge, United Kingdom Duration: 18 Jun 2012 → 23 Jun 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7318 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012
Country/Territory	United Kingdom
City	Cambridge
Period	18/06/12 → 23/06/12

Scopus subject areas

Theoretical Computer Science
Computer Science(all)

ID: 49825851