Julia Chuzhoy's Publications

The papers appear in the reverse chronological order of the original (usually conference) publication.


• Julia Chuzhoy and Sanjeev Khanna.
  Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm.
  In Proceedings of the 56th Annual (ACM) Symposium on Theory of Computing, (STOC), pages 83-94, 2024
  A full version, arxiv:2405.20861.
  
  
• Julia Chuzhoy and Sanjeev Khanna.
  A Faster Combinatorial Algorithm for Maximum Bipartite Matching.
  In Proceedings of the 2024 (ACM-SIAM) Symposium on Discrete Algorithms, (SODA), pages 2185-2235, 2024.
  A full version, arxiv:2312.12584.
  
  
• Julia Chuzhoy and Ruimin Zhang.
  A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths.
  In Proceedings of the 55th Annual (ACM) Symposium on Theory of Computing, (STOC), pages 1159--1172, 2023.
  A full version, arxiv.2304.09321.
  
  
• Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg and Zihan Tan.
  A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems.
  In 14th Innovations in Theoretical Computer Science Conference, (ITCS)} LIPIcs volue 251, pages 38:1--38:23, 2023.
  A full version, arxiv.2211.05906 (under slightly different title).
  
  
• Julia Chuzhoy.
  A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems.
  In Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2122-2213, 2023.
  A full version, arxiv.2211.10556.
  
  
• Julia Chuzhoy and Zihan Tan.
  A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs.
  In Proc. 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 303-316, 2022.
  A full version, arxiv.2202.06827.
  A video of an informal talk at Research at TTIC series.
  
  
• Julia Chuzhoy.
  Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time.
  In Proc. 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 626-639, 2021.
  A full version, arxiv.2109.05621.
  
  
• Julia Chuzhoy and Thatchaphol Saranurak.
  Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition.
  In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2478-2496, 2021.
  A full version, arXiv.2009.08479.
  
  
• Julia Chuzhoy, Sepideh Mahabadi and Zihan Tan.
  Towards Better Approximation of Graph Crossing Number.
  In Proc. of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 73-84, 2020.
  A full version, arXiv.2011.06545.
  
  
• Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng and Thatchaphol Saranurak.
  A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.
  In Proc. of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1158-1167, 2020.
  A full version, arXiv.1910.08025.
  
  
• Parinya Chalermsook, Julia Chuzhoy and Thatchaphol Saranurak.
  Pinning Down the Strong Wilber 1 Bound for Binary Search Trees.
  In Proc. APPROX 2020, LIPIcs, volume 176, pp. 33:1--33:21, 2020.
  Invited to Special Issue of Theory of Computing for APPROX/RANDOM 2020.
  A full version, arXiv.1912.02900.
  
  
• Julia Chuzhoy, Merav Parter and Zihan Tan.
  On Packing Low-Diameter Spanning Trees.
  In 47th International Colloquium on Automata, Languages, and Programming (ICALP) 2020.
  A full version, arXiv.2006.07486.
  
  
• Julia Chuzhoy and Sanjeev Khanna.
  A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems.
  In Proc. of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 389-400, 2019.
  A full version, arXiv:1905.11512.
  
  
• Julia Chuzhoy and Zihan Tan.
  Towards Tight(er) Bounds for the Excluded Grid Theorem.
  Journal of Combinatorial Theory, Series B, Volume 146, pp. 219-265, 2021.
  A preliminary version appeared in Proc. of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 1445-1464, 2019.
  An arxiv version, arXiv:1901.07944.
  
  
• Julia Chuzhoy and Rachit Nimavat.
  Large Minors in Expanders, arXiv:1901.09349, 2019.
  
  
• Julia Chuzhoy, David H.K. Kim and Rachit Nimavat.
  Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary .
  In Proc. of the 45th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 38:1-38:14, 2018.
  A full version, arXiv:1805.09956.
  
  
• Julia Chuzhoy, David H.K. Kim and Rachit Nimavat.
  Almost Polynomial Hardness for Node-Disjoint Paths in Grids.
  Theory of Computing, volume 17, pages 1-57, 2021.
  A preliminary version appeared in Proc. of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1220-1233, 2018.
  Invited to Theory of Computing journal.
  An Arxiv version, arXiv:1711.01980.
  
  
