Julia Chuzhoy's Publications
Julia Chuzhoy's publications
The papers appear in the reverse chronological order of the original (usually conference) publication.
 Julia Chuzhoy and Ruimin Zhang.
A New Deterministic Algorithm for Fully Dynamic AllPairs Shortest Paths.
In Proceedings of the 55th Annual (ACM) Symposium on Theory of Computing,
(STOC), pages 11591172, 2023.
A full version, arxiv.2304.09321.
 Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg and Zihan Tan.
A New Conjecture on Hardness of 2CSP's with Implications to Hardness of Densest kSubgraph and Other Problems.
In 14th Innovations in Theoretical Computer Science Conference, (ITCS)}
LIPIcs volue 251, pages 38:138: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 ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 21222213, 2023.
A full version, arxiv.2211.10556.
 Julia Chuzhoy and Zihan Tan.
A Subpolynomial Approximation Algorithm for Graph Crossing Number in LowDegree Graphs.
In Proc. 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 303316, 2022.
A full version, arxiv.2202.06827.
A video of an informal talk at Research at TTIC series.

Julia Chuzhoy.
Decremental AllPairs Shortest Paths in Deterministic NearLinear
Time.
In Proc. 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 626639, 2021.
A full version, arxiv.2109.05621.

Julia Chuzhoy and Thatchaphol Saranurak.
Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition.
In Proc. ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 24782496, 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. 7384, 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. 11581167, 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:133: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 LowDiameter 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 SingleSource Shortest Paths with Applications to VertexCapacitated Flow and Cut Problems.
In Proc. of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 389400, 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. 219265, 2021.
A preliminary version appeared in Proc. of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, (SODA), pages 14451464, 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 NodeDisjoint Paths in Grids with Sources on the Boundary
.
In Proc. of the 45th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 38:138:14, 2018.
A full version, arXiv:1805.09956.
 Julia Chuzhoy, David H.K. Kim and Rachit Nimavat.
Almost Polynomial Hardness for NodeDisjoint Paths in Grids.
Theory of Computing, volume 17, pages 157, 2021.
A preliminary version appeared
in Proc. of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 12201233, 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 17189, 2022.
A preliminary version appeared
in Proc. of the 49th Annual ACM SIGACT Symposium on Theory of Computing, (STOC), pages 8699, 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 820829, 2016.
A full version, arXiv:1608.00271.
 Julia Chuzhoy, David H.K. Kim and Shi Li.
Improved Approximation for NodeDisjoint Paths in Planar Graphs.
In Proc. of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 556569, 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 645654, 2015.
For a full version, see this paper.
 Julia Chuzhoy and David H.K. Kim.
On Approximating NodeDisjoint Paths in Grids.
In Proc. of APPROX 2015, LIPIcsLeibniz International Proceedings in Informatics (Vol. 40).
 Chandra Chekuri and Julia Chuzhoy.
Degree3 Treewdith Sparsifiers.
In Proc. of the 26th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), pages 242255, 2015.
A full version, arxiv:1410.1016
 Julia Chuzhoy.
Improved Bounds for the Flat Wall Theorem.
In Proc. of the 26th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), pages 256275, 2015.
A full version, arxiv:1410.9276
 Chandra Chekuri and Julia Chuzhoy.
Polynomial Bounds for the GridMinor 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 6069, 2014.
 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 585607, 2014.
 Chandra Chekuri and Julia Chuzhoy.
LargeTreewidth Graph Decompositions and Applications.
In Proc. of the 45th Annual ACM Symposium on Theory of Computing (STOC),
pages 291300, 2013.
A full version, arXiv:1304.1577.
 Julia Chuzhoy and Shi Li.
A Polylogarithmic Approximation Algorithm for EdgeDisjoint 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 233242, 2012.
A cowinner 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 7384, 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 689708, 2012.
A full version
 Julia Chuzhoy.
On Vertex Sparsifiers with Steiner Nodes.
In Proc. of the 44th Symposium on Theory of Computing (STOC), pages 673688, 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 14901532, 2016.
A preliminary version appeared in Proc. of the 44th Symposium on Theory of Computing (STOC), pages 855874, 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 kroute 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 TwentyThird Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 780799, 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 303312, 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 TwentySecond Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 10501069, 2011.
A full version.
 MohammadHossein Bateni and Julia Chuzhoy.
