Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds
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.