• Julia Chuzhoy, David H.K. Kim and Rachit Nimavat.
  New Hardness Results for Routing on Disjoint Paths.
  SIAM Journal on Computing, volume 51, issue 2, pages 17-189, 2022.
  A preliminary version appeared in Proc. of the 49th Annual ACM SIGACT Symposium on Theory of Computing, (STOC), pages 86-99, 2017
  Invited to the SICOMP STOC 2017 special issue.
  An Arxiv version, arXiv:1611.05429; slides.
  
  
• Julia Chuzhoy and Alina Ene.
  On Approximating Maximum Independent Set of Rectangles.
  In Proc. of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 820-829, 2016.
  A full version, arXiv:1608.00271.
  
  
• Julia Chuzhoy, David H.K. Kim and Shi Li.
  Improved Approximation for Node-Disjoint Paths in Planar Graphs.
  In Proc. of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 556-569, 2016.
  A full version, arXiv:1603.05520.
  
  
• Julia Chuzhoy.
  Improved Bounds for the Excluded Grid Theorem, arxiv:1602.02629.
  This paper contains a full version of the STOC 2015 paper, together with additional extensions.
  The paper focuses on the "improved" aspect. I am planning to write an expository article emphasizing the "simplified" aspect.
  
  
• Julia Chuzhoy.
  Excluded Grid Theorem: Improved and Simplified.
  In Proc. of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 645-654, 2015.
  For a full version, see this paper.
  
  
• Julia Chuzhoy and David H.K. Kim.
  On Approximating Node-Disjoint Paths in Grids.
  In Proc. of APPROX 2015, LIPIcs-Leibniz International Proceedings in Informatics (Vol. 40).
  
  
• Chandra Chekuri and Julia Chuzhoy.
  Degree-3 Treewdith Sparsifiers.
  In Proc. of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 242-255, 2015.
  A full version, arxiv:1410.1016
  
  
• Julia Chuzhoy.
  Improved Bounds for the Flat Wall Theorem.
  In Proc. of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 256-275, 2015.
  A full version, arxiv:1410.9276
  
  
• Chandra Chekuri and Julia Chuzhoy.
  Polynomial Bounds for the Grid-Minor Theorem.
  Journal of the ACM, Volume 63, Issue 5, Article no. 40, 2016.
  A preliminary version appeared in Proc. of the 46th Annual Symposium on the Theory of Computing (STOC), pages 60-69, 2014.
  
  • A detailed presentation of the proof with my voiceover: Part 1, Part 2, Part 3.1, Part 3.2, Part 4, Part 5.
  • A less detailed presentation: slides and video (interactive; static) of the talk at the Workshop on Flexible Network Design, Toronto, July 2013.
    
  
  
• Julia Chuzhoy.
  Flows, Cuts and Integral Routing in Graphs - an Approximation Algorithmist's Perspective. (An expository article).
  In Proc. of the International Congress of Mathematicians, pages 585-607, 2014.
  
  
• Chandra Chekuri and Julia Chuzhoy.
  Large-Treewidth Graph Decompositions and Applications.
  In Proc. of the 45th Annual ACM Symposium on Theory of Computing (STOC), pages 291-300, 2013.
  A full version, arXiv:1304.1577.
  
  
• Julia Chuzhoy and Shi Li.
  A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2.
  Journal of the ACM, Volume 63, Issue 5, article no. 45, 2016.
  A preliminary version appeared in Proc. of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS),
  pages 233-242, 2012.
  A co-winner of the FOCS 2012 Best Paper Award.
  
  
• Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan and Sanjeev Khanna.
  Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply.
  In Proc. of APPROX 2012, Lecture Notes in Computer Science 7408, pages 73-84, 2012.
  
  
• Parinya Chalermsook, Julia Chuzhoy, Alina Ene and Shi Li.
  Approximation Algorithms and Hardness of Integral Concurrent Flow.
  In Proc. of the 44th Symposium on Theory of Computing (STOC), pages 689-708, 2012.
  A full version
  
  
• Julia Chuzhoy.
  On Vertex Sparsifiers with Steiner Nodes.
  In Proc. of the 44th Symposium on Theory of Computing (STOC), pages 673-688, 2012.
  A full version, arXiv:1204.2844.
  
  