Approximation Algorithms for the Directed kTour and kStroll Problems.
Algorithmica 75(3), pages 545561, 2013.
A preliminary version appeared in Proc. of APPROX 2010, Lecture Notes in Computer Science 6302, pages 2538, 2010.
 Parinya Chalermsook and Julia Chuzhoy.
Resource Minimization for Fire Containment.
In Proceedings of the TwentyFirst Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 13341349, 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 107116, 2009.
 Julia Chuzhoy and Sanjeev Khanna.
An O(k^3log n)Approximation Algorithm for VertexConnectivity Survivable Network Design.
Theory of Computing, Volume 8, pp. 401413, 2012.
A preliminary version in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
pages 437441, 2009.
 Julia Chuzhoy and Paolo Codenotti.
Resource Minimization Job Scheduling [Erratum].
In Proceedings of APPROX 2009, Lecture Notes in Computer Science 5687, pages 7083, 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 892901, 2009.
A more detailed version
 Julia Chuzhoy and Sanjeev Khanna.
Algorithms for SingleSource VertexConnectivity.
In Proc. of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 105114, 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 FlowCut 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 165178, 2007.
 Julia Chuzhoy and Sanjeev Khanna.
Hardness of Directed Routing with Congestion.
ECCC technical report TR06109, 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 527536, 2006.
Notice: the APXhardness 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 LowDimensional Spaces.
In Proc. of the 22nd ACM Symposium on Computational Geometry (SOCG),
pages 187196, 2006.
 Chandra Chekuri, Julia Chuzhoy, Liane LewinEytan, Seffi Naor and
Ariel Orda.
Noncooperative multicast and facility location games.
IEEE Journal on Selected Areas in Communication (Special Issue on NonCooperative Behavior in Networking),
vol. 25, no. 6, pp.
11931206, 2007. (Invited paper.)
Preliminary version appeared in
Proc. of the 7th ACM Conference on Electronic Commerce (EC), pages
7281, 2006
 Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna and Lisa Zhang.
Hardness of the Undirected
EdgeDisjoint Paths Problem with Congestion.
In Proc. of the 46th IEEE Symposium on Foundations of Computer Science
(FOCS), pages 226244, 2005.

Julia Chuzhoy and Sanjeev Khanna.
New Hardness Results for Undirected EdgeDisjoint Paths.
Manuscript, 2005.
 Mihai Badoiu, Julia Chuzhoy, Piotr Indyk and Anastasios Sidiropoulos.
LowDistortion
Embeddings of General Metrics into the Line.
In Proc. of the 37th Annual ACM Symposium on Theory of Computing
(STOC), pages 225233, 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 943951.
 Julia Chuzhoy and Yuval Rabani.
Approximating kmedian with nonuniform capacities.
In Proc. of the 16th Annual ACMSIAM Symposium on Discrete Algorithms
(SODA), pages 952958, 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
8190, 2004.
 Julia Chuzhoy and Joseph (Seffi) Naor.
The Hardness of Metric Labeling.
SIAM Journal on Computing, Volume 36
(5), pages 13761386, 2007.
Preliminary version appeared in
Proc. of FOCS 2004, pages
108114.
 Julia Chuzhoy and Joseph (Seffi) Naor.
New hardness results for congestion minimization and machine scheduling.
Journal of the ACM, Volume 53 (50), pages 707721, 2006.
Preliminary version appeared in
Proc. of STOC 2004, pages 2834.
 Julia Chuzhoy, Sudipto Guha, Eran Halperin, Guy Kortsarz, Sanjeev Khanna, Robert Krauthgamer
and Joseph (Seffi) Naor.
Asymmetric kcenter is log*nhard to Approximate.
Journal of the ACM, Volume 52, Issue 4, pages 538551, 2005.
Preliminary version appeared in Proc. of STOC 2004, pages 2127.
 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. 751766,
SpringerVerlag, 2003.
 Julia Chuzhoy and Joseph (Seffi) Naor.
Covering Problems with Hard Capacities.
SIAM Journal on Computing, Volume 36 (2),
pages 498515, 2006.
Preliminary version appeared in
Proc. of FOCS 2002, pages 481481.

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 730738, 2006.
Preliminary version appeared in
Proc. of FOCS 2001, pages 348356.
 My Master's thesis contains improved algorithms for Metric Labeling when the number of labels is small.
back to my homepage