Sublinear-time reductions for big data computing. (English) Zbl 07550538
Du, Ding-Zhu (ed.) et al., Combinatorial optimization and applications. 15th international conference, COCOA 2021, Tianjin, China, December 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13135, 374-388 (2021).
Summary: With the rapid popularization of big data, the dichotomy between tractable and intractable problems in big data computing has been shifted. Sublinear time, rather than polynomial time, has recently been regarded as the new standard of tractability in big data computing. This change brings the demand for new methodologies in computational complexity theory in the context of big data. Based on the prior work for sublinear-time complexity classes [9], this paper focuses on sublinear-time reductions specialized for problems in big data computing. First, the pseudo-sublinear-time reduction is proposed and the complexity classes P and PsT are proved to be closed under it. To establish PsT-intractability for certain problems in P, we find the first problem in \(\mathtt{P} {\setminus } \mathtt{PsT} \). Using the pseudo-sublinear-time reduction, we prove that the nearest edge query is in PsT but the algebraic equation root problem is not. Then, the pseudo-polylog-time reduction is introduced and the complexity class PsPL is proved to be closed under it. The PsT-completeness under it is regarded as an evidence that some problems can not be solved in polylogarithmic time after a polynomial-time preprocessing, unless PsT = PsPL. We prove that all PsT-complete problems are also P-complete, which gives a further direction for identifying PsT-complete problems.
For the entire collection see [Zbl 1490.68014].
For the entire collection see [Zbl 1490.68014].
MSC:
| 68T09 | Computational aspects of data analysis and big data |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | SSD ranking: the fastest solid state drives. https://www.gamingpcbuilder.com/ssd-ranking-the-fastest-solid-state-drives/. Accessed 4 Aug 2021 |
| [2] | Baswana, S., Chaudhury, S.R., Choudhary, K., Khan, S.: Dynamic DFS in undirected graphs: breaking the \(o(m)\) barrier. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10-12 January 2016, pp. 730-739. SIAM (2016) · Zbl 1410.68277 |
| [3] | Bringmann, K.: Fine-grained complexity theory (tutorial). In: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019) · Zbl 07559113 |
| [4] | Cadoli, M.; Donini, FM; Liberatore, P.; Schaerf, M., Preprocessing of intractable problems, Inf. Comput., 176, 2, 89-120 (2002) · Zbl 1012.68082 · doi:10.1006/inco.2001.3043 |
| [5] | Chen, L., Duan, R., Wang, R., Zhang, H., Zhang, T.: An improved algorithm for incremental DFS tree in undirected graphs. In: Eppstein, D. (ed.) 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018. Volume 101 of LIPIcs, Malmö, Sweden, 18-20 June 2018, pp. 16:1-16:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018) · Zbl 1477.05178 |
| [6] | Cook, SA, A taxonomy of problems with fast parallel algorithms, Inf. Control, 64, 1-3, 2-22 (1985) · Zbl 0575.68045 · doi:10.1016/S0019-9958(85)80041-3 |
| [7] | Crescenzi, P.: A short guide to approximation preserving reductions. In: Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, 24-27 June 1997, pp. 262-273. IEEE Computer Society (1997) |
| [8] | Fan, W.; Geerts, F.; Neven, F., Making queries tractable on big data with preprocessing, Proc. VLDB Endow., 6, 9, 685-696 (2013) · doi:10.14778/2536360.2536368 |
| [9] | Gao, X.; Li, J.; Miao, D.; Liu, X., Recognizing the tractability in big data computing, Theor. Comput. Sci., 838, 195-207 (2020) · Zbl 1453.68167 · doi:10.1016/j.tcs.2020.07.026 |
| [10] | Holdsworth, B., Woods, R.C.: Karnaugh maps and function simplification. In: Holdsworth, B., Woods, R.C. (eds.) Digital Logic Design, 4th edn, pp. 43-80. Newnes, Oxford (2002) |
| [11] | Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987). (Reprint from 1967) |
| [12] | Li, J.: Complexity, algorithms and quality of big data intensive computing. In: Database Systems for Advanced Applications - 19th International Conference, DASFAA 2014, Bali, Indonesia. Springer (2014) |
| [13] | Nekrich, Y.; Navarro, G.; Fomin, FV; Kaski, P., Sorted range reporting, Algorithm Theory - SWAT 2012, 271-282 (2012), Heidelberg: Springer, Heidelberg · Zbl 1347.68343 · doi:10.1007/978-3-642-31155-0_24 |
| [14] | Papadimitriou, CH, Computational Complexity (1994), Reading: Addison-Wesley, Reading · Zbl 0833.68049 |
| [15] | Reif, JH, Depth-first search is inherently sequential, Inf. Process. Lett., 20, 5, 229-234 (1985) · Zbl 0572.68051 · doi:10.1016/0020-0190(85)90024-9 |
| [16] | Smith, JR, Parallel algorithms for depth-first searches I. Planar graphs, SIAM J. Comput., 15, 3, 814-830 (1986) · Zbl 0612.68059 · doi:10.1137/0215058 |
| [17] | Williams, V.V.: Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In: Husfeldt, T., Kanj, I.A. (eds.) 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Volume 43 of LIPIcs, Patras, Greece, 16-18 September 2015, pp. 17-29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015) · Zbl 1378.68054 |
| [18] | Williams, V.V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pp. 3447-3487. World Scientific (2018) · Zbl 1490.68115 |
| [19] | Yang, J.; Wang, H.; Cao, Y., Tractable queries on big data via preprocessing with logarithmic-size output, Knowl. Inf. Syst., 56, 1, 141-163 (2017) · doi:10.1007/s10115-017-1092-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
