{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T14:42:53Z","timestamp":1743604973856},"reference-count":39,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2022,3,1]]},"DOI":"10.1587\/transfun.2021eai0003","type":"journal-article","created":{"date-parts":[[2021,10,7]],"date-time":"2021-10-07T22:10:10Z","timestamp":1633644610000},"page":"131-141","source":"Crossref","is-referenced-by-count":1,"title":["Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms"],"prefix":"10.1587","volume":"E105.A","author":[{"given":"Kyohei","family":"CHIBA","sequence":"first","affiliation":[{"name":"School of Informatics and Engineering, The University of Electro-Communications"}]},{"given":"Hiro","family":"ITO","sequence":"additional","affiliation":[{"name":"School of Informatics and Engineering, The University of Electro-Communications"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] S.P.A. Alewijnse, T.M. Bagautdinov, M. de Berg, Q.W. Bouts, A.P. ten Brink, K. Buchin, and M.A. Westenberg, \u201cProgressive geometric algorithms,\u201d Proc. SOCG&apos;14, pp.50-59, 2014 (Journal version: JoCG, vol.6, no.2, pp.72-92, 2015). 10.1145\/2582112.2582156","DOI":"10.1145\/2582112.2582156"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, \u201cEfficient testing of large graphs,\u201d Proc. FOCS 99, pp.656-666, 1999 (Journal version: Combinatorica, vol.20, pp.451-476, 2000). 10.1007\/s004930070001","DOI":"10.1007\/s004930070001"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] N. Alon, E. Fischer, I. Newman, and A. Shapira, \u201cA combinatorial characterization of the testable graph properties: It&apos;s all about regularity,\u201d SIAM J. Comput., vol.39, no.1, pp.143-167, 2009. 10.1137\/060667177","DOI":"10.1137\/060667177"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] N. Alon and A. Shapira, \u201cEvery monotone graph property is testable,\u201d Proc. STOC 2005, pp.128-138, 2005. (Journal version: SIAM J. Comput., vol.38, no.6, pp.1703-1727, 2008). 10.1137\/050633445","DOI":"10.1137\/050633445"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] N. Alon and A. Shapira, \u201cA characterization of the (natural) graph properties testable with a one-sided error,\u201d Proc. FOCS 2005, pp.429-438, 2005 (Journal version: SIAM J. Comput., vol.37, no.6, pp.1703-1727, 2008). 10.1137\/06064888x","DOI":"10.1137\/06064888X"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] T. Batu, P. Berenbrink, and C. Sohler, \u201cA sublinear-time approximation scheme for bin packing,\u201d Theor. Comput. Sci., vol.410, no.47-49, pp.5082-5092, 2009. 10.1016\/j.tcs.2009.08.006","DOI":"10.1016\/j.tcs.2009.08.006"},{"key":"7","unstructured":"[7] J. Babu, A. Khoury, and I. Newman, \u201cEvery property of outerplanar graphs is testable,\u201d Proc. RANDOM 2016, LIPICS, pp.21:1-21:19, 2016. 10.4230\/LIPIcs.APPROX-RANDOM.2016.21"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] A. Bhattacharyya and Y. Yoshida, Property Testing \u2014 Problems and Techniques, Springer, 2021.","DOI":"10.1007\/978-981-16-8622-1"},{"key":"9","unstructured":"[9] M. Boddy and T.L. Dean, \u201cSolving time-dependent planning problems,\u201d Proc. IJCAI&apos;89, vol.2, pp.979-984, 1989."},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] A. Bogdanov, K. Obata, abd L. Trevisan, \u201cA lower bound for testing 3-colorability in bounded-degree graphs,\u201d Proc. FOCS 02, pp.93-102, 2002. 10.1109\/sfcs.2002.1181886","DOI":"10.1109\/SFCS.2002.1181886"},{"key":"11","unstructured":"[11] K. Chiba, M. Imura, H. Ito, and I. Newman, \u201cSublinear progressive algorithms \u2014 The framework and fundamental theorems,\u201d The 5th International Workshop on Innovative Algorithms for Big Data (IABD2019), Kyoto, Japan, Nov. 2019."},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] R. Diestel: Graph Theory, 5th ed., Springer, 2016.","DOI":"10.1007\/978-3-662-53622-3"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] H. Fichtenberger, P. Peng, and C. Sohler, \u201cEvery testable (infinite) property of bounded-degree graphs contains an infinite hyperfinite subproperty, arXiv: 1811.02937, 2018 (also appeared in SODA2019). 10.1137\/1.9781611975482.45","DOI":"10.1137\/1.9781611975482.45"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] L. Gishboliner and A. Shapira, \u201cDeterministic vs non-deterministic graph property testing,\u201d Electronic Colloquium on Computational Complexity, Report no.59, pp.1-17, 2013.","DOI":"10.1007\/s11856-014-1096-x"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] O. Goldreich, ed., Property Testing \u2014 Current Research and Surveys, LNCS 6390, Springer, 2010. 10.1007\/978-3-642-16367-8","DOI":"10.1007\/978-3-642-16367-8"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] O. Goldreich, Introduction to Property Testing, Cambridge University Press, 2017. 10.1017\/9781108135252","DOI":"10.1017\/9781108135252"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] O. Goldreich, S. Goldwasser, and D. Ron, \u201cProperty testing and its connection to learning and approximation,\u201d J. ACM, vol.45, no.4, pp.653-750, July 1998. 10.1145\/285055.285060","DOI":"10.1145\/285055.285060"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] O. Goldreich and D. Ron, \u201cProperty testing in bounded degree graphs,\u201d Proc. STOC 1997, pp.406-415, 1997 (Journal versioon: Algorithmica, vol.32, no.2, pp.302-343, 2002). 10.1007\/s00453-001-0078-7","DOI":"10.1007\/s00453-001-0078-7"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] W. Hoeffding, \u201cProbability inequalities for sums of bounded random variables,\u201d J. Am. Stat. Assoc., vol.58, no.301, pp.13-30, 1963. 10.1080\/01621459.1963.10500830","DOI":"10.1080\/01621459.1963.10500830"},{"key":"20","unstructured":"[20] H. Ito, \u201cEvery property is testable on a natural class of scale-free multigraphs,\u201d Proc. ESA 2016, LIPICS, vol.49, pp.21:2-21:15, 2016 (ISBN 978-3-95977-005-7)."},{"key":"21","doi-asserted-by":"publisher","unstructured":"[21] H. Ito, \u201cWhat graph properties are constant-time testable? \u2014 Dense graphs, sparse graphs, and complex networks,\u201d The Review of Socionetwork Strategies, vol.13, no.2, pp.101-121, Springer, 2019. 10.1007\/s12626-019-00054-0","DOI":"10.1007\/s12626-019-00054-0"},{"key":"22","doi-asserted-by":"publisher","unstructured":"[22] H. Ito, A. Khoury, and I. Newman, \u201cOn the characterization of 1-sided error strongly-testable graph properties for bounded-degree graphs,\u201d Comput. Complex., vol.29, no.1, pp.1-45, Springer, 2020. 10.1007\/s00037-019-00191-6","DOI":"10.1007\/s00037-019-00191-6"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] H. Ito, S. Kiyoshima, and Y. Yoshida, \u201cConstant-time approximation algorithms for the knapsack problem,\u201d Proc. TAMC 2012, LNCS 7287, pp.131-142, Springer, 2012. 10.1007\/978-3-642-29952-0_17","DOI":"10.1007\/978-3-642-29952-0_17"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] H. Ito, A. Nagao, and T. Park, \u201cGeneralized shogi, chess, and xiangqui are constant-time testable,\u201d IEICE Trans. Fundamentals, vol.E102-A, no.9, pp.1126-1133, Sept. 2019. 10.1587\/transfun.e102.a.1126","DOI":"10.1587\/transfun.E102.A.1126"},{"key":"25","unstructured":"[25] H. Ito and T. Ueda, \u201cHow to solve the cake-cutting problem in sublinear time,\u201d Proc. 8th International Conference on Fun with Algorithms (FUN2016), LIPICS, vol.49, pp.21:1-21:15, 2016 (ISBN 978-3-95977-005-7)."},{"key":"26","doi-asserted-by":"crossref","unstructured":"[26] N. Katoh, et al., eds.: \u201cSpecial Issue on Foundations of Innovative Algorithms for Big Data \u2014 Sublinear Computational Paradigm and Its Expansions\u201d, The Review of Socionetwork Strategies, vol.13, no.2, 2019.","DOI":"10.1007\/s12626-019-00058-w"},{"key":"27","unstructured":"[27] N. Katoh, et al. eds., Sublinear Computation Paradigm \u2014 Algorithmic Revolution in the Big Data Era, Springer, 2022 (Open Access: DOI: 10.1007\/978-981-16-4095-7). 10.1007\/978-981-16-4095-7"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] M. Kusumoto and Y. Yoshida, \u201cTesting forest-isomorphizm in the adjacency list model,\u201d Proc. of ICALP2014 (1), LNCS 8572, pp.763-774, 2014. 10.1007\/978-3-662-43948-7_63","DOI":"10.1007\/978-3-662-43948-7_63"},{"key":"29","unstructured":"[29] R.-H. Li, L. Qin, J. Xu Yu, and R. Mao, \u201cEfficient and progressive group steiner tree search,\u201d Proc. SIGMOD\/PODS&apos;16, pp.91-106, 2016. 10.1145\/2882903.2915217"},{"key":"30","doi-asserted-by":"publisher","unstructured":"[30] L. Lov\u00e1sz and K. Vesztergombi, \u201cNon-deterministic graph property testing,\u201d Combinatorics, Probability and Computing, vol.22, no.5, pp.749-762, 2013. 10.1017\/s0963548313000205","DOI":"10.1017\/S0963548313000205"},{"key":"31","unstructured":"[31] A. Mesrikhani and M. Farshi, \u201cProgressive sorting in the external memory model,\u201d The CSI Journal on Computer Science and Engineering, vol.15, no.2, pp.1-4, 2018."},{"key":"32","unstructured":"[32] A. Mesrikhani, M. Farshi, and M. Davoodi, \u201cProgressive algorithm for euclidean minimum spanning tree,\u201d Proc. ICCG&apos;18, pp.29-32, 2018."},{"key":"33","doi-asserted-by":"publisher","unstructured":"[33] I. Newman and C. Sohler, \u201cEvery property of hyperfinite graphs is testable,\u201d Proc. STOC 2011, ACM, pp.675-784, 2011 (Journal version: SIAM J. Comput., vol.42, no.3, pp.1095-1112, 2013). 10.1137\/120890946","DOI":"10.1137\/120890946"},{"key":"34","doi-asserted-by":"publisher","unstructured":"[34] R. Rubinfeld and M. Sudan, \u201cRobust characterizations of polynomials with applications to program testing,\u201d SIAM J. Comput., vol.25, no.2, pp.252-271, 1996 (Conference version was appeared in 1992). 10.1137\/s0097539793255151","DOI":"10.1137\/S0097539793255151"},{"key":"35","unstructured":"[35] E. Szemer\u00e9di, \u201cRegular partitions of graphs,\u201d J.C. Bermond, J.C. Fournier, M. Las Vergnas, and D. Sotteau, eds., Colloq. Internat. CNRS, CNRS, Paris, pp.399-401, 1978."},{"key":"36","doi-asserted-by":"crossref","unstructured":"[36] A.C. Yao, \u201cLower bounds to randomized algorithms for graph properties,\u201d Proc. FOCS 1987, pp.393-400, 1987. 10.1109\/sfcs.1987.39","DOI":"10.1109\/SFCS.1987.39"},{"key":"37","doi-asserted-by":"crossref","unstructured":"[37] Y. Yoshida, \u201cA characterization of locally testable affine-invariant properties via decomposition theorems,\u201d Proc. STOC 14, pp.154-163, 2014. 10.1145\/2591796.2591802","DOI":"10.1145\/2591796.2591802"},{"key":"38","doi-asserted-by":"publisher","unstructured":"[38] Y. Yoshida and H. Ito, \u201cProperty testing on <i>k<\/i>-vertex-connectivity of graphs,\u201d Proc. ICALP 08, Part I, LNCS 5125, pp.539-550, Springer, 2008 (Journal version: Algorithmica, vol.62, no.3-4, pp.701-712, 2012). 10.1007\/s00453-010-9477-y","DOI":"10.1007\/s00453-010-9477-y"},{"key":"39","doi-asserted-by":"publisher","unstructured":"[39] Y. Yoshida and H. Ito, \u201cQuery-number preserving reductions and linear lower bounds for testing,\u201d IEICE Trans. Inf. &amp; Syst., vol.E93-D, no.2, pp.233-240, Feb. 2010. 10.1587\/transinf.e93.d.233","DOI":"10.1587\/transinf.E93.D.233"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E105.A\/3\/E105.A_2021EAI0003\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T14:29:29Z","timestamp":1725892169000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E105.A\/3\/E105.A_2021EAI0003\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,1]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2021eai0003","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"type":"print","value":"0916-8508"},{"type":"electronic","value":"1745-1337"}],"subject":[],"published":{"date-parts":[[2022,3,1]]},"article-number":"2021EAI0003"}}