Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
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 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 38:1-38:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chuzhoy_et_al:LIPIcs.ITCS.2023.38, author = {Chuzhoy, Julia and Dalirrooyfard, Mina and Grinberg, Vadim and Tan, Zihan}, title = {{A New Conjecture on Hardness of 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {38:1--38:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.38}, URN = {urn:nbn:de:0030-drops-175411}, doi = {10.4230/LIPIcs.ITCS.2023.38}, annote = {Keywords: Hardness of Approximation, Densest k-Subgraph} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 20:1-20:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bernstein_et_al:LIPIcs.ICALP.2022.20, author = {Bernstein, Aaron and van den Brand, Jan and Probst Gutenberg, Maximilian and Nanongkai, Danupon and Saranurak, Thatchaphol and Sidford, Aaron and Sun, He}, title = {{Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {20:1--20:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.20}, URN = {urn:nbn:de:0030-drops-163611}, doi = {10.4230/LIPIcs.ICALP.2022.20}, annote = {Keywords: dynamic graph algorithm, adaptive adversary, spanner, sparsifier} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak. Pinning down the Strong Wilber 1 Bound for Binary Search Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 33:1-33:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chalermsook_et_al:LIPIcs.APPROX/RANDOM.2020.33, author = {Chalermsook, Parinya and Chuzhoy, Julia and Saranurak, Thatchaphol}, title = {{Pinning down the Strong Wilber 1 Bound for Binary Search Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {33:1--33:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.33}, URN = {urn:nbn:de:0030-drops-126368}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.33}, annote = {Keywords: Binary search trees, Dynamic optimality, Wilber bounds} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Julia Chuzhoy, Merav Parter, and Zihan Tan. On Packing Low-Diameter Spanning Trees. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 33:1-33:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chuzhoy_et_al:LIPIcs.ICALP.2020.33, author = {Chuzhoy, Julia and Parter, Merav and Tan, Zihan}, title = {{On Packing Low-Diameter Spanning Trees}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {33:1--33:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.33}, URN = {urn:nbn:de:0030-drops-124405}, doi = {10.4230/LIPIcs.ICALP.2020.33}, annote = {Keywords: Spanning tree, packing, edge-connectivity} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 38:1-38:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chuzhoy_et_al:LIPIcs.ICALP.2018.38, author = {Chuzhoy, Julia and Kim, David H. K. and Nimavat, Rachit}, title = {{Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {38:1--38:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.38}, URN = {urn:nbn:de:0030-drops-90423}, doi = {10.4230/LIPIcs.ICALP.2018.38}, annote = {Keywords: Node-disjoint paths, approximation algorithms, routing and layout} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Julia Chuzhoy. Excluded Grid Theorem: Improved and Simplified (Invited Talk). In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, p. 31:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{chuzhoy:LIPIcs.SWAT.2016.31, author = {Chuzhoy, Julia}, title = {{Excluded Grid Theorem: Improved and Simplified}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {31:1--31:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.31}, URN = {urn:nbn:de:0030-drops-60546}, doi = {10.4230/LIPIcs.SWAT.2016.31}, annote = {Keywords: Graph Minor Theory, Excluded Grid Theorem, Graph Routing} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Julia Chuzhoy and David H. K. Kim. On Approximating Node-Disjoint Paths in Grids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 187-211, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{chuzhoy_et_al:LIPIcs.APPROX-RANDOM.2015.187, author = {Chuzhoy, Julia and Kim, David H. K.}, title = {{On Approximating Node-Disjoint Paths in Grids}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {187--211}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.187}, URN = {urn:nbn:de:0030-drops-53032}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.187}, annote = {Keywords: Node-disjoint paths, approximation algorithms, routing and layout} }
Feedback for Dagstuhl Publishing