Imperial College London
Portrait Picture

Dr Mahdi Cheraghchi

Faculty of Engineering, Department of Computing

Honorary Senior Lecturer
 
 
 
//

Contact

 

m.cheraghchi Website CV

 
 
//

Location

 

353ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Cheraghchi:2018:10.1016/j.jcss.2018.04.006,
author = {Cheraghchi, M and Grigorescu, E and Juba, B and Wimmer, K and Xie, N},
doi = {10.1016/j.jcss.2018.04.006},
journal = {Journal of Computer and System Sciences},
pages = {45--59},
title = {AC(0) circle MOD(2 )lower bounds for the boolean inner product},
url = {http://dx.doi.org/10.1016/j.jcss.2018.04.006},
volume = {97},
year = {2018}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - AC0MOD2circuits are AC0circuits augmented with a layer of parity gates just above the input layer.  We  study  AC0 MOD2circuit  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  rst  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  rst  superlinear  lower  bound  for  the  Boolean  Inner  Product function against  AC0 MOD2of  depth four  or  greater.  Specically,  we  prove a  superlinear lower  bound  for  circuits  of  arbitrary  constant  depth,  and  an ˜(n2) lower  bound  for  the special case of depth-4 AC0MOD2.
AU  - Cheraghchi,M
AU  - Grigorescu,E
AU  - Juba,B
AU  - Wimmer,K
AU  - Xie,N
DO  - 10.1016/j.jcss.2018.04.006
EP  - 59
PY  - 2018///
SN  - 0022-0000
SP  - 45
TI  - AC(0) circle MOD(2 )lower bounds for the boolean inner product
T2  - Journal of Computer and System Sciences
UR  - http://dx.doi.org/10.1016/j.jcss.2018.04.006
UR  - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000441371400004&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR  - http://hdl.handle.net/10044/1/63225
VL  - 97
ER  -
Download