Julia Chuzhoy

127 papers A* 54A 1Journal 60Unranked 8
YearRankTypeTitle / Venue / Authors
2026 A* conf
Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs.
SODA
Julia Chuzhoy, Ron Mosenzon, Ohad Trabelsi
2026 J jnl
Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition.
CoRR
Julia Chuzhoy, Merav Parter
2025 A* conf
Breaking the O(m
STOC
Julia Chuzhoy, Ohad Trabelsi
2025 J jnl
Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut.
CoRR
Julia Chuzhoy, Ohad Trabelsi
2025 J jnl
Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs.
CoRR
Julia Chuzhoy, Ron Mosenzon, Ohad Trabelsi
2025 A* conf
Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition.
SODA
Julia Chuzhoy, Merav Parter
2024 A* conf
A Faster Combinatorial Algorithm for Maximum Bipartite Matching.
SODA
Julia Chuzhoy, Sanjeev Khanna
2024 A* conf
Maximum Bipartite Matching in n
STOC
Julia Chuzhoy, Sanjeev Khanna
2024 J jnl
Maximum Bipartite Matching in n
CoRR
Julia Chuzhoy, Sanjeev Khanna
2023 A* conf
A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems.
SODA
Julia Chuzhoy
2023 J jnl
A Faster Combinatorial Algorithm for Maximum Bipartite Matching.
CoRR
Julia Chuzhoy, Sanjeev Khanna
2023 A conf
A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems.
ITCS
Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, Zihan Tan
2023 A* conf
A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths.
STOC
Julia Chuzhoy, Ruimin Zhang
2023 J jnl
A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths.
CoRR
Julia Chuzhoy, Ruimin Zhang
2023 J jnl
Pinning Down the Strong Wilber-1 Bound for Binary Search Trees.
Theory Comput.
Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak
2022 J jnl
A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems.
CoRR
Julia Chuzhoy
2022 J jnl
A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems.
CoRR
Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, Zihan Tan
2022 J jnl
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs.
CoRR
Julia Chuzhoy, Zihan Tan
2022 A* conf
A subpolynomial approximation algorithm for graph crossing number in low-degree graphs.
STOC
Julia Chuzhoy, Zihan Tan
2022 J jnl
New Hardness Results for Routing on Disjoint Paths.
SIAM J. Comput.
Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
2021 J jnl
Almost Polynomial Hardness of Node-Disjoint Paths in Grids.
Theory Comput.
Julia Chuzhoy, David Hong Kyun Kim, Rachit Nimavat
2021 J jnl
Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time.
CoRR
Julia Chuzhoy
2021 A* conf
Decremental all-pairs shortest paths in deterministic near-linear time.
STOC
Julia Chuzhoy
2021 A* conf
Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition.
SODA
Julia Chuzhoy, Thatchaphol Saranurak
2021 J jnl
Towards tight(er) bounds for the Excluded Grid Theorem.
J. Comb. Theory B
Julia Chuzhoy, Zihan Tan
2020 A* conf
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.
FOCS
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak
2020 J jnl
Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition.
CoRR
Julia Chuzhoy, Thatchaphol Saranurak
2020 A* conf
On Packing Low-Diameter Spanning Trees.
ICALP
Julia Chuzhoy, Merav Parter, Zihan Tan
2020 J jnl
On Packing Low-Diameter Spanning Trees.
CoRR
Julia Chuzhoy, Merav Parter, Zihan Tan
2020 — conf
Pinning down the Strong Wilber 1 Bound for Binary Search Trees.
APPROX-RANDOM
Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak
2020 A* ed.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020
STOC
Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
2020 A* conf
Towards Better Approximation of Graph Crossing Number.
FOCS
Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan
2020 J jnl
Towards Better Approximation of Graph Crossing Number.
CoRR
Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan
2019 J jnl
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.
CoRR
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak
2019 J jnl
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems.
CoRR
Julia Chuzhoy, Sanjeev Khanna
2019 A* conf
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems.
STOC
Julia Chuzhoy, Sanjeev Khanna
2019 J jnl
Large Minors in Expanders.
CoRR
Julia Chuzhoy, Rachit Nimavat
2019 J jnl
Pinning Down the Strong Wilber 1 Bound for Binary Search Trees.
CoRR
Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak
2019 A* conf
Towards Tight(er) Bounds for the Excluded Grid Theorem.
SODA
Julia Chuzhoy, Zihan Tan
2019 J jnl
Towards Tight(er) Bounds for the Excluded Grid Theorem.
CoRR
Julia Chuzhoy, Zihan Tan
2018 A* conf
Almost polynomial hardness of node-disjoint paths in grids.
STOC
Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
2018 A* conf
Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary.
ICALP
Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
2018 J jnl
Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary.
CoRR
Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
2017 J jnl
Almost Polynomial Hardness of Node-Disjoint Paths in Grids.
CoRR
Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
2017 A* conf
New hardness results for routing on disjoint paths.
STOC
Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
2017 J jnl
Special Section on the Fifty-Fifth Annual ACM Symposium on Foundations of Coomputer Science (FOCS 2014).
SIAM J. Comput.
Julia Chuzhoy, Alexander Russell
2016 J jnl
A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2.
J. ACM
Julia Chuzhoy, Shi Li
2016 J jnl
Approximation Algorithms and Hardness of the
ACM Trans. Algorithms
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
2016 — conf
Excluded Grid Theorem: Improved and Simplified (Invited Talk).
SWAT
Julia Chuzhoy
2016 — ch.
Generalized Steiner Network.
Encyclopedia of Algorithms
Julia Chuzhoy
2016 J jnl
Improved Approximation for Node-Disjoint Paths in Planar Graphs.
CoRR
Julia Chuzhoy, David H. K. Kim, Shi Li
2016 J jnl
Improved Bounds for the Excluded Grid Theorem.
CoRR
Julia Chuzhoy
2016 A* conf
Improved approximation for node-disjoint paths in planar graphs.
STOC
Julia Chuzhoy, David H. K. Kim, Shi Li
2016 — ch.
Large-Treewidth Graph Decompositions.
Encyclopedia of Algorithms
Julia Chuzhoy
2016 J jnl
New Hardness Results for Routing on Disjoint Paths.
CoRR
Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
2016 A* conf
On Approximating Maximum Independent Set of Rectangles.
FOCS
Julia Chuzhoy, Alina Ene
2016 J jnl
On Approximating Maximum Independent Set of Rectangles.
CoRR
Julia Chuzhoy, Alina Ene
2016 J jnl
Polynomial Bounds for the Grid-Minor Theorem.
J. ACM
Chandra Chekuri, Julia Chuzhoy
2016 J jnl
Routing in Undirected Graphs with Constant Congestion.
SIAM J. Comput.
Julia Chuzhoy
2015 A* conf
Degree-3 Treewidth Sparsifiers.
SODA
Chandra Chekuri, Julia Chuzhoy
2015 A* conf
Excluded Grid Theorem: Improved and Simplified.
STOC
Julia Chuzhoy
2015 A* conf
Improved Bounds for the Flat Wall Theorem.
SODA
Julia Chuzhoy
2015 — conf
On Approximating Node-Disjoint Paths in Grids.
APPROX-RANDOM
Julia Chuzhoy, David H. K. Kim
2014 J jnl
Degree-3 Treewidth Sparsifiers.
CoRR
Chandra Chekuri, Julia Chuzhoy
2014 J jnl
Improved Bounds for the Flat Wall Theorem.
CoRR
Julia Chuzhoy
2014 A* conf
Polynomial bounds for the grid-minor theorem.
STOC
Chandra Chekuri, Julia Chuzhoy
2013 J jnl
Approximation Algorithms for the Directed
Algorithmica
MohammadHossein Bateni, Julia Chuzhoy
2013 J jnl
Large-Treewidth Graph Decompositions and Applications
CoRR
Chandra Chekuri, Julia Chuzhoy
2013 A* conf
Large-treewidth graph decompositions and applications.
STOC
Chandra Chekuri, Julia Chuzhoy
2013 J jnl
Polynomial Bounds for the Grid-Minor Theorem
CoRR
Chandra Chekuri, Julia Chuzhoy
2012 J jnl
A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
CoRR
Julia Chuzhoy, Shi Li
2012 A* conf
A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2.
FOCS
Julia Chuzhoy, Shi Li
2012 J jnl
An O(k
Theory Comput.
Julia Chuzhoy, Sanjeev Khanna
2012 A* conf
Approximation algorithms and hardness of integral concurrent flow.
STOC
Parinya Chalermsook, Julia Chuzhoy, Alina Ene, Shi Li
2012 A* conf
Approximation algorithms and hardness of the
SODA
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
2012 — conf
Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply.
APPROX-RANDOM
Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, Sanjeev Khanna
2012 J jnl
On Vertex Sparsifiers with Steiner Nodes
CoRR
Julia Chuzhoy
2012 A* conf
On vertex sparsifiers with Steiner nodes.
STOC
Julia Chuzhoy
2012 A* conf
Routing in undirected graphs with constant congestion.
STOC
Julia Chuzhoy
2011 A* conf
An algorithm for the graph crossing number problem.
STOC
Julia Chuzhoy
2011 J jnl
Approximation Algorithms and Hardness of the k-Route Cut Problem
CoRR
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
2011 A* conf
On Graph Crossing Number and Edge Planarization.
SODA
Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos
2011 J jnl
Routing in Undirected Graphs with Constant Congestion
CoRR
Julia Chuzhoy
2010 J jnl
An Algorithm for the Graph Crossing Number Problem
CoRR
Julia Chuzhoy
2010 — conf
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems.
APPROX-RANDOM
MohammadHossein Bateni, Julia Chuzhoy
2010 J jnl
Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs.
Comb.
Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang
2010 J jnl
On Graph Crossing Number and Edge Planarization
CoRR
Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos
2010 A* conf
Resource Minimization for Fire Containment.
SODA
Parinya Chalermsook, Julia Chuzhoy
2009 A* conf
An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.
FOCS
Julia Chuzhoy, Sanjeev Khanna
2009 — conf
Erratum: Resource Minimization Job Scheduling.
APPROX-RANDOM
Julia Chuzhoy, Paolo Codenotti
2009 A* conf
Maximum independent set of rectangles.
SODA
Parinya Chalermsook, Julia Chuzhoy
2009 J jnl
On Allocating Goods to Maximize Fairness
CoRR
Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna
2009 A* conf
On Allocating Goods to Maximize Fairness.
FOCS
Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna
2009 J jnl
Polynomial flow-cut gaps and hardness of directed cut problems.
J. ACM
Julia Chuzhoy, Sanjeev Khanna
2009 — conf
Resource Minimization Job Scheduling.
APPROX-RANDOM
Julia Chuzhoy, Paolo Codenotti
2008 A* conf
Algorithms for Single-Source Vertex Connectivity.
FOCS
Julia Chuzhoy, Sanjeev Khanna
2008 J jnl
An O(k
CoRR
Julia Chuzhoy, Sanjeev Khanna
2008 — ch.
Generalized Steiner Network.
Encyclopedia of Algorithms
Julia Chuzhoy
2008 A* conf
Network design for vertex connectivity.
STOC
Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna
2008 J jnl
On the approximability of some network design problems.
ACM Trans. Algorithms
Julia Chuzhoy, Anupam Gupta, Joseph Naor, Amitabh Sinha
2007 J jnl
Algorithmic aspects of bandwidth trading.
ACM Trans. Algorithms
Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor
2007 A* conf
Hardness of routing with congestion in directed graphs.
STOC
Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar
2007 J jnl
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs.
Electron. Colloquium Comput. Complex.
Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang
2007 J jnl
Non-Cooperative Multicast and Facility Location Games.
IEEE J. Sel. Areas Commun.
Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph Naor, Ariel Orda
2007 A* conf
Polynomial flow-cut gaps and hardness of directed cut problems.
STOC
Julia Chuzhoy, Sanjeev Khanna
2007 J jnl
The Hardness of Metric Labeling.
SIAM J. Comput.
Julia Chuzhoy, Joseph Naor
2006 J jnl
Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.
Math. Oper. Res.
Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani
2006 J jnl
Covering Problems with Hard Capacities.
SIAM J. Comput.
Julia Chuzhoy, Joseph Naor
2006 — conf
Embedding ultrametrics into low-dimensional spaces.
SCG
Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos
2006 J jnl
Hardness of Directed Routing with Congestion.
Electron. Colloquium Comput. Complex.
Julia Chuzhoy, Sanjeev Khanna
2006 A* conf
Hardness of cut problems in directed graphs.
STOC
Julia Chuzhoy, Sanjeev Khanna
2006 J jnl
New hardness results for congestion minimization and machine scheduling.
J. ACM
Julia Chuzhoy, Joseph Naor
2006 A* conf
Non-cooperative multicast and facility location games.
EC
Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph Naor, Ariel Orda
2005 A* conf
Approximating k-median with non-uniform capacities.
SODA
Julia Chuzhoy, Yuval Rabani
2005 J jnl
Asymmetric
J. ACM
Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor
2005 A* conf
Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.
FOCS
Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang
2005 A* conf
Low-distortion embeddings of general metrics into the line.
STOC
Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos
2005 A* conf
On the approximability of some network design problems.
SODA
Julia Chuzhoy, Anupam Gupta, Joseph Naor, Amitabh Sinha
2004 A* conf
Asymmetric k-center is log
STOC
Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor
2004 — —
Hardness approximation and new approximability classes.
Julia Chuzhoy
2004 A* conf
Machine Minimization for Scheduling Jobs with Interval Constraints.
FOCS
Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor
2004 A* conf
New hardness results for congestion minimization and machine scheduling.
STOC
Julia Chuzhoy, Joseph Naor
2004 A* conf
The Hardness of Metric Labeling.
FOCS
Julia Chuzhoy, Joseph Naor
2003 A* conf
Algorithmic Aspects of Bandwidth Trading.
ICALP
Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor
2003 J jnl
Asymmetric k-center is log
Electron. Colloquium Comput. Complex.
Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor
2002 A* conf
Covering Problems with Hard Capacities.
FOCS
Julia Chuzhoy, Joseph Naor
2001 A* conf
Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.
FOCS
Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani