Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
An elementary proof of a 3n - o(n) lower bound on the circuit complexity of affine dispersers. / Demenkov, Evgeny; Kulikov, Alexander S.
Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings. 2011. p. 256-265 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6907 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
}
TY - GEN
T1 - An elementary proof of a 3n - o(n) lower bound on the circuit complexity of affine dispersers
AU - Demenkov, Evgeny
AU - Kulikov, Alexander S.
PY - 2011/9/1
Y1 - 2011/9/1
N2 - A Boolean function f: double-struck F2n → double-struck F 2 is called an affine disperser of dimension d, if f is not constant on any affine subspace of double-struck F2 n of dimension at least d. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for sublinear d. The main motivation for studying such functions comes from extracting randomness from structured sources of imperfect randomness. In this paper, we show another application: we give a very simple proof of a 3n-o(n) lower bound on the circuit complexity (over the full binary basis) of affine dispersers for sublinear dimension. The same lower bound 3n-o(n) (but for a completely different function) was given by Blum in 1984 and is still the best known. The main technique is to substitute variables by linear functions. This way the function is restricted to an affine subspace of F2n. An affine disperser for sublinear dimension then guarantees that one can make n-o(n) such substitutions before the function degenerates. It remains to show that each such substitution eliminates at least 3 gates from a circuit.
AB - A Boolean function f: double-struck F2n → double-struck F 2 is called an affine disperser of dimension d, if f is not constant on any affine subspace of double-struck F2 n of dimension at least d. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for sublinear d. The main motivation for studying such functions comes from extracting randomness from structured sources of imperfect randomness. In this paper, we show another application: we give a very simple proof of a 3n-o(n) lower bound on the circuit complexity (over the full binary basis) of affine dispersers for sublinear dimension. The same lower bound 3n-o(n) (but for a completely different function) was given by Blum in 1984 and is still the best known. The main technique is to substitute variables by linear functions. This way the function is restricted to an affine subspace of F2n. An affine disperser for sublinear dimension then guarantees that one can make n-o(n) such substitutions before the function degenerates. It remains to show that each such substitution eliminates at least 3 gates from a circuit.
UR - http://www.scopus.com/inward/record.url?scp=80052123323&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22993-0_25
DO - 10.1007/978-3-642-22993-0_25
M3 - Conference contribution
AN - SCOPUS:80052123323
SN - 9783642229923
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 256
EP - 265
BT - Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings
T2 - 36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011
Y2 - 22 August 2011 through 26 August 2011
ER -
ID: 49825721