Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Karthekeyan Chandrasekaran, Chandra Chekuri, Manuel R. Torres, and Weihao Zhu. On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chandrasekaran_et_al:LIPIcs.APPROX/RANDOM.2024.9, author = {Chandrasekaran, Karthekeyan and Chekuri, Chandra and Torres, Manuel R. and Zhu, Weihao}, title = {{On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {9:1--9:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.9}, URN = {urn:nbn:de:0030-drops-210025}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.9}, annote = {Keywords: Densest subgraph problem, Hardness of approximation, Approximation algorithms} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, and Evelyn Warton. Matrix Multiplication Verification Using Coding Theory. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bennett_et_al:LIPIcs.APPROX/RANDOM.2024.42, author = {Bennett, Huck and Gajulapalli, Karthik and Golovnev, Alexander and Warton, Evelyn}, title = {{Matrix Multiplication Verification Using Coding Theory}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {42:1--42:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.42}, URN = {urn:nbn:de:0030-drops-210352}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.42}, annote = {Keywords: Matrix Multiplication Verification, Derandomization, Sparse Matrices, Error-Correcting Codes, Hardness Barriers, Reductions} }
Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Clemens Heuberger, Daniel Krenn, and Tobias Lechner. Analysis of Regular Sequences: Summatory Functions and Divide-And-Conquer Recurrences. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{heuberger_et_al:LIPIcs.AofA.2024.24, author = {Heuberger, Clemens and Krenn, Daniel and Lechner, Tobias}, title = {{Analysis of Regular Sequences: Summatory Functions and Divide-And-Conquer Recurrences}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.24}, URN = {urn:nbn:de:0030-drops-204597}, doi = {10.4230/LIPIcs.AofA.2024.24}, annote = {Keywords: Regular sequence, Divide-and-Conquer Recurrence, Summatory Function, Asymptotic Analysis} }
Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
James Allen Fill, Daniel Q. Naiman, and Ao Sun. Sharpened Localization of the Trailing Point of the Pareto Record Frontier. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fill_et_al:LIPIcs.AofA.2024.28, author = {Fill, James Allen and Naiman, Daniel Q. and Sun, Ao}, title = {{Sharpened Localization of the Trailing Point of the Pareto Record Frontier}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {28:1--28:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.28}, URN = {urn:nbn:de:0030-drops-204631}, doi = {10.4230/LIPIcs.AofA.2024.28}, annote = {Keywords: Multivariate records, Pareto records, generators, interior generators, minima, maxima, record-setting region, frontier, current records, boundary-crossing probabilities, first moment method, second moment method, orthants} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7, author = {Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik}, title = {{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.7}, URN = {urn:nbn:de:0030-drops-204035}, doi = {10.4230/LIPIcs.CCC.2024.7}, annote = {Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Meng-Tsung Tsai, Shi-Chun Tsai, and Tsung-Ta Wu. Dependent k-Set Packing on Polynomoids. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 84:1-84:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{tsai_et_al:LIPIcs.MFCS.2023.84, author = {Tsai, Meng-Tsung and Tsai, Shi-Chun and Wu, Tsung-Ta}, title = {{Dependent k-Set Packing on Polynomoids}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {84:1--84:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.84}, URN = {urn:nbn:de:0030-drops-186180}, doi = {10.4230/LIPIcs.MFCS.2023.84}, annote = {Keywords: Hereditary Systems, Hypergraph Matchings, Compleixty Trichotomy} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Yi-Jun Chang, Martín Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai. Streaming Complexity of Spanning Tree Computation. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chang_et_al:LIPIcs.STACS.2020.34, author = {Chang, Yi-Jun and Farach-Colton, Mart{\'\i}n and Hsu, Tsan-Sheng and Tsai, Meng-Tsung}, title = {{Streaming Complexity of Spanning Tree Computation}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {34:1--34:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.34}, URN = {urn:nbn:de:0030-drops-118951}, doi = {10.4230/LIPIcs.STACS.2020.34}, annote = {Keywords: Max-Leaf Spanning Trees, BFS Trees, DFS Trees} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Eric Allender, Martín Farach-Colton, and Meng-Tsung Tsai. Syntactic Separation of Subset Satisfiability Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{allender_et_al:LIPIcs.APPROX-RANDOM.2019.16, author = {Allender, Eric and Farach-Colton, Mart{\'\i}n and Tsai, Meng-Tsung}, title = {{Syntactic Separation of Subset Satisfiability Problems}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {16:1--16:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.16}, URN = {urn:nbn:de:0030-drops-112319}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.16}, annote = {Keywords: Syntactic Class, Exponential Time Hypothesis, APX, PTAS} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Yen-Ting Chen, Meng-Tsung Tsai, and Shi-Chun Tsai. A Dichotomy Result for Cyclic-Order Traversing Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chen_et_al:LIPIcs.ISAAC.2018.29, author = {Chen, Yen-Ting and Tsai, Meng-Tsung and Tsai, Shi-Chun}, title = {{A Dichotomy Result for Cyclic-Order Traversing Games}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {29:1--29:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.29}, URN = {urn:nbn:de:0030-drops-99775}, doi = {10.4230/LIPIcs.ISAAC.2018.29}, annote = {Keywords: st-planar graphs, biconnectivity, fault-tolerant routing algorithms, software defined network} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Martín Farach-Colton, Meng Li, and Meng-Tsung Tsai. Streaming Algorithms for Planar Convex Hulls. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{farachcolton_et_al:LIPIcs.ISAAC.2018.47, author = {Farach-Colton, Mart{\'\i}n and Li, Meng and Tsai, Meng-Tsung}, title = {{Streaming Algorithms for Planar Convex Hulls}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {47:1--47:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.47}, URN = {urn:nbn:de:0030-drops-99951}, doi = {10.4230/LIPIcs.ISAAC.2018.47}, annote = {Keywords: Convex Hulls, Streaming Algorithms, Lower Bounds} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Travis Gagie, Meng He, and Gonzalo Navarro. Tree Path Majority Data Structures. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 68:1-68:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gagie_et_al:LIPIcs.ISAAC.2018.68, author = {Gagie, Travis and He, Meng and Navarro, Gonzalo}, title = {{Tree Path Majority Data Structures}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {68:1--68:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.68}, URN = {urn:nbn:de:0030-drops-100166}, doi = {10.4230/LIPIcs.ISAAC.2018.68}, annote = {Keywords: Majorities on Trees, Succinct data structures} }
Feedback for Dagstuhl Publishing