Aho, A., Ullman, J., and Yannakakis, M.. On notations of information transfer in VLSI circuits. In STOC, pages 133–139, 1983.Google Scholar

Ajtai, Miklós. A lower bound for finding predecessors in Yao’s call probe model. Combinatorica, 8(3):235–247, 1988.Google Scholar

Alon, Noga, Hoory, Shlomo, and Linial, Nathan. The Moore bound for irregular graphs. Graph Combinator, 18(1):53–57, 2002.CrossRefGoogle Scholar

Alon, Noga, Matias, Yossi, and Szegedy, Mario. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137–147, 1999.Google Scholar

Alon, Noga and Orlitsky, Alon. Repeated communication and Ramsey graphs. IEEE Trans. Inf. Theory, 41(5):1276–1289, 1995.CrossRefGoogle Scholar

Ambainis, Andris, Kokainis, Martins, and Kothari, Robin. Nearly optimal separations between communication (or query) complexity and partitions. In CCC, pages 1–14, 2016.Google Scholar

Andoni, Alexandr, Indyk, Piotr, and Patrascu, Mihai. On the optimality of the dimensionality reduction method. In FOCS, pages 449–458, 2006.CrossRefGoogle Scholar

Babai, László, Frankl, Peter, and Simon, Janos. Complexity classes in communication complexity theory (preliminary version). In FOCS, pages 337–347, 1986.CrossRefGoogle Scholar

Babai, László, Gál, Anna, Kimmel, Peter G., and Lokam, Satyanarayana V.. Communication complexity of simultaneous messages. SIAM J. Comput., 33(1):137–166, 2003.CrossRefGoogle Scholar

Babai, László, Nisan, Noam, and Szegedy, Mario. Multiparty protocols and logspace-hard pseudorandom sequences. In STOC, pages 1–11, 1989.CrossRefGoogle Scholar

Babu, Ajesh and Radhakrishnan, Jaikumar. An entropy based proof of the Moore bound for irregular graphs. arXiv:1011.1058, 2010.Google Scholar

Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and Sivakumar, D.. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702–732, 2004.Google Scholar

Barak, Boaz, Braverman, Mark, Chen, Xi, and Rao, Anup. How to compress interactive communication. In STOC, pages 67–76, 2010.Google Scholar

Barrington, David A.. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹.In STOC, pages 1–5, 1986.CrossRefGoogle Scholar

Bauer, Balthazar, Moran, Shay, and Yehudayoff, Amir. Internal compression of protocols to entropy. In LIPIcs-Leibniz International Proceedings in Informatics, volume 40. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.Google Scholar

Beame, Paul and Fich, Faith E.. Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci., 65(1):38–72, 2002.Google Scholar

Beame, Paul and Pitassi, Toniann. Simplified and improved resolution lower bounds. In FOCS, pages 274–282, 1996.Google Scholar

Behrend, Felix A.. On the sets of integers which contain no three in arithmetic progression. Proc. Nat. Acad. Sci., 28(12):561–563, 1946.Google Scholar

Braverman, Mark. Interactive information complexity. SIAM J. Comput., 44(6):1698–1739, 2015.CrossRefGoogle Scholar

Braverman, Mark and Garg, Ankit. Public vs private coin in bounded-round information. In ICALP, volume 8572, pages 502–513, 2014.Google Scholar

Braverman, Mark and Moitra, Ankur. An information complexity approach to extended formulations. In STOC, pages 161–170, 2013.CrossRefGoogle Scholar

Braverman, Mark, Rao, Anup, Weinstein, Omri, and Yehudayoff, Amir. Direct products in communication complexity. In FOCS, pages 746–755, 2013.CrossRefGoogle Scholar

Brodal, Gerth Stølting, Chaudhuri, Shiva, and Radhakrishnan, Jaikumar. The randomized complexity of maintaining the minimum. In SWAT, volume 1097, pages 4–15, 1996.Google Scholar

Brody, Joshua, Buhrman, Harry, Koucký, Michal, Loff, Bruno, Speelman, Florian, and Vereshchagin, Nikolay. Towards a reverse Newman’s theorem in interactive information complexity. Algorithmica, 76(3):749–781, 2016.Google Scholar

Chakrabarti, Amit and Regev, Oded. An optimal lower bound on the communication complexity of Gap-Hamming-distance. SIAM J. Comput., 41(5):1299–1317, 2012.Google Scholar

