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 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amit Deshpande and Rameshwar Pratap. One-Pass Additive-Error Subset Selection for 𝓁_p Subspace Approximation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{deshpande_et_al:LIPIcs.ICALP.2022.51, author = {Deshpande, Amit and Pratap, Rameshwar}, title = {{One-Pass Additive-Error Subset Selection for 𝓁\underlinep Subspace Approximation}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {51:1--51:14}, 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.51}, URN = {urn:nbn:de:0030-drops-163924}, doi = {10.4230/LIPIcs.ICALP.2022.51}, annote = {Keywords: Subspace approximation, streaming algorithms, low-rank approximation, adaptive sampling, volume sampling, subset selection} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Almost Shortest Paths with Near-Additive Error in Weighted Graphs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{elkin_et_al:LIPIcs.SWAT.2022.23, author = {Elkin, Michael and Gitlitz, Yuval and Neiman, Ofer}, title = {{Almost Shortest Paths with Near-Additive Error in Weighted Graphs}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {23:1--23:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.23}, URN = {urn:nbn:de:0030-drops-161833}, doi = {10.4230/LIPIcs.SWAT.2022.23}, annote = {Keywords: spanners, hopset, shortest paths, PRAM, distance oracles} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
W. Cole Franks and Philipp Reichenbach. Barriers for Recent Methods in Geodesic Optimization. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 13:1-13:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{franks_et_al:LIPIcs.CCC.2021.13, author = {Franks, W. Cole and Reichenbach, Philipp}, title = {{Barriers for Recent Methods in Geodesic Optimization}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {13:1--13:54}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.13}, URN = {urn:nbn:de:0030-drops-142879}, doi = {10.4230/LIPIcs.CCC.2021.13}, annote = {Keywords: Geodesically Convex Optimization, Weight Margin, Moment Polytope, Diameter Bounds, Tensor Scaling, Matrix Scaling} }
Published in: LIPIcs, Volume 193, 12th International Conference on Interactive Theorem Proving (ITP 2021)
Magnus O. Myreen. The CakeML Project’s Quest for Ever Stronger Correctness Theorems (Invited Paper). In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{myreen:LIPIcs.ITP.2021.1, author = {Myreen, Magnus O.}, title = {{The CakeML Project’s Quest for Ever Stronger Correctness Theorems}}, booktitle = {12th International Conference on Interactive Theorem Proving (ITP 2021)}, pages = {1:1--1:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-188-7}, ISSN = {1868-8969}, year = {2021}, volume = {193}, editor = {Cohen, Liron and Kaliszyk, Cezary}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2021.1}, URN = {urn:nbn:de:0030-drops-138963}, doi = {10.4230/LIPIcs.ITP.2021.1}, annote = {Keywords: Program verification, interactive theorem proving} }
Published in: LIPIcs, Volume 193, 12th International Conference on Interactive Theorem Proving (ITP 2021)
Kesha Hietala, Robert Rand, Shih-Han Hung, Liyi Li, and Michael Hicks. Proving Quantum Programs Correct. In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{hietala_et_al:LIPIcs.ITP.2021.21, author = {Hietala, Kesha and Rand, Robert and Hung, Shih-Han and Li, Liyi and Hicks, Michael}, title = {{Proving Quantum Programs Correct}}, booktitle = {12th International Conference on Interactive Theorem Proving (ITP 2021)}, pages = {21:1--21:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-188-7}, ISSN = {1868-8969}, year = {2021}, volume = {193}, editor = {Cohen, Liron and Kaliszyk, Cezary}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2021.21}, URN = {urn:nbn:de:0030-drops-139160}, doi = {10.4230/LIPIcs.ITP.2021.21}, annote = {Keywords: Formal Verification, Quantum Computing, Proof Engineering} }
Published in: LIPIcs, Volume 193, 12th International Conference on Interactive Theorem Proving (ITP 2021)
Konrad Slind. Specifying Message Formats with Contiguity Types. In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{slind:LIPIcs.ITP.2021.30, author = {Slind, Konrad}, title = {{Specifying Message Formats with Contiguity Types}}, booktitle = {12th International Conference on Interactive Theorem Proving (ITP 2021)}, pages = {30:1--30:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-188-7}, ISSN = {1868-8969}, year = {2021}, volume = {193}, editor = {Cohen, Liron and Kaliszyk, Cezary}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2021.30}, URN = {urn:nbn:de:0030-drops-139252}, doi = {10.4230/LIPIcs.ITP.2021.30}, annote = {Keywords: Logic, verification, formal language theory, message format languages} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Michael B. Cohen, Aaron Sidford, and Kevin Tian. Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 62:1-62:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cohen_et_al:LIPIcs.ITCS.2021.62, author = {Cohen, Michael B. and Sidford, Aaron and Tian, Kevin}, title = {{Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {62:1--62:18}, 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.62}, URN = {urn:nbn:de:0030-drops-136011}, doi = {10.4230/LIPIcs.ITCS.2021.62}, annote = {Keywords: Variational inequalities, minimax optimization, acceleration, 𝓁\underline∞ regression} }
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 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, and Siddharth Gupta. C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dalozzo_et_al:LIPIcs.IPEC.2019.9, author = {Da Lozzo, Giordano and Eppstein, David and Goodrich, Michael T. and Gupta, Siddharth}, title = {{C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.9}, URN = {urn:nbn:de:0030-drops-114705}, doi = {10.4230/LIPIcs.IPEC.2019.9}, annote = {Keywords: Clustered planarity, carving-width, non-crossing partitions, FPT} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Vincent Cohen-Addad, Marcin Pilipczuk, and Michał Pilipczuk. Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cohenaddad_et_al:LIPIcs.ESA.2019.33, author = {Cohen-Addad, Vincent and Pilipczuk, Marcin and Pilipczuk, Micha{\l}}, title = {{Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {33:1--33:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.33}, URN = {urn:nbn:de:0030-drops-111543}, doi = {10.4230/LIPIcs.ESA.2019.33}, annote = {Keywords: k-Median, Facility Location, Planar Graphs, Approximation Scheme} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Adam Karczmarz and Piotr Sankowski. Min-Cost Flow in Unit-Capacity Planar Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 66:1-66:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{karczmarz_et_al:LIPIcs.ESA.2019.66, author = {Karczmarz, Adam and Sankowski, Piotr}, title = {{Min-Cost Flow in Unit-Capacity Planar Graphs}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {66:1--66:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.66}, URN = {urn:nbn:de:0030-drops-111878}, doi = {10.4230/LIPIcs.ESA.2019.66}, annote = {Keywords: minimum-cost flow, minimum-cost circulation, planar graphs} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
William M. Hoza. Typically-Correct Derandomization for Small Time and Space. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 9:1-9:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hoza:LIPIcs.CCC.2019.9, author = {Hoza, William M.}, title = {{Typically-Correct Derandomization for Small Time and Space}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {9:1--9:39}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.9}, URN = {urn:nbn:de:0030-drops-108317}, doi = {10.4230/LIPIcs.CCC.2019.9}, annote = {Keywords: Derandomization, pseudorandomness, space complexity} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Dean Doron, Pooya Hatami, and William M. Hoza. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 16:1-16:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{doron_et_al:LIPIcs.CCC.2019.16, author = {Doron, Dean and Hatami, Pooya and Hoza, William M.}, title = {{Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {16:1--16:34}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.16}, URN = {urn:nbn:de:0030-drops-108382}, doi = {10.4230/LIPIcs.CCC.2019.16}, annote = {Keywords: Pseudorandom generators, Constant-depth formulas, Explicit constructions} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Michael B. Cohen, T.S. Jayram, and Jelani Nelson. Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 15:1-15:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{cohen_et_al:OASIcs.SOSA.2018.15, author = {Cohen, Michael B. and Jayram, T.S. and Nelson, Jelani}, title = {{Simple Analyses of the Sparse Johnson-Lindenstrauss Transform}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {15:1--15:9}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.15}, URN = {urn:nbn:de:0030-drops-83056}, doi = {10.4230/OASIcs.SOSA.2018.15}, annote = {Keywords: dimensionality reduction, Johnson-Lindenstrauss, Sparse Johnson-Lindenstrauss Transform} }
Feedback for Dagstuhl Publishing