[1]   Peyman Afshani: Improved pointer machine and I/O lower bounds for simplex range reporting and related problems. Int. J. Comput. Geometry Appl., 23(4-5):233–252, 2013. Preliminary version in SCG’12. [doi:10.1142/S0218195913600054]

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

[3]   Ziv Bar-Yossef, Thathachar S. Jayram, Ravi Kumar, and D. Sivakumar: An information statistics approach to data stream and communication complexity. J. Comput. System Sci., 68(4):702–732, 2004. Preliminary version in FOCS’02. [doi:10.1016/j.jcss.2003.11.006]

[4]   Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, and Bryan T. Wilkinson: Linear-space data structures for range mode query in arrays. Theory Comput. Syst., 55(4):719–741, 2014. Preliminary version in STACS’12. [doi:10.1007/s00224-013-9455-2]

[5]   Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, and Toniann Pitassi: A little advice can be very helpful. In Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’12), pp. 615–625. SIAM, 2012. ACM DL.

[6]   Bernard Chazelle: Lower bounds on the complexity of polytope range searching. J. Amer. Math. Soc., 2(4):637–666, 1989. Preliminary version in ICALP’03. [doi:10.1090/S0894-0347-1989-1001852-0]

[7]   Bernard Chazelle and Ding Liu: Lower bounds for intersection searching and fractional cascading in higher dimension. J. Comput. System Sci., 68(2):269–284, 2004. Preliminary version in STOC’01. [doi:10.1016/j.jcss.2003.07.003]

[8]   Bernard Chazelle and Burton Rosenberg: Simplex range reporting on a pointer machine. Comput. Geom., 5(5):237–247, 1996. [doi:10.1016/0925-7721(95)00002-X]

[9]   Dmitriy Yu. Cherukhin: The lower estimate of complexity in the class of schemes of depth 2 without restrictions on a basis. Vestnik Moscow University Series 1, Mathematika, 60(4):54–56, 2005.

[10]   Michael L. Fredman and Michael E. Saks: The cell probe complexity of dynamic data structures. In Proc. 21st STOC, pp. 345–354. ACM Press, 1989. [doi:10.1145/73007.73040]

[11]   Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, and Emanuele Viola: Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. IEEE Trans. Inform. Theory, 59(10):6611–6627, 2013. Preliminary version in STOC’12. [doi:10.1109/TIT.2013.2270275]

[12]   Anna Gál and Peter Bro Miltersen: The cell probe complexity of succinct data structures. Theoret. Comput. Sci., 379(3):405–417, 2007. Preliminary version in ICALP’03. [doi:10.1016/j.tcs.2007.02.047]

[13]   Stasys Jukna: Entropy of operators or why matrix multiplication is hard for depth-two circuits. Theory Comput. Syst., 46(2):301–310, 2010. [doi:10.1007/s00224-008-9133-y]

[14]   Bala Kalyanasundaram and Georg Schnitger: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math., 5(4):545–557, 1992. Preliminary version in SCTC’87. [doi:10.1137/0405044]

[15]   Kasper Green Larsen: The cell probe complexity of dynamic range counting. In Proc. 44th STOC, pp. 85–94. ACM Press, 2012. [doi:10.1145/2213977.2213987, arXiv:1105.5933]

[16]   Kasper Green Larsen: Higher cell probe lower bounds for evaluating polynomials. In Proc. 53rd FOCS, pp. 293–301. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.21]

[17]   Kasper Green Larsen: On range searching in the group model and combinatorial discrepancy. SIAM J. Comput., 43(2):673–686, 2014. Preliminary version in FOCS’11. [doi:10.1137/120865240]

[18]   Kasper Green Larsen and Huy Le Nguyen: Improved range searching lower bounds. In Proc. 28th Ann. Symp. on Computational Geometry (SCG’12), pp. 171–178. ACM Press, 2012. [doi:10.1145/2261250.2261275]

[19]   Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson: On data structures and asymmetric communication complexity. J. Comput. System Sci., 57(1):37–49, 1998. Preliminary version in STOC’95. [doi:10.1006/jcss.1998.1577]

[20]   Rina Panigrahy, Kunal Talwar, and Udi Wieder: Lower bounds on near neighbor search via metric expansion. In Proc. 51st FOCS, pp. 805–814. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.82]

[21]   Mihai Pǎtraşcu: Towards polynomial lower bounds for dynamic problems. In Proc. 42nd STOC, pp. 603–610. ACM Press, 2010. [doi:10.1145/1806689.1806772]

[22]   Mihai Pǎtraşcu and Erik D. Demaine: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput., 35(4):932–963, 2006. Preliminary versions in STOC’04 and SODA’04. [doi:10.1137/S0097539705447256]

[23]   Mihai Pǎtraşcu and Mikkel Thorup: Higher lower bounds for near-neighbor and further rich problems. SIAM J. Comput., 39(2):730–741, 2009. Preliminary version in FOCS’06. [doi:10.1137/070684859]

[24]   Alexander A. Razborov: On the distributional complexity of disjointness. Theoret. Comput. Sci., 106(2):385–390, 1992. Preliminary version in ICALP’90. [doi:10.1016/0304-3975(92)90260-M]

[25]   Claude Shannon: A mathematical theory of communication. Bell System Technical Journal, 27:379–423, 623–656, July, October 1948. Reprinted in Mobile Computing and Communications Review, 2001.

[26]   Leslie Valiant: Graph-theoretic methods in low-level complexity. In Proc. 6th Internat. Symp. on Mathemat. Found. of Comp. Sci. (MFCS’77), pp. 162–176, 1977. [doi:10.1007/3-540-08353-7_135]

[27]   Andrew Chi-Chih Yao: Some complexity questions related to distributive computing (preliminary report). In Proc. 11st STOC, pp. 209–213. ACM Press, 1979. [doi:10.1145/800135.804414]

[28]   Andrew Chi-Chih Yao: Should tables be sorted? J. ACM, 28(3):615–628, 1981. Preliminary version in FOCS’78. [doi:10.1145/322261.322274]