Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. Cheraghchi, M., Kabanets, V., Lu, Z., & Myrisiotis, D. ACM Transactions on Computation Theory (ToCT), 2020. Preliminary version in Proceedings of ICALP 2019.Paper Link doi abstract bibtex The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $θ$, for a given parameter $θ$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a PRG is called local if its output bit strings, when viewed as the truth table of a Boolean function, can be computed by a Boolean circuit of small size. We get new and improved lower bounds for MCSP that almost match the best-known lower bounds against several circuit models. Specifically, we show that computing MCSP, on functions with a truth table of length $N$, requires: 1) $N^{3-o(1)}$-size de Morgan formulas, improving the recent $N^{2-o(1)}$ lower bound by Hirahara and Santhanam (CCC 2017), 2) $N^{2-o(1)}$-size formulas over an arbitrary basis or general branching programs (no non-trivial lower bound was known for MCSP against these models), and 3) $2^{Ω(N^{1/(d+1.01)})}$-size depth-$d$ $\mathrm{AC}^0$ circuits, improving the (implicit, in their work) exponential size lower bound by Allender et al. (SICOMP 2006). The $\mathrm{AC}^0$ lower bound stated above matches the best-known $\mathrm{AC}^0$ lower bound (for \tt PARITY) up to a small additive constant in the depth. Also, for the special case of depth-$2$ circuits (i.e., CNFs or DNFs), we get an optimal lower bound of \(2^Ω(N)\) for MCSP.
@ARTICLE{ref:CKLM20,
title = {Circuit Lower Bounds for {MCSP} from Local
Pseudorandom Generators},
author = {Mahdi Cheraghchi and Valentine Kabanets and Zhenjian
Lu and Dimitrios Myrisiotis},
year = 2020,
journal = {{ACM Transactions on Computation Theory (ToCT)}},
volume = 12,
number = 3,
articleno = 21,
note = {Preliminary version in {Proceedings of ICALP 2019}.},
url_Paper = {https://eccc.weizmann.ac.il/report/2019/022},
url_Link = {https://dl.acm.org/doi/abs/10.1145/3404860},
doi = {10.1145/3404860},
abstract = {The Minimum Circuit Size Problem (MCSP) asks if a
given truth table of a Boolean function $f$ can be
computed by a Boolean circuit of size at most
$\theta$, for a given parameter $\theta$. We improve
several circuit lower bounds for MCSP, using
pseudorandom generators (PRGs) that are local; a PRG
is called \textit{local} if its output bit strings,
when viewed as the truth table of a Boolean
function, can be computed by a Boolean circuit of
small size. We get new and improved lower bounds for
MCSP that almost match the best-known lower bounds
against several circuit models. Specifically, we
show that computing MCSP, on functions with a truth
table of length $N$, requires: 1) $N^{3-o(1)}$-size
de Morgan formulas, improving the recent
$N^{2-o(1)}$ lower bound by Hirahara and Santhanam
(CCC 2017), 2) $N^{2-o(1)}$-size formulas over an
arbitrary basis or general branching programs (no
non-trivial lower bound was known for MCSP against
these models), and 3)
$2^{\Omega(N^{1/(d+1.01)})}$-size depth-$d$
$\mathrm{AC}^0$ circuits, improving the (implicit,
in their work) exponential size lower bound by
Allender et al. (SICOMP 2006). The $\mathrm{AC}^0$
lower bound stated above matches the best-known
$\mathrm{AC}^0$ lower bound (for {\tt PARITY}) up to
a small \textit{additive} constant in the
depth. Also, for the special case of depth-$2$
circuits (i.e., CNFs or DNFs), we get an optimal
lower bound of \(2^{{\Omega}(N)}\) for MCSP. },
keywords = {Minimum circuit size problem (MCSP), circuit lower
bounds, pseudorandom generators (PRGs),
constant-depth circuits, branching programs, local
PRGs, de Morgan formulas}
}
Downloads: 0
{"_id":"PhPqsTQN2B9LZjkSv","bibbaseid":"cheraghchi-kabanets-lu-myrisiotis-circuitlowerboundsformcspfromlocalpseudorandomgenerators-2020","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Cheraghchi, M.","Kabanets, V.","Lu, Z.","Myrisiotis, D."],"bibdata":{"bibtype":"article","type":"article","title":"Circuit Lower Bounds for MCSP from Local Pseudorandom Generators","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["Valentine"],"propositions":[],"lastnames":["Kabanets"],"suffixes":[]},{"firstnames":["Zhenjian"],"propositions":[],"lastnames":["Lu"],"suffixes":[]},{"firstnames":["Dimitrios"],"propositions":[],"lastnames":["Myrisiotis"],"suffixes":[]}],"year":"2020","journal":"ACM Transactions on Computation Theory (ToCT)","volume":"12","number":"3","articleno":"21","note":"Preliminary version in Proceedings of ICALP 2019.","url_paper":"https://eccc.weizmann.ac.il/report/2019/022","url_link":"https://dl.acm.org/doi/abs/10.1145/3404860","doi":"10.1145/3404860","abstract":"The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $θ$, for a given parameter $θ$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a PRG is called <i>local</i> if its output bit strings, when viewed as the truth table of a Boolean function, can be computed by a Boolean circuit of small size. We get new and improved lower bounds for MCSP that almost match the best-known lower bounds against several circuit models. Specifically, we show that computing MCSP, on functions with a truth table of length $N$, requires: 1) $N^{3-o(1)}$-size de Morgan formulas, improving the recent $N^{2-o(1)}$ lower bound by Hirahara and Santhanam (CCC 2017), 2) $N^{2-o(1)}$-size formulas over an arbitrary basis or general branching programs (no non-trivial lower bound was known for MCSP against these models), and 3) $2^{Ω(N^{1/(d+1.01)})}$-size depth-$d$ $\\mathrm{AC}^0$ circuits, improving the (implicit, in their work) exponential size lower bound by Allender et al. (SICOMP 2006). The $\\mathrm{AC}^0$ lower bound stated above matches the best-known $\\mathrm{AC}^0$ lower bound (for \\tt PARITY) up to a small <i>additive</i> constant in the depth. Also, for the special case of depth-$2$ circuits (i.e., CNFs or DNFs), we get an optimal lower bound of \\(2^Ω(N)\\) for MCSP. ","keywords":"Minimum circuit size problem (MCSP), circuit lower bounds, pseudorandom generators (PRGs), constant-depth circuits, branching programs, local PRGs, de Morgan formulas","bibtex":"@ARTICLE{ref:CKLM20,\n title =\t {Circuit Lower Bounds for {MCSP} from Local\n Pseudorandom Generators},\n author =\t {Mahdi Cheraghchi and Valentine Kabanets and Zhenjian\n Lu and Dimitrios Myrisiotis},\n year =\t 2020,\n journal =\t {{ACM Transactions on Computation Theory (ToCT)}},\n volume =\t 12,\n number =\t 3,\n articleno =\t 21,\n note =\t {Preliminary version in {Proceedings of ICALP 2019}.},\n url_Paper =\t {https://eccc.weizmann.ac.il/report/2019/022},\n url_Link =\t {https://dl.acm.org/doi/abs/10.1145/3404860},\n doi =\t\t {10.1145/3404860},\n abstract =\t {The Minimum Circuit Size Problem (MCSP) asks if a\n given truth table of a Boolean function $f$ can be\n computed by a Boolean circuit of size at most\n $\\theta$, for a given parameter $\\theta$. We improve\n several circuit lower bounds for MCSP, using\n pseudorandom generators (PRGs) that are local; a PRG\n is called \\textit{local} if its output bit strings,\n when viewed as the truth table of a Boolean\n function, can be computed by a Boolean circuit of\n small size. We get new and improved lower bounds for\n MCSP that almost match the best-known lower bounds\n against several circuit models. Specifically, we\n show that computing MCSP, on functions with a truth\n table of length $N$, requires: 1) $N^{3-o(1)}$-size\n de Morgan formulas, improving the recent\n $N^{2-o(1)}$ lower bound by Hirahara and Santhanam\n (CCC 2017), 2) $N^{2-o(1)}$-size formulas over an\n arbitrary basis or general branching programs (no\n non-trivial lower bound was known for MCSP against\n these models), and 3)\n $2^{\\Omega(N^{1/(d+1.01)})}$-size depth-$d$\n $\\mathrm{AC}^0$ circuits, improving the (implicit,\n in their work) exponential size lower bound by\n Allender et al. (SICOMP 2006). The $\\mathrm{AC}^0$\n lower bound stated above matches the best-known\n $\\mathrm{AC}^0$ lower bound (for {\\tt PARITY}) up to\n a small \\textit{additive} constant in the\n depth. Also, for the special case of depth-$2$\n circuits (i.e., CNFs or DNFs), we get an optimal\n lower bound of \\(2^{{\\Omega}(N)}\\) for MCSP. },\n keywords =\t {Minimum circuit size problem (MCSP), circuit lower\n bounds, pseudorandom generators (PRGs),\n constant-depth circuits, branching programs, local\n PRGs, de Morgan formulas}\n}\n\n","author_short":["Cheraghchi, M.","Kabanets, V.","Lu, Z.","Myrisiotis, D."],"key":"ref:CKLM20","id":"ref:CKLM20","bibbaseid":"cheraghchi-kabanets-lu-myrisiotis-circuitlowerboundsformcspfromlocalpseudorandomgenerators-2020","role":"author","urls":{" paper":"https://eccc.weizmann.ac.il/report/2019/022"," link":"https://dl.acm.org/doi/abs/10.1145/3404860"},"keyword":["Minimum circuit size problem (MCSP)","circuit lower bounds","pseudorandom generators (PRGs)","constant-depth circuits","branching programs","local PRGs","de Morgan formulas"],"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"article","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-29T18:47:45.884Z","downloads":8,"keywords":["minimum circuit size problem (mcsp)","circuit lower bounds","pseudorandom generators (prgs)","constant-depth circuits","branching programs","local prgs","de morgan formulas"],"search_terms":["circuit","lower","bounds","mcsp","local","pseudorandom","generators","cheraghchi","kabanets","lu","myrisiotis"],"title":"Circuit Lower Bounds for MCSP from Local Pseudorandom Generators","year":2020,"dataSources":["YZqdBBx6FeYmvQE6D"]}