Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Zhao Song, Lichen Zhang, and Ruizhe Zhang. Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 93:1-93:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{song_et_al:LIPIcs.ITCS.2024.93, author = {Song, Zhao and Zhang, Lichen and Zhang, Ruizhe}, title = {{Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {93:1--93:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.93}, URN = {urn:nbn:de:0030-drops-196212}, doi = {10.4230/LIPIcs.ITCS.2024.93}, annote = {Keywords: Deep learning theory, Nonconvex optimization} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang. Distance Queries over Dynamic Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ISAAC.2023.18, author = {Chen, Jingbang and He, Meng and Munro, J. Ian and Peng, Richard and Wu, Kaiyu and Zhang, Daniel J.}, title = {{Distance Queries over Dynamic Interval Graphs}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {18:1--18:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.18}, URN = {urn:nbn:de:0030-drops-193207}, doi = {10.4230/LIPIcs.ISAAC.2023.18}, annote = {Keywords: interval graph, proper interval graph, intersection graph, geometric intersection graph, distance oracle, distance query, shortest path query, dynamic graph} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Ming Ding and Peng Zhang. Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ding_et_al:LIPIcs.ESA.2023.41, author = {Ding, Ming and Zhang, Peng}, title = {{Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {41:1--41:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.41}, URN = {urn:nbn:de:0030-drops-186947}, doi = {10.4230/LIPIcs.ESA.2023.41}, annote = {Keywords: 1-Laplacian Solvers, Simplicial Complexes, Incomplete Nested Dissection} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Daniel A. Spielman and Peng Zhang. Hardness Results for Weaver’s Discrepancy Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{spielman_et_al:LIPIcs.APPROX/RANDOM.2022.40, author = {Spielman, Daniel A. and Zhang, Peng}, title = {{Hardness Results for Weaver’s Discrepancy Problem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {40:1--40:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.40}, URN = {urn:nbn:de:0030-drops-171628}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.40}, annote = {Keywords: Discrepancy Problem, Kadison-Singer Problem, Hardness of Approximation} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Han Jiang, Shang-En Huang, Thatchaphol Saranurak, and Tian Zhang. Vertex Sparsifiers for Hyperedge Connectivity. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{jiang_et_al:LIPIcs.ESA.2022.70, author = {Jiang, Han and Huang, Shang-En and Saranurak, Thatchaphol and Zhang, Tian}, title = {{Vertex Sparsifiers for Hyperedge Connectivity}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {70:1--70:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.70}, URN = {urn:nbn:de:0030-drops-170081}, doi = {10.4230/LIPIcs.ESA.2022.70}, annote = {Keywords: Vertex sparsifier, hypergraph, connectivity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, and Peng Zhang. Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 53:1-53:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ding_et_al:LIPIcs.ICALP.2022.53, author = {Ding, Ming and Kyng, Rasmus and Gutenberg, Maximilian Probst and Zhang, Peng}, title = {{Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {53:1--53:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.53}, URN = {urn:nbn:de:0030-drops-163945}, doi = {10.4230/LIPIcs.ICALP.2022.53}, annote = {Keywords: Simplicial Complexes, Combinatorial Laplacians, Linear Equations, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ming Ding, Rasmus Kyng, and Peng Zhang. Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 54:1-54:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ding_et_al:LIPIcs.ICALP.2022.54, author = {Ding, Ming and Kyng, Rasmus and Zhang, Peng}, title = {{Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {54:1--54:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.54}, URN = {urn:nbn:de:0030-drops-163950}, doi = {10.4230/LIPIcs.ICALP.2022.54}, annote = {Keywords: Two-Commodity Flow Problems, Linear Programming, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (Overparametrized) Neural Networks in Near-Linear Time. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{vandenbrand_et_al:LIPIcs.ITCS.2021.63, author = {van den Brand, Jan and Peng, Binghui and Song, Zhao and Weinstein, Omri}, title = {{Training (Overparametrized) Neural Networks in Near-Linear Time}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {63:1--63:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.63}, URN = {urn:nbn:de:0030-drops-136025}, doi = {10.4230/LIPIcs.ITCS.2021.63}, annote = {Keywords: Deep learning theory, Nonconvex optimization} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Xuangui Huang. Space Hardness of Solving Structured Linear Systems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{huang:LIPIcs.ISAAC.2020.56, author = {Huang, Xuangui}, title = {{Space Hardness of Solving Structured Linear Systems}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {56:1--56:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.56}, URN = {urn:nbn:de:0030-drops-134001}, doi = {10.4230/LIPIcs.ISAAC.2020.56}, annote = {Keywords: linear system solver, logarithmic space, threshold circuit} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Yin Tat Lee. Convex Optimization and Dynamic Data Structure (Invited Talk). In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{lee:LIPIcs.FSTTCS.2020.3, author = {Lee, Yin Tat}, title = {{Convex Optimization and Dynamic Data Structure}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.3}, URN = {urn:nbn:de:0030-drops-132440}, doi = {10.4230/LIPIcs.FSTTCS.2020.3}, annote = {Keywords: Convex Optimization, Dynamic Data Structure} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Wei Chen and Binghui Peng. On Adaptivity Gaps of Influence Maximization Under the Independent Cascade Model with Full-Adoption Feedback. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.ISAAC.2019.24, author = {Chen, Wei and Peng, Binghui}, title = {{On Adaptivity Gaps of Influence Maximization Under the Independent Cascade Model with Full-Adoption Feedback}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {24:1--24:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.24}, URN = {urn:nbn:de:0030-drops-115208}, doi = {10.4230/LIPIcs.ISAAC.2019.24}, annote = {Keywords: Adaptive influence maximization, adaptivity gap, full-adoption feedback} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Yao Xu, Yong Chen, Guohui Lin, Tian Liu, Taibo Luo, and Peng Zhang. A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{xu_et_al:LIPIcs.ISAAC.2017.66, author = {Xu, Yao and Chen, Yong and Lin, Guohui and Liu, Tian and Luo, Taibo and Zhang, Peng}, title = {{A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {66:1--66:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.66}, URN = {urn:nbn:de:0030-drops-82120}, doi = {10.4230/LIPIcs.ISAAC.2017.66}, annote = {Keywords: Approximation algorithm, duo-preservation string mapping, string partition, independent set} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang. Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{mahoney_et_al:LIPIcs.ICALP.2016.52, author = {Mahoney, Michael W. and Rao, Satish and Wang, Di and Zhang, Peng}, title = {{Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^\{-3\}) Time}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {52:1--52:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.52}, URN = {urn:nbn:de:0030-drops-63335}, doi = {10.4230/LIPIcs.ICALP.2016.52}, annote = {Keywords: Mixed packing and covering, Linear program, Approximation algorithm, Parallel algorithm} }
Feedback for Dagstuhl Publishing