• Julia Chuzhoy.
  Routing in Undirected Graphs with Constant Congestion.
  SIAM Journal on Computing (special issue for STOC 2012), 45(4), pages 1490-1532, 2016.
  A preliminary version appeared in Proc. of the 44th Symposium on Theory of Computing (STOC), pages 855-874, 2012.
  A video and slides of my talk at the BIRS workshop on approximation algorithms and hardness of approximation, Nov 2011.
  
  
• Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan and Yuan Zhou.
  Approximation algorithms and hardness of the k-route cut problem.
  ACM Transactions on Algorithms (TALG) - Special Issue on SODA'12.
  Volume 12, Issue 1, Article No. 2, 2016
  A Preliminary version appeared in Proc. of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 780-799, 2012.
  
  
• Julia Chuzhoy.
  An Algorithm for the Graph Crossing Number Problem.
  In Proc. of the 43rd annual ACM Symposium on Theory of computing (STOC), pages 303-312, 2011.
  A full version, arXiv:1012.0255v1
  
  
• Julia Chuzhoy, Yury Makarychev and Anastasios Sidiropoulos.
  On Graph Crossing Number and Edge Planarization.
  In Proc. of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1050-1069, 2011.
  A full version.
  
  
• MohammadHossein Bateni and Julia Chuzhoy.
  Approximation Algorithms for the Directed k-Tour and k-Stroll Problems.
  Algorithmica 75(3), pages 545-561, 2013.
  A preliminary version appeared in Proc. of APPROX 2010, Lecture Notes in Computer Science 6302, pages 25-38, 2010.
  
  
  
• Parinya Chalermsook and Julia Chuzhoy.
  Resource Minimization for Fire Containment.
  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1334-1349, 2010.
  
  
• Deeparnab Chakrabarty, Julia Chuzhoy and Sanjeev Khanna.
  On Allocating Goods to Maximize Fairness.
  In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 107-116, 2009.
  • Full version.
  • Preliminary version, arXiv:0901.0205v1, Jan. 2009.
  • "Detailed" slides
  
  
  
• Julia Chuzhoy and Sanjeev Khanna.
  An O(k^3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.
  Theory of Computing, Volume 8, pp. 401-413, 2012.
  A preliminary version in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
  pages 437-441, 2009.
  
  
  
• Julia Chuzhoy and Paolo Codenotti.
  Resource Minimization Job Scheduling [Erratum].
  In Proceedings of APPROX 2009, Lecture Notes in Computer Science 5687, pages 70-83, 2009.
  A full version [Erratum].
  
  
• Parinya Chalermsook and Julia Chuzhoy.
  Maximum Independent Set of Rectangles.
  In Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms (SODA), pages 892-901, 2009.
  A more detailed version
  
  
• Julia Chuzhoy and Sanjeev Khanna.
  Algorithms for Single-Source Vertex-Connectivity.
  In Proc. of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 105-114, 2008.
  Full version containing all proofs
  
  
• Tanmoy Chakraborty, Julia Chuzhoy and Sanjeev Khanna.
  Network Design for Vertex Connectivity
  In Proc. of the 2008 ACM Symposium on Theory of Computing (STOC), pages 167 - 176, 2008.
  
  
• Julia Chuzhoy and Sanjeev Khanna.
  Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems
  Journal of the ACM, Volume 56, issue 2, Article 6, 2009.
  Preliminary version appeared in Proc. of the 39th ACM Symposium on Theory of Computing (STOC), pages 179 - 188, 2007.
  
  
• Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna and Kunal Talwar.
  Hardness of Routing with Congestion in Directed Graphs.
  In Proc. of the 39th ACM Symposium on Theory of Computing (STOC), pages 165-178, 2007.
  
  
• Julia Chuzhoy and Sanjeev Khanna.
  Hardness of Directed Routing with Congestion.
  ECCC technical report TR06-109, 2006.
  
  
• Julia Chuzhoy and Sanjeev Khanna.
  Hardness of Cut Problems in Directed Graphs.
  In Proc. of the 38th ACM Symposium on Theory of Computing (STOC), pages 527-536, 2006.
  Notice: the APX-hardness proof for undirected sparsest cut that appears in the Appendix of this paper is incorrect. A correct proof appears in the Full version of our multicut paper that appeared at STOC 2007, whose results also subsume the results of this paper.
  
  
• Mihai Badoiu, Julia Chuzhoy, Piotr Indyk and Anastasios Sidiropoulos.
  Embedding Ultrametrics Into Low-Dimensional Spaces.
  In Proc. of the 22nd ACM Symposium on Computational Geometry (SOCG), pages 187-196, 2006.
  
  
• Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Seffi Naor and Ariel Orda.
  Non-cooperative multicast and facility location games.
  IEEE Journal on Selected Areas in Communication (Special Issue on Non-Cooperative Behavior in Networking),
  vol. 25, no. 6, pp. 1193-1206, 2007. (Invited paper.)
  Preliminary version appeared in Proc. of the 7th ACM Conference on Electronic Commerce (EC), pages 72-81, 2006
  
  
• Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna and Lisa Zhang.
  Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.
  In Proc. of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), pages 226-244, 2005.
  
  