Chakrabarti, Amit, Shi, Yaoyun, Wirth, Anthony, and Yao, Andrew. Informational complexity and the direct sum problem for simultaneous message complexity. In FOCS, pages 270–278, 2001.Google Scholar

Chandra, Ashok K., Furst, Merrick L., and Lipton, Richard J.. Multi-party protocols. In STOC, pages 94–99, 1983.CrossRefGoogle Scholar

Chattopadhyay, Arkadev, Koucký, Michal, Loff, Bruno, and Mukhopadhyay, Sagnik. Simulation theorems via pseudorandom properties. arXiv:1704.06807, 2017.Google Scholar

Chung, Fan R. K., Graham, Ronald L., Frankl, Peter, and Shearer, James B.. Some intersection theorems for ordered sets and graphs. J. Comb. Theory Ser. A, 43(1):23–37, 1986.Google Scholar

Cole, Richard and Vishkin, Uzi. Deterministic coin tossing and accelerating cascades: Micro and macro techniques for designing parallel algorithms. In STOC, pages 206–219, 1986.Google Scholar

Cook, William, Coullard, Collette R., and Turán, Gy. On the complexity of cutting-plane proofs. Discrete Appl. Math., 18(1):25–38, 1987.CrossRefGoogle Scholar

Dietzfelbinger, Martin and Wunderlich, Henning. A characterization of average case communication complexity. Inf. Process. Lett., 101(6):245–249, 2007.CrossRefGoogle Scholar

Dinur, Irit and Meir, Or. Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity. In LIPIcs-Leibniz International Proceedings in Informatics, volume 50. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.Google Scholar

Drucker, Andrew, Kuhn, Fabian, and Oshman, Rotem. On the power of the congested clique model. In PODC, pages 367–376, 2014.CrossRefGoogle Scholar

Duris, Pavol, Galil, Zvi, and Schnitger, Georg. Lower bounds on communication complexity. Inform. Comput., 73(1):1–22, 1987.Google Scholar

Edmonds, Jack. Paths, trees, and flowers. Can. J. Math., 17:449–467, 1965.CrossRefGoogle Scholar

Edmonds, Jack. Matroids and the greedy algorithm. Math. Program, 1(1):127–136, 1971.Google Scholar

Edmonds, Jeff, Impagliazzo, Russell, Rudich, Steven, and Sgall, Jiri. Communication complexity towards lower bounds on circuit depth. Comput. Complex., 10(3):210–246, 2001.Google Scholar

Ellis, David, Filmus, Yuval, and Friedgut, Ehud. Triangle-intersecting families of graphs. J. Eur. Math. Soc., 14(3):841–885, 2012.Google Scholar

Feder, Tomàs, Kushilevitz, Eyal, Naor, Moni, and Nisan, Noam. Amortized communication complexity. SIAM J. Comput., 24(4):736–750, 1995.Google Scholar

Feige, Uriel, Peleg, David, Prabhakar Raghavan, and Eli Upfal. Computing with noisy information. SIAM J. Comput., 23(5):1001–1018, 1994.Google Scholar

Fiorini, Samuel, Rothvoß, Thomas, and Tiwary, Hans Raj. Extended formulations for polygons. Discrete Comput. Geom., 48(3):658–668, 2012.Google Scholar

Fredman, Michael L. and Saks, Michael E.. The cell probe complexity of dynamic data structures. In STOC, pages 345–354, 1989.Google Scholar

Frischknecht, Silvio, Holzer, Stephan, and Wattenhofer, Roger. Networks cannot compute their diameter in sublinear time. In SODA, pages 1150–1162, 2012.Google Scholar

Galler, Bernard A. and Fisher, Michael J.. An improved equivalence algorithm. Commun. ACM, 7(5):301–303, 1964.Google Scholar

Ganor, Anat, Kol, Gillat, and Raz, Ran. Exponential separation of information and communication for Boolean functions. JACM, 63(5):46, 2016.Google Scholar

Gavinsky, Dmitry and Lovett, Shachar. En route to the log-rank conjecture: New reductions and equivalent formulations. In ICALP, pages 514–524, 2014.Google Scholar

