Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Weighted gate elimination : Boolean dispersers for quadratic varieties imply improved circuit lower bounds. / Golovnev, Alexander; Kulikov, Alexander S.
ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, 2016. p. 405-411 (ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
}
TY - GEN
T1 - Weighted gate elimination
T2 - 7th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016
AU - Golovnev, Alexander
AU - Kulikov, Alexander S.
PY - 2016/1/14
Y1 - 2016/1/14
N2 - In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An (n; k; s)-quadratic disperser is a function on n variables that is not constant on any subset of Fn2 of size at least s that can be defined as the set of common roots of at most k quadratic polynomials. We show thfi at if a Boolean function f is a n; 1:83n; 2g(n)-quadratic disperser for any function g(n) = o(n) then the circuit size of f is at least 3:11n. In order to prove this, we generalize the gate elimination method so that the induction works on the size of the variety rather than on the number of variables as in previously known proofs.
AB - In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An (n; k; s)-quadratic disperser is a function on n variables that is not constant on any subset of Fn2 of size at least s that can be defined as the set of common roots of at most k quadratic polynomials. We show thfi at if a Boolean function f is a n; 1:83n; 2g(n)-quadratic disperser for any function g(n) = o(n) then the circuit size of f is at least 3:11n. In order to prove this, we generalize the gate elimination method so that the induction works on the size of the variety rather than on the number of variables as in previously known proofs.
KW - Boolean circuits
KW - Dispersers
KW - Lower bounds
UR - http://www.scopus.com/inward/record.url?scp=84966460693&partnerID=8YFLogxK
U2 - 10.1145/2840728.2840755
DO - 10.1145/2840728.2840755
M3 - Conference contribution
AN - SCOPUS:84966460693
T3 - ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
SP - 405
EP - 411
BT - ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
PB - Association for Computing Machinery
Y2 - 14 January 2016 through 16 January 2016
ER -
ID: 49824036