AC0-MOD2 lower bounds for the Boolean Inner Product. Cheraghchi, M., Grigorescu, E., Juba, B., Wimmer, K., & Xie, N. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55, of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:14, 2016. Extended version in Journal of Computer and System SciencesLink Paper doi abstract bibtex 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.
@INPROCEEDINGS{ref:conf:CGJWX16,
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},
booktitle = {Proceedings of the 43rd {International Colloquium on
Automata, Languages, and Programming (ICALP 2016)}},
pages = {35:1--35:14},
series = {Leibniz International Proceedings in Informatics
(LIPIcs)},
year = 2016,
volume = 55,
url_Link = {http://drops.dagstuhl.de/opus/volltexte/2016/6315},
doi = {10.4230/LIPIcs.ICALP.2016.35},
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 = {Extended version in {Journal of Computer and System
Sciences}},
url_Paper = {https://eccc.weizmann.ac.il//report/2015/030/}
}
Downloads: 0
{"_id":"R8PQdbvdAGvyN3rR3","bibbaseid":"cheraghchi-grigorescu-juba-wimmer-xie-ac0mod2lowerboundsforthebooleaninnerproduct-2016","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":"inproceedings","type":"inproceedings","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","booktitle":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)","pages":"35:1–35:14","series":"Leibniz International Proceedings in Informatics (LIPIcs)","year":"2016","volume":"55","url_link":"http://drops.dagstuhl.de/opus/volltexte/2016/6315","doi":"10.4230/LIPIcs.ICALP.2016.35","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":"Extended version in Journal of Computer and System Sciences","url_paper":"https://eccc.weizmann.ac.il//report/2015/030/","bibtex":"@INPROCEEDINGS{ref:conf:CGJWX16,\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 booktitle =\t {Proceedings of the 43rd {International Colloquium on\n Automata, Languages, and Programming (ICALP 2016)}},\n pages =\t {35:1--35:14},\n series =\t {Leibniz International Proceedings in Informatics\n (LIPIcs)},\n year =\t 2016,\n volume =\t 55,\n url_Link =\t {http://drops.dagstuhl.de/opus/volltexte/2016/6315},\n doi =\t\t {10.4230/LIPIcs.ICALP.2016.35},\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 {Extended version in {Journal of Computer and System\n Sciences}},\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:conf:CGJWX16","id":"ref:conf:CGJWX16","bibbaseid":"cheraghchi-grigorescu-juba-wimmer-xie-ac0mod2lowerboundsforthebooleaninnerproduct-2016","role":"author","urls":{" link":"http://drops.dagstuhl.de/opus/volltexte/2016/6315"," paper":"https://eccc.weizmann.ac.il//report/2015/030/"},"keyword":["Boolean analysis","circuit complexity","lower bounds"],"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-28T22:30:02.278Z","downloads":1,"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":2016,"dataSources":["YZqdBBx6FeYmvQE6D"]}