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Õ(n1∕3) . 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]