Gavinsky, Dmitry, Meir, Or, Weinstein, Omri, and Wigderson, Avi. Toward better formula lower bounds: An information complexity approach to the KRW composition conjecture. In STOC, pages 213–222, 2014.Google Scholar

Gödel, Kurt. Über formal unentscheidbare sätze der principia mathematica und verwandter systeme I. Monatshefte für mathematik und physik, 38(1):173–198, 1931.Google Scholar

Goel, Ashish, Kapralov, Michael, and Khanna, Sanjeev. On the communication and streaming complexity of maximum bipartite matching. In SODA, pages 468–485, 2012.Google Scholar

Goemans, Michel X.. Smallest compact formulation for the permutahedron. Math. Program, 153(1):5–11, 2015.Google Scholar

Göös, Mika, Pitassi, Toniann, and Watson, Thomas. Deterministic communication vs. partition number. In FOCS, pages 1077–1088, 2015.Google Scholar

Göös, Mika and Watson, Thomas. Communication complexity of set-disjointness for all probabilities. In LIPIcs-Leibniz International Proceedings in Informatics, volume 28. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014.Google Scholar

Graham, Ronald L.. Rudiments of Ramsey Theory. Number 45 in Regional Conference series in mathematics. American Mathematical Society, 1980.Google Scholar

Graham, Ronald L., Rothschild, Bruce L., and Spencer, Joel H.. Ramsey theory. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, New York, 1980.Google Scholar

Gregoryev, D.. Lower bounds in algebraic computational complexity. Theorems in Comput. Complex. 1, (118):25–82, 1982.Google Scholar

Grolmusz, Vince. Circuits and multi-party protocols. Comput. Complex., 7(1):1–18, 1998.CrossRefGoogle Scholar

Gromov, Misha. In a search for a structure, part 1: On entropy. 2012.Google Scholar

Haken, Armin. The intractability of resolution. Theor. Comput. Sci., 39(2–3): 297–308, August 1985.Google Scholar

Hales, Alfred W. and Jewett, Robert I.. On regularity and positional games. Tr. Amer. Math. Soc., 106:222–229, 1963.Google Scholar

Halstenberg, Bernd and Reischuk, Rüdiger. Different modes of communication. SIAM J. Comput., 22(5):913–934, 1993.Google Scholar

Harper, Lawrence H.. Optimal numberings and isoperimetric problems on graphs. J. Comb. Theory, 1(3):385–393, 1966.Google Scholar

Harsha, Prahladh, Jain, Rahul, McAllester, David A., and Radhakrishnan, Jaikumar. The communication complexity of correlation. In CCC, pages 10–23, 2007.Google Scholar

Hartmanis, Juris and Stearns, Richard E.. On the computational complexity of algorithms. T. Amn. Math. Soc., 117:285–306, 1965.Google Scholar

Håstad, Johan and Wigderson, Avi. Composition of the universal relation. In Advances in Comput. Complex. Theory, American Mathematical Society, pages 119–134, 1990.Google Scholar

Håstad, Johan and Wigderson, Avi. The randomized communication complexity of set disjointness. Theory of Computing, 3(1):211–219, 2007.Google Scholar

Hennie, Fred C.. One-tape, off-line Turing machine computations. Inform. Control, 8(6):553–578, 1965.Google Scholar

Holenstein, Thomas. Parallel repetition: Simplification and the no-signaling case. Theory of Computing, 5(1):141–172, 2009.Google Scholar

Holzer, Stephan and Wattenhofer, Roger. Optimal distributed all pairs shortest paths and applications. In PODC, pages 355–364, 2012.Google Scholar

Hrubeš, Pavel. A note on semantic cutting planes. In ECCC, 20:128, 2013.Google Scholar

Hrubeš, Pavel and Rao, Anup. Circuits with medium fan-in. In CCC, volume 33, pages 381–391, 2015.Google Scholar

Hrubeš, Pavel. Personal communication, 2016.Google Scholar

Impagliazzo, Russell, Pitassi, Toniann, and Urquhart, Alasdair. Upper and lower bounds for tree-like cutting planes proofs. In LICS, pages 220–228, 1994.Google Scholar

Indyk, Piotr and Woodruff, David P.. Tight lower bounds for the distinct elements problem. In FOCS, pages 283–288, 2003.Google Scholar