• Julia Chuzhoy and Sanjeev Khanna.
  New Hardness Results for Undirected Edge-Disjoint Paths.
  Manuscript, 2005.
  
  
• Mihai Badoiu, Julia Chuzhoy, Piotr Indyk and Anastasios Sidiropoulos.
  Low-Distortion Embeddings of General Metrics into the Line.
  In Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 225-233, 2005.
  Full version containing all the proofs.
  
  
• Julia Chuzhoy, Anupam Gupta, Joseph (Seffi) Naor and Amitabh Sinha.
  On the Approximability of Some Network Design Problems.
  ACM Transactions on Algorithms (TALG) (special issue of SODA 2005), Volume 4(2), 2008.
  Preliminary version appeared in Proc. of SODA 2005, pages 943-951.
  
  
• Julia Chuzhoy and Yuval Rabani.
  Approximating k-median with non-uniform capacities.
  In Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 952-958, 2005.
  
  
• Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna and Joseph (Seffi) Naor.
  Machine Minimization for Scheduling Jobs with Interval Constraints.
  In Proc. of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 81-90, 2004.
  
  
• Julia Chuzhoy and Joseph (Seffi) Naor.
  The Hardness of Metric Labeling.
  SIAM Journal on Computing, Volume 36 (5), pages 1376-1386, 2007.
  Preliminary version appeared in Proc. of FOCS 2004, pages 108-114.
  
  
• Julia Chuzhoy and Joseph (Seffi) Naor.
  New hardness results for congestion minimization and machine scheduling.
  Journal of the ACM, Volume 53 (50), pages 707-721, 2006.
  Preliminary version appeared in Proc. of STOC 2004, pages 28-34.
  
  
• Julia Chuzhoy, Sudipto Guha, Eran Halperin, Guy Kortsarz, Sanjeev Khanna, Robert Krauthgamer and Joseph (Seffi) Naor.
  Asymmetric k-center is log*n-hard to Approximate.
  Journal of the ACM, Volume 52, Issue 4, pages 538-551, 2005.
  Preliminary version appeared in Proc. of STOC 2004, pages 21-27.
  
  
• Randeep Bhatia, Julia Chuzhoy, Ari Freund and Joseph (Seffi) Naor.
  Algorithmic Aspects of Bandwidth Trading.
  In Proc. of the 30th International Colloquium on Automata, Languages, and Programming (ICALP), 2003.
  Lecture Notes in Computer Science 2719, pages. 751-766, Springer-Verlag, 2003.
  
  
• Julia Chuzhoy and Joseph (Seffi) Naor.
  Covering Problems with Hard Capacities.
  SIAM Journal on Computing, Volume 36 (2), pages 498-515, 2006.
  Preliminary version appeared in Proc. of FOCS 2002, pages 481-481.
  
  
• Julia Chuzhoy, Rafail Ostrovsky and Yuval Rabani.
  Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.
  Mathematics of Operations Research, Volume 31 (4), pages 730-738, 2006.
  Preliminary version appeared in Proc. of FOCS 2001, pages 348-356.
  
  
• My Master's thesis contains improved algorithms for Metric Labeling when the number of labels is small.

back to my homepage