OASIcs, Volume 80
Fog-IoT 2020, April 21, 2020, Sydney, Australia
Editors: Anton Cervin and Yang Yang
Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Sudeepa Roy, Amir Gilad, Yihao Hu, Hanze Meng, Zhengjie Miao, Kristin Stephens-Martinez, and Jun Yang. How Database Theory Helps Teach Relational Queries in Database Education (Invited Talk). In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{roy_et_al:LIPIcs.ICDT.2024.2, author = {Roy, Sudeepa and Gilad, Amir and Hu, Yihao and Meng, Hanze and Miao, Zhengjie and Stephens-Martinez, Kristin and Yang, Jun}, title = {{How Database Theory Helps Teach Relational Queries in Database Education}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {2:1--2:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.2}, URN = {urn:nbn:de:0030-drops-197841}, doi = {10.4230/LIPIcs.ICDT.2024.2}, annote = {Keywords: Query Debugging, SQL, Relational Algebra, Relational Calculus, Database Education, Boolean Provenance} }
Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Zhewei Wei, Ji-Rong Wen, and Mingji Yang. Approximating Single-Source Personalized PageRank with Absolute Error Guarantees. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{wei_et_al:LIPIcs.ICDT.2024.9, author = {Wei, Zhewei and Wen, Ji-Rong and Yang, Mingji}, title = {{Approximating Single-Source Personalized PageRank with Absolute Error Guarantees}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {9:1--9:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.9}, URN = {urn:nbn:de:0030-drops-197911}, doi = {10.4230/LIPIcs.ICDT.2024.9}, annote = {Keywords: Graph Algorithms, Sublinear Algorithms, Personalized PageRank} }
Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Pankaj K. Agarwal, Rahul Raychaudhury, Stavros Sintos, and Jun Yang. Computing Data Distribution from Query Selectivities. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{agarwal_et_al:LIPIcs.ICDT.2024.18, author = {Agarwal, Pankaj K. and Raychaudhury, Rahul and Sintos, Stavros and Yang, Jun}, title = {{Computing Data Distribution from Query Selectivities}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {18:1--18:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.18}, URN = {urn:nbn:de:0030-drops-198007}, doi = {10.4230/LIPIcs.ICDT.2024.18}, annote = {Keywords: selectivity queries, discrete distributions, Multiplicative Weights Update, eps-approximation, learnable functions, depth problem, arrangement} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Jesper Jansson, Wing-Kin Sung, Seyed Ali Tabatabaee, and Yutong Yang. A Faster Algorithm for Constructing the Frequency Difference Consensus Tree. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jansson_et_al:LIPIcs.STACS.2024.43, author = {Jansson, Jesper and Sung, Wing-Kin and Tabatabaee, Seyed Ali and Yang, Yutong}, title = {{A Faster Algorithm for Constructing the Frequency Difference Consensus Tree}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {43:1--43:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.43}, URN = {urn:nbn:de:0030-drops-197539}, doi = {10.4230/LIPIcs.STACS.2024.43}, annote = {Keywords: phylogenetic tree, frequency difference consensus tree, tree algorithm, centroid path decomposition, max-Manhattan Skyline Problem} }
Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Jonathan Sterling, Daniel Gratzer, and Lars Birkedal. Towards Univalent Reference Types: The Impact of Univalence on Denotational Semantics. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 47:1-47:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{sterling_et_al:LIPIcs.CSL.2024.47, author = {Sterling, Jonathan and Gratzer, Daniel and Birkedal, Lars}, title = {{Towards Univalent Reference Types: The Impact of Univalence on Denotational Semantics}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {47:1--47:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.47}, URN = {urn:nbn:de:0030-drops-196901}, doi = {10.4230/LIPIcs.CSL.2024.47}, annote = {Keywords: univalent foundations, homotopy type theory, impredicative encodings, synthetic guarded domain theory, guarded recursion, higher-order store, reference types} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Mong-Jen Kao. Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kao:LIPIcs.ISAAC.2023.45, author = {Kao, Mong-Jen}, title = {{Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {45:1--45:14}, 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.45}, URN = {urn:nbn:de:0030-drops-193474}, doi = {10.4230/LIPIcs.ISAAC.2023.45}, annote = {Keywords: Capacitated facility location, Hard capacities, Uniform facility cost} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Ting-Yu Kuo, Yu-Han Chen, Andrea Frosini, Sun-Yuan Hsieh, Shi-Chun Tsai, and Mong-Jen Kao. On Min-Max Graph Balancing with Strict Negative Correlation Constraints. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kuo_et_al:LIPIcs.ISAAC.2023.50, author = {Kuo, Ting-Yu and Chen, Yu-Han and Frosini, Andrea and Hsieh, Sun-Yuan and Tsai, Shi-Chun and Kao, Mong-Jen}, title = {{On Min-Max Graph Balancing with Strict Negative Correlation Constraints}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {50:1--50:15}, 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.50}, URN = {urn:nbn:de:0030-drops-193524}, doi = {10.4230/LIPIcs.ISAAC.2023.50}, annote = {Keywords: Unrelated Scheduling, Graph Balancing, Strict Correlation Constraints} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Enze Sun, Zonghan Yang, and Yuhao Zhang. Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 97:1-97:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{sun_et_al:LIPIcs.ESA.2023.97, author = {Sun, Enze and Yang, Zonghan and Zhang, Yuhao}, title = {{Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {97:1--97:14}, 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.97}, URN = {urn:nbn:de:0030-drops-187500}, doi = {10.4230/LIPIcs.ESA.2023.97}, annote = {Keywords: Online Algorithm, Scheduling, Machine Minimization, Rent Minimization} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Chuhan Yang and Christopher Musco. Efficient Block Approximate Matrix Multiplication. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 103:1-103:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{yang_et_al:LIPIcs.ESA.2023.103, author = {Yang, Chuhan and Musco, Christopher}, title = {{Efficient Block Approximate Matrix Multiplication}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {103:1--103:15}, 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.103}, URN = {urn:nbn:de:0030-drops-187562}, doi = {10.4230/LIPIcs.ESA.2023.103}, annote = {Keywords: Approximate matrix multiplication, randomized numerical linear algebra, trace estimation} }
Published in: LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)
Yunheng Han and Erin K. Molloy. Quartets Enable Statistically Consistent Estimation of Cell Lineage Trees Under an Unbiased Error and Missingness Model (Abstract). In 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 273, pp. 8:1-8:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{han_et_al:LIPIcs.WABI.2023.8, author = {Han, Yunheng and Molloy, Erin K.}, title = {{Quartets Enable Statistically Consistent Estimation of Cell Lineage Trees Under an Unbiased Error and Missingness Model}}, booktitle = {23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)}, pages = {8:1--8:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-294-5}, ISSN = {1868-8969}, year = {2023}, volume = {273}, editor = {Belazzougui, Djamal and Ouangraoua, A\"{i}da}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.8}, URN = {urn:nbn:de:0030-drops-186347}, doi = {10.4230/LIPIcs.WABI.2023.8}, annote = {Keywords: Tumor Phylogenetics, Cell Lineage Trees, Quartets, Supertrees, ASTRAL} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Guozhen Rong, Yongjie Yang, and Wenjun Li. A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 77:1-77:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{rong_et_al:LIPIcs.MFCS.2023.77, author = {Rong, Guozhen and Yang, Yongjie and Li, Wenjun}, title = {{A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {77:1--77: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.77}, URN = {urn:nbn:de:0030-drops-186118}, doi = {10.4230/LIPIcs.MFCS.2023.77}, annote = {Keywords: partial search order, maximum cardinality search, chordal graphs, clique graphs, dynamic programming} }
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-dev.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 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)
Jiong Yang, Arijit Shaw, Teodora Baluta, Mate Soos, and Kuldeep S. Meel. Explaining SAT Solving Using Causal Reasoning. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{yang_et_al:LIPIcs.SAT.2023.28, author = {Yang, Jiong and Shaw, Arijit and Baluta, Teodora and Soos, Mate and Meel, Kuldeep S.}, title = {{Explaining SAT Solving Using Causal Reasoning}}, booktitle = {26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)}, pages = {28:1--28:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-286-0}, ISSN = {1868-8969}, year = {2023}, volume = {271}, editor = {Mahajan, Meena and Slivovsky, Friedrich}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.28}, URN = {urn:nbn:de:0030-drops-184909}, doi = {10.4230/LIPIcs.SAT.2023.28}, annote = {Keywords: Satisfiability, Causality, SAT solver, Clause management} }
Published in: LIPIcs, Volume 268, 14th International Conference on Interactive Theorem Proving (ITP 2023)
Jujian Zhang. Formalising the Proj Construction in Lean. In 14th International Conference on Interactive Theorem Proving (ITP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 268, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{zhang:LIPIcs.ITP.2023.35, author = {Zhang, Jujian}, title = {{Formalising the Proj Construction in Lean}}, booktitle = {14th International Conference on Interactive Theorem Proving (ITP 2023)}, pages = {35:1--35:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-284-6}, ISSN = {1868-8969}, year = {2023}, volume = {268}, editor = {Naumowicz, Adam and Thiemann, Ren\'{e}}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2023.35}, URN = {urn:nbn:de:0030-drops-184105}, doi = {10.4230/LIPIcs.ITP.2023.35}, annote = {Keywords: Lean, formalisation, algebraic geometry, scheme, Proj construction, projective geometry} }
Feedback for Dagstuhl Publishing