{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:39:35Z","timestamp":1787326775583,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1855464"],"award-info":[{"award-number":["DMS-1855464"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018267"],"award-info":[{"award-number":["2018267"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We consider the problem of determining the maximal $\\alpha \\in (0,1]$ such that every matching $M$ of size $k$ (or at most $k$) in a bipartite graph $G$ contains an induced matching of size at least $\\alpha |M|$. This measure was recently introduced in [N. Alon et al., Adv. Neural Inf. Process. Syst., 2017, pp. 2097--2106] and is motivated by computational models in cognitive neuroscience as well as by modeling interference in radio and communication networks. We prove various hardness results for computing $\\alpha$ either exactly or approximately. En route to our results, we also consider the maximum connected matching problem: determining the largest matching $N$ in a graph $G$ such that every two edges in $N$ are connected by an edge. We prove a nearly optimal $n^{1-\\epsilon}$ hardness of approximation result (under randomized reductions) for connected matching in bipartite graphs (with both sides of cardinality $n$). Toward this end we define bipartite half-covers: a new combinatorial object that may be of independent interest. To our knowledge, the best previous hardness result for the maximum connected matching problem was that it is hard to approximate within some constant $\\beta&gt;1$. Finally, we demonstrate the existence of bipartite graphs with $n$ vertices on each side of average degree $d$, achieving $\\alpha=1\/2-\\epsilon$ for matchings of size sufficiently smaller than $n\/d$. This nearly matches the trivial upper bound of $1\/2$ on $\\alpha$ which holds for any graph containing a path of length 3.<\/jats:p>","DOI":"10.1137\/18m1224672","type":"journal-article","created":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T14:03:06Z","timestamp":1585058586000},"page":"885-903","source":"Crossref","is-referenced-by-count":3,"title":["Multitasking Capacity: Hardness Results and Improved Constructions"],"prefix":"10.1137","volume":"34","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan D.","family":"Cohen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas L","family":"Griffiths","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Reichman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Igor","family":"Shinkar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tal","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Yu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,3,24]]},"reference":[{"key":"atypb1","first-page":"1079","author":"Alon N.","year":"2012","journal-title":"ACM"},{"key":"atypb2","first-page":"2100","author":"Alon N.","year":"2017","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"atypb3","first-page":"74","author":"Austrin P.","year":"2009","journal-title":"IEEE"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/18.179355"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01994876"},{"key":"atypb6","first-page":"34","author":"Cameron K.","year":"2003","journal-title":"New York"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/2873054"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1985.1096245"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1037\/0033-295X.97.3.332"},{"key":"atypb10","first-page":"463","volume":"2","author":"Erdos P.","year":"1935","journal-title":"Compos. Math."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.3758\/s13415-013-0236-9"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305006759"},{"key":"atypb13","first-page":"201","author":"Golovach P. A.","year":"2014","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2014.06.003"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.04.001"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122555"},{"key":"atypb18","first-page":"954","author":"Manurangsi P.","year":"2017","journal-title":"ACM"},{"key":"atypb19","unstructured":"S. Musslick, B. Dey, K. Ozcimder, M. Patwary, T. L. Willke, and J. D. Cohen,\n                      Controlled vs. automatic processing: A graph-theoretic approach to the analysis of serial vs. parallel processing in neural network architectures\n                      , in Proceedings of the 38th Annual Meeting of the Cognitive Science Society (CogSci), 2016, pp. 1547-1552."},{"key":"atypb20","unstructured":"S. Musslick, B. Dey, K. Ozcimder, M. Patwary, T. L. Willke, and J. D. Cohen,\n                      Parallel processing versus efficiency of representation in neural networks\n                      , in Proceedings of the 16th Neural Computation and Psychology Workshop, 2016."},{"key":"atypb21","unstructured":"C. H. Papadimitriou,\n                      Computational Complexity\n                      , John Wiley and Sons, New York, 2003."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1206"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"D. E. Rumelhart, J. L. McClelland, and P. R. Group,\n                      Parallel Distributed Processing\n                      , Vol. 1, MIT Press, Cambridge, MA, 1987.","DOI":"10.7551\/mitpress\/5237.001.0001"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1037\/0033-295X.84.2.127"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1037\/0033-295X.111.4.1003"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300004478"},{"key":"atypb27","first-page":"681","author":"Zuckerman D.","year":"2006","journal-title":"ACM"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1224672","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:00Z","timestamp":1787322960000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1224672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1224672"],"URL":"https:\/\/doi.org\/10.1137\/18m1224672","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}