AC0-MOD2 lower bounds for the Boolean Inner Product. Cheraghchi, M., Grigorescu, E., Juba, B., Wimmer, K., & Xie, N. Journal of Computer and System Sciences, 97:45–59, 2018. Preliminary version in Proceedings of ICALP 2016.Link Paper doi abstract bibtex 7 downloads AC0-MOD2 circuits are AC0 circuits augmented with a layer of parity gates just above the input layer. We study AC0-MOD2 circuit lower bounds for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have highlighted this problem as a frontier problem in circuit complexity that arose both as a first step towards solving natural special cases of the matrix rigidity problem and as a candidate for constructing pseudorandom generators of minimal complexity. We give the first superlinear lower bound for the Boolean Inner Product function against AC0-MOD2 of depth four or greater. Specifically, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an $Ω̃(n^2)}$ lower bound for the special case of depth-4 AC0-MOD2.
@ARTICLE{ref:CGJWX18,
author = {Mahdi Cheraghchi and Elena Grigorescu and Brendan
Juba and Karl Wimmer and Ning Xie},
title = {{AC0-MOD2} lower bounds for the {Boolean} Inner
Product},
journal = {Journal of Computer and System Sciences},
volume = 97,
pages = "45--59",
year = 2018,
doi = "10.1016/j.jcss.2018.04.006",
url_Link =
"http://www.sciencedirect.com/science/article/pii/S002200001830518X",
keywords = "Boolean analysis, Circuit complexity, Lower bounds",
abstract = "AC0-MOD2 circuits are AC0 circuits augmented with a
layer of parity gates just above the input layer. We
study AC0-MOD2 circuit lower bounds for computing
the Boolean Inner Product functions. Recent works by
Servedio and Viola (ECCC TR12-144) and Akavia et
al. (ITCS 2014) have highlighted this problem as a
frontier problem in circuit complexity that arose
both as a first step towards solving natural special
cases of the matrix rigidity problem and as a
candidate for constructing pseudorandom generators
of minimal complexity. We give the first superlinear
lower bound for the Boolean Inner Product function
against AC0-MOD2 of depth four or
greater. Specifically, we prove a superlinear lower
bound for circuits of arbitrary constant depth, and
an $\tilde{\Omega(n^2)}$ lower bound for the special
case of depth-4 AC0-MOD2.",
note = {Preliminary version in Proceedings of {ICALP 2016.}},
url_Paper = {https://eccc.weizmann.ac.il//report/2015/030/}
}
Downloads: 7
{"_id":"9D7ehaSBwHSexweGD","bibbaseid":"cheraghchi-grigorescu-juba-wimmer-xie-ac0mod2lowerboundsforthebooleaninnerproduct-2018","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","H4D7r27RcPALT5DCs","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.","Grigorescu, E.","Juba, B.","Wimmer, K.","Xie, N."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["Elena"],"propositions":[],"lastnames":["Grigorescu"],"suffixes":[]},{"firstnames":["Brendan"],"propositions":[],"lastnames":["Juba"],"suffixes":[]},{"firstnames":["Karl"],"propositions":[],"lastnames":["Wimmer"],"suffixes":[]},{"firstnames":["Ning"],"propositions":[],"lastnames":["Xie"],"suffixes":[]}],"title":"AC0-MOD2 lower bounds for the Boolean Inner Product","journal":"Journal of Computer and System Sciences","volume":"97","pages":"45–59","year":"2018","doi":"10.1016/j.jcss.2018.04.006","url_link":"http://www.sciencedirect.com/science/article/pii/S002200001830518X","keywords":"Boolean analysis, Circuit complexity, Lower bounds","abstract":"AC0-MOD2 circuits are AC0 circuits augmented with a layer of parity gates just above the input layer. We study AC0-MOD2 circuit lower bounds for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have highlighted this problem as a frontier problem in circuit complexity that arose both as a first step towards solving natural special cases of the matrix rigidity problem and as a candidate for constructing pseudorandom generators of minimal complexity. We give the first superlinear lower bound for the Boolean Inner Product function against AC0-MOD2 of depth four or greater. Specifically, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an $Ω̃(n^2)}$ lower bound for the special case of depth-4 AC0-MOD2.","note":"Preliminary version in Proceedings of ICALP 2016.","url_paper":"https://eccc.weizmann.ac.il//report/2015/030/","bibtex":"@ARTICLE{ref:CGJWX18,\n author =\t {Mahdi Cheraghchi and Elena Grigorescu and Brendan\n Juba and Karl Wimmer and Ning Xie},\n title =\t {{AC0-MOD2} lower bounds for the {Boolean} Inner\n Product},\n journal =\t {Journal of Computer and System Sciences},\n volume =\t 97,\n pages =\t \"45--59\",\n year =\t 2018,\n doi =\t\t \"10.1016/j.jcss.2018.04.006\",\n url_Link =\n \"http://www.sciencedirect.com/science/article/pii/S002200001830518X\",\n keywords =\t \"Boolean analysis, Circuit complexity, Lower bounds\",\n abstract =\t \"AC0-MOD2 circuits are AC0 circuits augmented with a\n layer of parity gates just above the input layer. We\n study AC0-MOD2 circuit lower bounds for computing\n the Boolean Inner Product functions. Recent works by\n Servedio and Viola (ECCC TR12-144) and Akavia et\n al. (ITCS 2014) have highlighted this problem as a\n frontier problem in circuit complexity that arose\n both as a first step towards solving natural special\n cases of the matrix rigidity problem and as a\n candidate for constructing pseudorandom generators\n of minimal complexity. We give the first superlinear\n lower bound for the Boolean Inner Product function\n against AC0-MOD2 of depth four or\n greater. Specifically, we prove a superlinear lower\n bound for circuits of arbitrary constant depth, and\n an $\\tilde{\\Omega(n^2)}$ lower bound for the special\n case of depth-4 AC0-MOD2.\",\n note =\t {Preliminary version in Proceedings of {ICALP 2016.}},\n url_Paper =\t {https://eccc.weizmann.ac.il//report/2015/030/}\n}\n\n","author_short":["Cheraghchi, M.","Grigorescu, E.","Juba, B.","Wimmer, K.","Xie, N."],"key":"ref:CGJWX18","id":"ref:CGJWX18","bibbaseid":"cheraghchi-grigorescu-juba-wimmer-xie-ac0mod2lowerboundsforthebooleaninnerproduct-2018","role":"author","urls":{" link":"http://www.sciencedirect.com/science/article/pii/S002200001830518X"," paper":"https://eccc.weizmann.ac.il//report/2015/030/"},"keyword":["Boolean analysis","Circuit complexity","Lower bounds"],"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/writings/"}},"downloads":7,"html":""},"bibtype":"article","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-28T22:30:02.277Z","downloads":7,"keywords":["boolean analysis","circuit complexity","lower bounds"],"search_terms":["ac0","mod2","lower","bounds","boolean","inner","product","cheraghchi","grigorescu","juba","wimmer","xie"],"title":"AC0-MOD2 lower bounds for the Boolean Inner Product","year":2018,"dataSources":["YZqdBBx6FeYmvQE6D"]}