John, Fritz. Extremum problems with inequalities as subsidiary conditions. In Traces and Emergence of Nonlinear Programming, Springer, pages 187–204, 1948.Google Scholar

Jukna, Stasys. Boolean Function Complexity: Advances and Frontiers, volume 27. Springer Science and Business Media, 2012.Google Scholar

Kaibel, Volker and Pashkovich, Kanstantsin. Constructing extended formulations from reflection relations. In Facets of Combinatorial Optimization, Springer Science and Business Media, pages 77–100, 2013.Google Scholar

Kalyanasundaram, Bala and Schnitger, Georg. The probabilistic communication complexity of set intersection. SIAM J. Discrete Math., 5(4):545–557, 1992.Google Scholar

Kapralov, Michael. Better bounds for matchings in the streaming model. In SODA, pages 1679–1697, 2013.Google Scholar

Karchmer, Mauricio, Raz, Ran, and Wigderson, Avi. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Comput. Complex., 5(3/4):191–204, 1995. DOI : 10.1007/BF01206317.Google Scholar

Karchmer, Mauricio and Wigderson, Avi. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math., 3(2):255–265, 1990.Google Scholar

Klauck, Hartmut. One-way communication complexity and the Nečiporuk lower bound on formula size. SIAM J. Comput., 37(2):552–583, 2007.Google Scholar

Kleinberg, Jon M. and Tardos, Éva. Algorithm Design. Addison-Wesley, 2006.Google Scholar

Kol, Gillat. Interactive compression for product distributions. In STOC, pages 987–998, 2016.Google Scholar

Krajíček, Jan. Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. J. Symbolic Logic, 62(02):457–486, 1997.Google Scholar

Krapchenko, V.. A method of determining lower bounds for the complexity of π schemes. Math. Notes Acad. Sci. USSR, 11:474–479, 1971.Google Scholar

Kushilevitz, Eyal, Ostrovsky, Rafail, and Rabani, Yuval. Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM J. Comput., 30(2): 457–474, 2000.Google Scholar

Linial, Nathan. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193–201, 1992.Google Scholar

Lovász, László. Communication complexity: A survey. Technical report, 1990.Google Scholar

Lovász, László and Saks, Michael E.. Lattices, Möbius functions and communication complexity. In FOCS, pages 81–90, 1988.Google Scholar

Lovett, Shachar. Communication is bounded by root of rank. In STOC, pages 842–846, 2014.Google Scholar

Lupanov, Oleg. A method for synthesizing circuits. Izv. vysshykh uchebnykh zavedenii, Radiofizika, 1:120–140, 1958.Google Scholar

Miltersen, Peter, Nisan, Noam, Safra, Shmuel, and Wigderson, Avi. On data structures and asymmetric communication complexity. J. Comput. Sys. Sci., 57:37–49, 1 1998.Google Scholar

Neciporuk, E. I.. On a Boolean function. Dokl. Akad. Nauk SSSR, 7:765–766, 1966.Google Scholar

Newman, Ilan. Private vs. common random bits in communication complexity. Inform. Process. Lett., 39(2):67–71, 31 July 1991.Google Scholar

Nisan, Noam and Wigderson, Avi. Rounds in communication complexity revisited. SIAM J. Comput., 22(1):211–219, 1993.CrossRefGoogle Scholar

Nisan, Noam and Wigderson, Avi. On rank vs. communication complexity. Combinatorica, 15(4):557–565, 1995.CrossRefGoogle Scholar

Pankratov, Denis. Direct sum questions in classical communication complexity. Master’s thesis, University of Chicago, 2012.Google Scholar

Pătras̡cu, Mihai. Unifying the landscape of cell-probe lower bounds. SIAM J. Comput., 40(3):827–847, 2011.Google Scholar

Pǎtras̡cu, Mihai and Thorup, Mikkel. Time-space trade-offs for predecessor search. In STOC, pages 232–240, 2006.Google Scholar

Pǎtras̡cu, Mihai and Thorup, Mikkel. Dynamic integer sets with optimal rank, select, and predecessor search. In FOCS, pages 166–175, 2014.Google Scholar

Pudlák, Pavel. Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symbolic Logic, 62(03):981–998, 1997.Google Scholar

Rado, Richard. An inequality. London Journal of Mathematics Society, 27:1–6, 1952.Google Scholar

