Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds

by Emanuele Viola

Theory of Computing, Volume 15(18), pp. 1-9, 2019

Bibliography with links to cited articles

[1]   Miklós Ajtai: A non-linear time lower bound for Boolean branching programs. Theory of Computing, 1(8):149–176, 2005. Preliminary version in FOCS’99. [doi:10.4086/toc.2005.v001a008]

[2]   Noga Alon, Oded Goldreich, Johan Hĺstad, and René Peralta: Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992. Preliminary version in FOCS’90. [doi:10.1002/rsa.3240030308]

[3]   Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee: Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM, 50(2):154–195, 2003. Preliminary version in FOCS’00. [doi:10.1145/636865.636867]

[4]   Jon Louis Bentley: Decomposable searching problems. Inf. Process. Lett., 8(5):244–251, 1979. [doi:10.1016/0020-0190(79)90117-0]

[5]   Joshua Brody and Kasper Green Larsen: Adapt or die: Polynomial lower bounds for non-adaptive dynamic data structures. Theory of Computing, 11(19):471–489, 2015. [doi:10.4086/toc.2015.v011a019, arXiv:1208.2846]

[6]   Chris Calabro: A lower bound on the size of series-parallel graphs dense in long paths. ECCC, TR08-110, 2008.

[7]   Dmitriy Yu. Cherukhin: Lower bounds for Boolean circuits with finite depth and arbitrary gates. ECCC, TR08-032, 2008.

[8]   Dmitriy Yu. Cherukhin: Lower bounds for depth-2 and depth-3 Boolean circuits with arbitrary gates. In Proc. 3nd Internat. Comp. Sci. Symp. in Russia (CSR’08), pp. 122–133. Springer, 2008. [doi:10.1007/978-3-540-79709-8_15]

[9]   Henry Corrigan-Gibbs and Dmitry Kogan: The function-inversion problem: Barriers and opportunities. ECCC, TR18-182, 2019.

[10]   Zeev Dvir, Alexander Golovnev, and Omri Weinstein: Static data structure lower bounds imply rigidity, 2019. Preliminary version ECCC, TR18-188. [doi:10.1145/3313276.3316348, arXiv:1811.02725]

[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’13. [doi:10.1016/j.tcs.2007.02.047]

[13]   Oded Goldreich: Three XOR-lemmas - An exposition. In Studies in Complexity and Cryptography, pp. 248–272. Springer, 2011. [doi:10.1007/978-3-642-22670-0_22]

[14]   Stasys Jukna: Boolean Function Complexity: Advances and Frontiers. Springer, 2012. [doi:10.1007/978-3-642-24508-4]

[15]   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]

[16]   Kasper Green Larsen, Omri Weinstein, and Huacheng Yu: Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. In Proc. 50th STOC, pp. 978–989. ACM Press, 2018. [doi:10.1145/3188745.3188790, arXiv:1703.03575]

[17]   Peter Bro Miltersen: The bit probe complexity measure revisited. In Proc. 10th Symp. Theoretical Aspects of Comp. Sci. (STACS’93), pp. 662–671. Springer, 1993. [doi:10.1007/3-540-56503-5_65]

[18]   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]

[19]   Joseph Naor and Moni Naor: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. Preliminary version in STOC’90. [doi:10.1137/0222053]

[20]   Mark H. Overmars: The Design of Dynamic Data Structures. Springer, 1983. [doi:10.1007/BFb0014927]

[21]   Mihai Pătraşcu: Unifying the landscape of cell-probe lower bounds. SIAM J. Comput., 40(3):827–847, 2011. Preliminary version in FOCS’08. [doi:10.1137/09075336X, arXiv:1010.3783]

[22]   Pavel Pudlák: Communication in bounded depth circuits. Combinatorica, 14(2):203–216, 1994. [doi:10.1007/BF01215351]

[23]   Alan Siegel: On universal classes of extremely random constant-time hash functions. SIAM J. Comput., 33(3):505–543, 2004. [doi:10.1137/S0097539701386216]

[24]   Leslie G. Valiant: Graph-theoretic arguments in low-level complexity. In Proc. 6th Internat. Symp. on Mathematical Foundations of Computer Science (MFCS’77), pp. 162–176. Springer, 1977. [doi:10.1007/3-540-08353-7_135]

[25]   Emanuele Viola: On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1–72, 2009. [doi:10.1561/0400000033]

[26]   Emanuele Viola: Special topics in complexity theory, 2017. Available on author’s webpage.