Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. / Find, Magnus Gausdal; Golovnev, Alexander; Hirsch, Edward A.; Kulikov, Alexander S.
Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. Institute of Electrical and Electronics Engineers Inc., 2016. стр. 89-98 7782921 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Том 2016-December).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function
AU - Find, Magnus Gausdal
AU - Golovnev, Alexander
AU - Hirsch, Edward A.
AU - Kulikov, Alexander S.
PY - 2016/12/14
Y1 - 2016/12/14
N2 - We consider Boolean circuits over the full binary basis. We prove a (3+1/86)n-o(n) lower bound onthe size of such a circuit for an explicitly definedpredicate, namely an affine disperser for sublinear dimension. This improves the 3n-o(n) bound of Norbert Blum (1984).The proof is based on the gate elimination technique extended with the following three ideas. We generalize the computational model by allowing circuits to contain cycles, this in turn allows us to perform affine substitutions. We use a carefully chosen circuit complexity measure to track the progress of the gate elimination process. Finally, we use quadratic substitutions that may be viewed as delayed affine substitutions.
AB - We consider Boolean circuits over the full binary basis. We prove a (3+1/86)n-o(n) lower bound onthe size of such a circuit for an explicitly definedpredicate, namely an affine disperser for sublinear dimension. This improves the 3n-o(n) bound of Norbert Blum (1984).The proof is based on the gate elimination technique extended with the following three ideas. We generalize the computational model by allowing circuits to contain cycles, this in turn allows us to perform affine substitutions. We use a carefully chosen circuit complexity measure to track the progress of the gate elimination process. Finally, we use quadratic substitutions that may be viewed as delayed affine substitutions.
KW - Affine disperser
KW - Boolean circuits
KW - Lower bounds
UR - http://www.scopus.com/inward/record.url?scp=85009344853&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2016.19
DO - 10.1109/FOCS.2016.19
M3 - Conference contribution
AN - SCOPUS:85009344853
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 89
EP - 98
BT - Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
Y2 - 9 October 2016 through 11 October 2016
ER -
ID: 49823726