Ramamoorthy, Sivaramakrishnan Natarajan and Rao, Anup. Non-adaptive data structure lower bounds for median and predecessor search from sunflowers. In ECCC, 24:40, 2017.Google Scholar

Rao, Anup and Sinha, Makrand. Simplified separation of information and communication. In ECCC, 22:57, 2015.Google Scholar

Rao, Anup and Yehudayoff, Amir. Simplified lower bounds on the multiparty communication complexity of disjointness. In CCC, volume 33, pages 88–101, 2015.Google Scholar

Rao, Anup and Yehudayoff, Amir. Anti-concentration in most directions. CoRR, 2019. URL https://arxiv.org/abs/1811.06510.Google Scholar

Raz, Ran and McKenzie, Pierre. Separation of the monotone NC hierarchy. In STOC, pages 234–243. IEEE, 1997.Google Scholar

Raz, Ran and Wigderson, Avi. Monotone circuits for matching require linear depth. JACM, 39(3):736–744, 1992.Google Scholar

Razborov, Alexander. On the distributed complexity of disjointness. Theoret. Comput. Sci., 106:385–390, 1992.Google Scholar

Robinson, John Alan. A machine-oriented logic based on the resolution principle. JACM, 12(1):23–41, 1965.Google Scholar

Rothvoß, Thomas. The matching polytope has exponential extension complexity. In STOC, pages 263–272, 2014.Google Scholar

Ruzsa, Imre Z. and Szemerédi, Endre. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18: 939–945, 1978.Google Scholar

Samorodnitsky, Alex. An inequality for functions on the Hamming cube. Comb., Probab. Comput., 26(3):468–480, 2017.Google Scholar

Sen, Pranab and Venkatesh, Srinivasan. Lower bounds for predecessor searching in the cell probe model. J. Comput. Syst. Sci., 74(3):364–385, 2008.Google Scholar

Shannon, Claude E.. A mathematical theory of communication. AT&T Tech. J., 27, 1948. Monograph B-1598.Google Scholar

Shannon, Claude E.. The synthesis of two-terminal switching circuits. Bell Labs Tech. Jour., 28(1):59–98, 1949.Google Scholar

Sherstov, Alexander A.. The communication complexity of Gap-Hamming distance. Theory of Computing, 8(1):197–208, 2012.Google Scholar

Sherstov, Alexander A.. Communication lower bounds using directional derivatives. J. ACM, 61(6):34:1–34:71, 2014.Google Scholar

Sherstov, Alexander A.. Compressing interactive communication under product distributions. In FOCS, pages 535–544, 2016.Google Scholar

Szegedy, Balazs. An information theoretic approach to Sidorenko’s conjecture. arXiv:1406.6738, 2014.Google Scholar

Thompson, Clark D.. Area-time complexity for VLSI. In STOC, pages 81–88, 1979.Google Scholar

Boas, P. van Emde. Preserving order in a forest in less than logarithmic time. In FOCS, pages 75–84, 1975.Google Scholar

Vidick, Thomas. A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the Gap-Hamming-distance problem. Chicago J. Theor. Comput. Sci, 2012, 2012.Google Scholar

Viola, Emanuele. The communication complexity of addition. Combinatorica, 35(6):703–747, 2015. DOI : 10.1007/s00493–014-3078-3.Google Scholar

Neumann, John von. Zur Theorie der Gesellschaftsspiele. Math. Ann., 100:295–320, 1928.Google Scholar

Wikipedia. Linear programming – Wikipedia, the free encyclopedia, 2016a. URL https://en.wikipedia.org/wiki/Linear_programming. [Online; accessed August 30, 2016].Google Scholar

Wikipedia. Boolean satisfiability problem – Wikipedia, the free encyclopedia, 2016b. URL https://en.wikipedia.org/wiki/Boolean_ satisfiability_problem. [Online; accessed August 30, 2016].Google Scholar

Yannakakis, Mihalis. Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci., 43(3):441–466, 1991.Google Scholar

Yao, Andrew Chi-Chih. Some complexity questions related to distributive computing. In STOC, pages 209–213, 1979.Google Scholar

Yao, Andrew Chi-Chih. Lower bounds by probabilistic arguments. In FOCS, pages 420–428, 1983.Google Scholar

Yehudayoff, Amir. Pointer chasing via triangular discrimination. In ECCC, 23, 2016.Google Scholar