{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:15:56Z","timestamp":1787390156095,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,1,9]],"date-time":"2013-01-09T00:00:00Z","timestamp":1357689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,1,9]]},"DOI":"10.1145\/2422436.2422469","type":"proceedings-article","created":{"date-parts":[[2013,1,3]],"date-time":"2013-01-03T12:58:22Z","timestamp":1357217902000},"page":"269-282","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Runtime guarantees for regression problems"],"prefix":"10.1145","author":[{"given":"Hui Han","family":"Chin","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksander","family":"Madry","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gary L.","family":"Miller","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,1,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"The multiplicative weights update method: a meta algorithm and applications. Technical report","author":"Arora S.","year":"2005","unstructured":"S. Arora , E. Hazan , and S. Kale . The multiplicative weights update method: a meta algorithm and applications. Technical report , Princeton University , 2005 . 5 S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta algorithm and applications. Technical report, Princeton University, 2005. 5"},{"key":"e_1_3_2_1_2_1","volume-title":"On element SDD approximability. CoRR, abs\/0911.0547","author":"Avron H.","year":"2009","unstructured":"H. Avron , G. Shklarski , and S. Toledo . On element SDD approximability. CoRR, abs\/0911.0547 , 2009 . 2.1 H. Avron, G. Shklarski, and S. Toledo. On element SDD approximability. CoRR, abs\/0911.0547, 2009. 2.1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-011-0029-5"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989496"},{"key":"e_1_3_2_1_5_1","first-page":"2","article-title":"Solving elliptic finite element systems in near-linear time with support preconditioners. CoRR, cs.","author":"Boman E. G.","year":"2004","unstructured":"E. G. Boman , B. Hendrickson , and S. A. Vavasis . Solving elliptic finite element systems in near-linear time with support preconditioners. CoRR, cs. NA\/0407022 , 2004 . 2 .1 E. G. Boman, B. Hendrickson, and S. A. Vavasis. Solving elliptic finite element systems in near-linear time with support preconditioners. CoRR, cs.NA\/0407022, 2004. 2.1","journal-title":"NA\/0407022"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Candes J.","year":"2006","unstructured":"J. Candes , E. Compressive sampling . Proceedings of the International Congress of Mathematicians , 2006 . 1, 1 J. Candes, E. Compressive sampling. Proceedings of the International Congress of Mathematicians, 2006. 1, 1"},{"key":"e_1_3_2_1_8_1","volume-title":"Pde, Wavelet, And Stochastic Methods","author":"Chan T.","year":"2005","unstructured":"T. Chan and J. Shen . Image Processing And Analysis: Variational , Pde, Wavelet, And Stochastic Methods . SIAM , 2005 . 3.1, 6.1 T. Chan and J. Shen. Image Processing And Analysis: Variational, Pde, Wavelet, And Stochastic Methods. SIAM, 2005. 3.1, 6.1"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_2_1_12_1","volume-title":"Support-graph preconditioners for 2-dimensional trusses. CoRR, abs\/cs\/0703119","author":"Daitch S. I.","year":"2007","unstructured":"S. I. Daitch and D. A. Spielman . Support-graph preconditioners for 2-dimensional trusses. CoRR, abs\/cs\/0703119 , 2007 . 2.1 S. I. Daitch and D. A. Spielman. Support-graph preconditioners for 2-dimensional trusses. CoRR, abs\/cs\/0703119, 2007. 2.1"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-006-8803-0"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0738"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/040608982"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/080725891"},{"key":"e_1_3_2_1_19_1","first-page":"745","volume-title":"Proceedings of the 28th International Conference on Machine Learning (ICML-11), ICML '11","author":"Hocking T.","year":"2011","unstructured":"T. Hocking , J.-P. Vert , F. Bach , and A. Joulin . Clusterpath: an algorithm for clustering using convex fusion penalties. In L. Getoor and T. Scheffer, editors , Proceedings of the 28th International Conference on Machine Learning (ICML-11), ICML '11 , pages 745 -- 752 , New York, NY, USA , June 2011 . ACM. 3.4 T. Hocking, J.-P. Vert, F. Bach, and A. Joulin. Clusterpath: an algorithm for clustering using convex fusion penalties. In L. Getoor and T. Scheffer, editors, Proceedings of the 28th International Conference on Machine Learning (ICML-11), ICML '11, pages 745--752, New York, NY, USA, June 2011. ACM. 3.4"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/562474"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213979"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262177"},{"key":"e_1_3_2_1_23_1","volume-title":"Conference Talk","author":"Koutis I.","year":"2009","unstructured":"I. Koutis and G. Miller . The combinatorial multigrid solver . Conference Talk , March 2009 . 6 I. Koutis and G. Miller. The combinatorial multigrid solver. Conference Talk, March 2009. 6"},{"key":"e_1_3_2_1_24_1","volume-title":"Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)","author":"Koutis I.","year":"2007","unstructured":"I. Koutis and G. L. Miller . A linear work, O(n1\/6) time, parallel algorithm for solving planar Laplacians . In Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007) , 2007 . 3.1 I. Koutis and G. L. Miller. A linear work, O(n1\/6) time, parallel algorithm for solving planar Laplacians. In Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 2007. 3.1"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10331-5_99"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729694"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/27\/4\/045009"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160420503"},{"key":"e_1_3_2_1_33_1","volume-title":"Universital' catholique de Louvain","author":"Y.","year":"2007","unstructured":"Y. NESTEROV. Gradient methods for minimizing composite objective function. CORE Discussion Papers 2007076 , Universital' catholique de Louvain , Center for Operations Research and Econometrics (CORE) , 2007 . 1, 4.4 Y. NESTEROV. Gradient methods for minimizing composite objective function. CORE Discussion Papers 2007076, Universital' catholique de Louvain, Center for Operations Research and Econometrics (CORE), 2007. 1, 4.4"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882269"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976604773135104"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-2789(92)90242-F"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_2_1_38_1","volume-title":"Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105","author":"Spielman D. A.","year":"2006","unstructured":"D. A. Spielman and S.-H. Teng . Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105 , 2006 . 1, 2.1 D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105, 2006. 1, 2.1"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2005.00490.x"},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings of the 44th symposium on Theory of Computing, STOC '12","author":"Williams V. Vassilevska","year":"2012","unstructured":"V. Vassilevska Williams . Breaking the Coppersmith-Winograd barrier . In Proceedings of the 44th symposium on Theory of Computing, STOC '12 , 2012 . 2.1 V. Vassilevska Williams. Breaking the Coppersmith-Winograd barrier. In Proceedings of the 44th symposium on Theory of Computing, STOC '12, 2012. 2.1"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2007.906221"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2005.00532.x"}],"event":{"name":"ITCS '13: Innovations in Theoretical Computer Science","location":"Berkeley California USA","acronym":"ITCS '13","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 4th conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2422436.2422469","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2422436.2422469","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:14Z","timestamp":1750277654000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2422436.2422469"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,9]]},"references-count":44,"alternative-id":["10.1145\/2422436.2422469","10.1145\/2422436"],"URL":"https:\/\/doi.org\/10.1145\/2422436.2422469","relation":{},"subject":[],"published":{"date-parts":[[2013,1,9]]},"assertion":[{"value":"2013-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}