Sign-Rank vs. Discrepancy

by Kaave Hosseini, Hamed Hatami, and Shachar Lovett

Theory of Computing, Volume 18(19), pp. 1-22, 2022

Bibliography with links to cited articles

[1]   Noga Alon, Shay Moran, and Amir Yehudayoff: Sign rank versus Vapnik–Chervonenkis dimension. Sbornik Math., 208(12):1724–1757, 2017. Preliminary version in COLT’16:PMLR. [doi:10.1070/SM8780]

[2]   László Babai, Peter Frankl, and Janos Simon: Complexity classes in communication complexity theory. In Proc. 27th FOCS, pp. 337–347. IEEE Comp. Soc., 1986. [doi:10.1109/SFCS.1986.15]

[3]   László Babai, Noam Nisan, and Márió Szegedy: Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. System Sci., 45(2):204–232, 1992. Preliminary version in STOC’89.

[4]   Ronen Basri, Pedro F. Felzenszwalb, Ross B. Girshick, David W. Jacobs, and Caroline J. Klivans: Visibility constraints on features of 3D objects. In Proc. Conf. Comp. Vision and Pattern Recog. (CVPR’09), pp. 1231–1238. IEEE Comp. Soc., 2009. [doi:10.1109/CVPR.2009.5206726]

[5]   Amey Bhangale and Swastik Kopparty: The complexity of computing the minimum rank of a sign pattern matrix, 2015. [arXiv:1503.04486]

[6]   Thomas A. Brown and Joel H. Spencer: Minimization of ±1 matrices under line shifts. Colloquium Mathematicum, 23:165–171, 1971. [doi:10.4064/cm-23-1-165-171]

[7]   Harry Buhrman, Nikolay Vereshchagin, and Ronald de Wolf: On computation and communication with small bias. In Proc. 22nd IEEE Conf. on Comput. Complexity (CCC’07), pp. 24–32. IEEE Comp. Soc., 2007. [doi:10.1109/CCC.2007.18]

[8]   Mark Bun and Justin Thaler: Improved bounds on the sign-rank of AC0. In Proc. 43rd Internat. Colloq. on Automata, Languages, and Programming (ICALP’16), pp. 37:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.ICALP.2016.37, ECCC:TR16-075]

[9]   Arkadev Chattopadhyay and Toniann Pitassi: The story of set disjointness. SIGACT News, 41(3):59–85, 2010. [doi:10.1145/1855118.1855133]

[10]   Bernard Chazelle: The Discrepancy Method: Randomness and Complexity. Cambridge Univ. Press, 2000.

[11]   Benny Chor and Oded Goldreich: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230–261, 1988. Preliminary version in FOCS’85. [doi:10.1137/0217015]

[12]   Johannes G. van der Corput: Verteilungsfunktionen I (Distribution functions, German). Proc. Akad. Wetenschappen Amsterdam, 38:813–821, 1935.

[13]   Paul Erdős and Joel H. Spencer: Probabilistic Methods in Combinatorics. Akadémiai Kiadó, Budapest, and Academic Press, 1971.

[14]    Jürgen Forster: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. System Sci., 65(4):612–625, 2002. Preliminary version in CCC’01. [doi:10.1016/S0022-0000(02)00019-3]

[15]   Anna Gál and Ridwan Syed: Upper bounds on communication in terms of approximate rank. In Proc. Comp. Sci. Symp. in Russia (CSR’21), pp. 116–130. Springer, 2021. [doi:10.1007/978-3-030-79416-3_7, ECCC:TR19-006]

[16]   Hamed Hatami, Kaave Hosseini, and Shachar Lovett: Sign rank vs discrepancy. In Proc. 35th Comput. Complexity Conf. (CCC’20), pp. 18:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.18, ECCC:TR19-067]

[17]   Hartmut Klauck: Lower bounds for quantum communication complexity. SIAM J. Comput., 37(1):20–46, 2007. Preliminary version in FOCS’01. [doi:10.1137/S0097539702405620]

[18]   Adam R. Klivans and Rocco A. Servedio: Learning DNF in time 2Õ(n13) . J. Comput. System Sci., 68(2):303–318, 2004. Preliminary version in STOC’01. [doi:10.1016/j.jcss.2003.07.007]

[19]   Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman: Complexity measures of sign matrices. Combinatorica, 27(4):439–463, 2007. [doi:10.1007/s00493-007-2160-5]

[20]   Nati Linial and Adi Shraibman: Learning complexity vs. communication complexity. Combin. Probab. Comput., 18(1–2):227–245, 2009. Preliminary version in CCC’08. [doi:10.1017/S0963548308009656]

[21]   Noam Nisan: The communication complexity of threshold gates. In D. Miklós, T. Szőnyi, and V. T. Sós, editors, Combinatorics, Paul Erdős is Eighty, volume 1, pp. 301–315. Bolyai Society, Budapest and North-Holland, 1993. Author’s website.

[22]   Ramamohan Paturi and Janos Simon: Probabilistic communication complexity. J. Comput. System Sci., 33(1):106–123, 1986. Preliminary version in FOCS’84. [doi:10.1016/0022-0000(86)90046-2]

[23]   Alexander A. Razborov and Alexander A. Sherstov: The sign-rank of AC0. SIAM J. Comput., 39(5):1833–1855, 2010. Preliminary version in FOCS’08. [doi:10.1137/080744037, ECCC:TR08-016]

[24]   Alexander A. Sherstov: Halfspace matrices. Comput. Complexity, 17(2):149–178, 2008. Preliminary version in CCC’07. [doi:10.1007/s00037-008-0242-4]

[25]   Alexander A. Sherstov: The pattern matrix method. SIAM J. Comput., 40(6):1969–2000, 2011. [doi:10.1137/080733644, arXiv:0906.4291]

[26]   Alexander A. Sherstov: Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Combinatorica, 33(1):73–96, 2013. Preliminary version in STOC’10. [doi:10.1007/s00493-013-2759-7, arXiv:0910.4224, ECCC:TR10-025]

[27]   Alexander A. Sherstov: The hardest halfspace. Comput. Complexity, 30(2):11, 2021. [doi:10.1007/s00037-021-00211-4, arXiv:1902.01765, ECCC:TR19-016]

[28]   Justin Thaler: Lower bounds for the approximate degree of block-composed functions. In Proc. 43rd Internat. Colloq. on Automata, Languages, and Programming (ICALP’16), pp. 17:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.ICALP.2016.17, ECCC:TR14-150]

[29]   Hugh E. Warren: Lower bounds for approximation by nonlinear manifolds. Trans. AMS, 133(1):167–178, 1968. [doi:10.1090/S0002-9947-1968-0226281-1]