{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T17:23:16Z","timestamp":1751649796283},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T00:00:00Z","timestamp":1414454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9946-9","type":"journal-article","created":{"date-parts":[[2014,10,27]],"date-time":"2014-10-27T11:32:05Z","timestamp":1414409525000},"page":"326-343","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["$$\\mathrm {3SUM}$$ 3 SUM , $$\\mathrm {3XOR}$$ 3 XOR , Triangles"],"prefix":"10.1007","volume":"74","author":[{"given":"Zahra","family":"Jafargholi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,28]]},"reference":[{"issue":"2","key":"9946_CR1","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/1059513.1059515","volume":"52","author":"N Ailon","year":"2005","unstructured":"Ailon, N., Chazelle, B.: Lower bounds for linear degeneracy testing. J. ACM 52(2), 157\u2013171 (2005)","journal-title":"J. ACM"},{"issue":"3","key":"9946_CR2","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple constructions of almost $$k$$ k -wise independent random variables. Random Struct. Algorithms 3(3), 289\u2013304 (1992)","journal-title":"Random Struct. Algorithms"},{"key":"9946_CR3","unstructured":"Amossen, R.R.: Scalable Query Evaluation in Realational Databases. PhD Thesis, IT University of Copenhagen (2011)"},{"issue":"3","key":"9946_CR4","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209\u2013223 (1997)","journal-title":"Algorithmica"},{"issue":"4","key":"9946_CR5","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1007\/s00453-007-9036-3","volume":"50","author":"I Baran","year":"2008","unstructured":"Baran, I., Demaine, E.D., P\u01cetra\u015fcu, M.: Subquadratic algorithms for 3sum. Algorithmica 50(4), 584\u2013596 (2008)","journal-title":"Algorithmica"},{"key":"9946_CR6","unstructured":"Bhattacharyya, A., Indyk, P., Woodruff, D.P., Xie, N.: The complexity of linear dependence problems in vector spaces. In: ACM Innovations in Theoretical Computer Science Conference (ITCS), pp. 496\u2013508 (2011)"},{"key":"9946_CR7","doi-asserted-by":"crossref","unstructured":"Bj\u0151rklund, A., Pagh, R., Williams, V.V., Zwick, U.: Listing triangles. In: Colloquium on Automata, Languages and Programming (ICALP) (2014)","DOI":"10.1007\/978-3-662-43948-7_19"},{"key":"9946_CR8","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge, MA (2001)"},{"key":"9946_CR9","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M.: Universal hashing and $$k$$ k -wise independent random variables via integer arithmetic without primes. In: Symposium on Theoretical Aspects of Computer Science (STACS), pp. 569\u2013580 (1996)","DOI":"10.1007\/3-540-60922-9_46"},{"key":"9946_CR10","unstructured":"Elkin, M.: An improved construction of progression-free sets (2008). arXiv:0801.4310"},{"key":"9946_CR11","doi-asserted-by":"crossref","unstructured":"Erickson, J.: Lower bounds for linear satisfiability problems. Chic. J. Theor. Comput. Sci. (1999)","DOI":"10.4086\/cjtcs.1999.008"},{"key":"9946_CR12","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $${O}(n^2)$$ O ( n 2 ) problems in computational geometry. Comput. Geom. 5, 165\u2013185 (1995)","journal-title":"Comput. Geom."},{"key":"9946_CR13","doi-asserted-by":"crossref","unstructured":"Gutfreund, D., Viola, E.: Fooling parity tests with parity gates. In: 8thWorkshop on Randomization and Computation (RANDOM), pp. 381\u2013392. Springer (2004)","DOI":"10.1007\/978-3-540-27821-4_34"},{"issue":"4","key":"9946_CR14","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9946_CR15","unstructured":"Jorgesen, A.G., Pettie, S.: Threesomes, degenerates, and love triangles. In: IEEE Symposium on Foundations of Computer Science (FOCS) (2014)"},{"key":"9946_CR16","doi-asserted-by":"crossref","unstructured":"Maslen, D.K., Rockmore, D.N.: Generalized FFTs\u2014a survey of some recent results. In: Groups and Computation, II (New Brunswick, NJ, 1995), volume 28 of DIMACS Ser. Discrete Math. Theor. Comput. Sci., pp. 183\u2013237. Amer. Math. Soc., Providence, RI (1997)","DOI":"10.1090\/dimacs\/028\/13"},{"issue":"4","key":"9946_CR17","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput. 22(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9946_CR18","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci. 49(2), 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9946_CR19","unstructured":"O\u2019Bryant, K.: Sets of integers that do not contain long arithmetic progressions (2008). arXiv:0811.3057"},{"key":"9946_CR20","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: ACM Symposium on the Theory of Computing (STOC), pp. 603\u2013610 (2010)","DOI":"10.1145\/1806689.1806772"},{"key":"9946_CR21","doi-asserted-by":"crossref","unstructured":"Pagh, A., Pagh, R.: Scalable computation of acyclic joins. In: ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 225\u2013232 (2006)","DOI":"10.1145\/1142351.1142384"},{"key":"9946_CR22","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Williams, R.: On the possibility of faster SAT algorithms. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1065\u20131075 (2010)","DOI":"10.1137\/1.9781611973075.86"},{"key":"9946_CR23","doi-asserted-by":"crossref","unstructured":"Ruzsa, I.Z.: Solving a linear equation in a set of integers I. Acta Arith. LXV(3), 261\u2013263 (1993)","DOI":"10.4064\/aa-65-3-259-282"},{"issue":"6","key":"9946_CR24","doi-asserted-by":"crossref","first-page":"1757","DOI":"10.1109\/18.641542","volume":"43","author":"A Vardy","year":"1997","unstructured":"Vardy, A.: The intractability of computing the minimum distance of a code. IEEE Trans. Inf. Theory 43(6), 1757\u20131766 (1997)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9946_CR25","unstructured":"Viola, E.: Reducing 3XOR to listing triangles, an exposition (2011). http:\/\/www.ccs.neu.edu\/home\/viola\/"},{"key":"9946_CR26","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. In: ACM Symposium on the Theory of Computing (STOC), pp. 455\u2013464 (2009)","DOI":"10.1145\/1536414.1536477"},{"key":"9946_CR27","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 645\u2013654 (2010)","DOI":"10.1109\/FOCS.2010.67"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9946-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9946-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9946-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T13:51:34Z","timestamp":1565963494000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9946-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,28]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9946"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9946-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2014,10,28]]}}}