Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Max Dupré la Tour, Monika Henzinger, and David Saulpic. Fully Dynamic k-Means Coreset in Near-Optimal Update Time. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 100:1-100:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{latour_et_al:LIPIcs.ESA.2024.100, author = {la Tour, Max Dupr\'{e} and Henzinger, Monika and Saulpic, David}, title = {{Fully Dynamic k-Means Coreset in Near-Optimal Update Time}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {100:1--100:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.100}, URN = {urn:nbn:de:0030-drops-211716}, doi = {10.4230/LIPIcs.ESA.2024.100}, annote = {Keywords: clustering, fully-dynamic, coreset, k-means} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Hadley Black. Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{black:LIPIcs.APPROX/RANDOM.2024.37, author = {Black, Hadley}, title = {{Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {37:1--37:23}, 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.37}, URN = {urn:nbn:de:0030-drops-210308}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.37}, annote = {Keywords: Property testing, learning, Boolean functions, monotonicity, k-monotonicity} }
Published in: LIPIcs, Volume 313, 38th European Conference on Object-Oriented Programming (ECOOP 2024)
Jie Qiu, Colin Cai, Sahil Bhatia, Niranjan Hasabnis, Sanjit A. Seshia, and Alvin Cheung. Tenspiler: A Verified-Lifting-Based Compiler for Tensor Operations. In 38th European Conference on Object-Oriented Programming (ECOOP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 313, pp. 32:1-32:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{qiu_et_al:LIPIcs.ECOOP.2024.32, author = {Qiu, Jie and Cai, Colin and Bhatia, Sahil and Hasabnis, Niranjan and Seshia, Sanjit A. and Cheung, Alvin}, title = {{Tenspiler: A Verified-Lifting-Based Compiler for Tensor Operations}}, booktitle = {38th European Conference on Object-Oriented Programming (ECOOP 2024)}, pages = {32:1--32:28}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-341-6}, ISSN = {1868-8969}, year = {2024}, volume = {313}, editor = {Aldrich, Jonathan and Salvaneschi, Guido}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2024.32}, URN = {urn:nbn:de:0030-drops-208817}, doi = {10.4230/LIPIcs.ECOOP.2024.32}, annote = {Keywords: Program Synthesis, Code Transpilation, Tensor DSLs, Verification} }
Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)
Kostis Michailidis, Dimos Tsouros, and Tias Guns. Constraint Modelling with LLMs Using In-Context Learning. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 20:1-20:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{michailidis_et_al:LIPIcs.CP.2024.20, author = {Michailidis, Kostis and Tsouros, Dimos and Guns, Tias}, title = {{Constraint Modelling with LLMs Using In-Context Learning}}, booktitle = {30th International Conference on Principles and Practice of Constraint Programming (CP 2024)}, pages = {20:1--20:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-336-2}, ISSN = {1868-8969}, year = {2024}, volume = {307}, editor = {Shaw, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.20}, URN = {urn:nbn:de:0030-drops-207053}, doi = {10.4230/LIPIcs.CP.2024.20}, annote = {Keywords: Constraint Modelling, Constraint Acquisition, Constraint Programming, Large Language Models, In-Context Learning, Natural Language Processing, Named Entity Recognition, Retrieval-Augmented Generation, Optimisation} }
Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)
Florian Régin, Elisabetta De Maria, and Alexandre Bonlarron. Combining Constraint Programming Reasoning with Large Language Model Predictions. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{regin_et_al:LIPIcs.CP.2024.25, author = {R\'{e}gin, Florian and De Maria, Elisabetta and Bonlarron, Alexandre}, title = {{Combining Constraint Programming Reasoning with Large Language Model Predictions}}, booktitle = {30th International Conference on Principles and Practice of Constraint Programming (CP 2024)}, pages = {25:1--25:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-336-2}, ISSN = {1868-8969}, year = {2024}, volume = {307}, editor = {Shaw, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.25}, URN = {urn:nbn:de:0030-drops-207109}, doi = {10.4230/LIPIcs.CP.2024.25}, annote = {Keywords: Solver and Tools, ML-augmented CP, Constrained Text Generation, ML alongside CO} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Fully-Scalable MPC Algorithms for Clustering in High Dimension. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{czumaj_et_al:LIPIcs.ICALP.2024.50, author = {Czumaj, Artur and Gao, Guichen and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel}, title = {{Fully-Scalable MPC Algorithms for Clustering in High Dimension}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {50:1--50:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.50}, URN = {urn:nbn:de:0030-drops-201938}, doi = {10.4230/LIPIcs.ICALP.2024.50}, annote = {Keywords: Massively parallel computing, high dimension, facility location, k-median, k-means} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sami Davies, Benjamin Moseley, and Heather Newman. Simultaneously Approximating All 𝓁_p-Norms in Correlation Clustering. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{davies_et_al:LIPIcs.ICALP.2024.52, author = {Davies, Sami and Moseley, Benjamin and Newman, Heather}, title = {{Simultaneously Approximating All 𝓁\underlinep-Norms in Correlation Clustering}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {52:1--52:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.52}, URN = {urn:nbn:de:0030-drops-201950}, doi = {10.4230/LIPIcs.ICALP.2024.52}, annote = {Keywords: Approximation algorithms, correlation clustering, all-norms, lp-norms} }
Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Improved Sample Complexity Bounds for Branch-And-Cut. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{balcan_et_al:LIPIcs.CP.2022.3, author = {Balcan, Maria-Florina and Prasad, Siddharth and Sandholm, Tuomas and Vitercik, Ellen}, title = {{Improved Sample Complexity Bounds for Branch-And-Cut}}, booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)}, pages = {3:1--3:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-240-2}, ISSN = {1868-8969}, year = {2022}, volume = {235}, editor = {Solnon, Christine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.3}, URN = {urn:nbn:de:0030-drops-166321}, doi = {10.4230/LIPIcs.CP.2022.3}, annote = {Keywords: Automated algorithm configuration, integer programming, machine learning theory, tree search, branch-and-bound, branch-and-cut, cutting planes, sample complexity, generalization guarantees, data-driven algorithm design} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Maria-Florina Balcan. Generalization Guarantees for Data-Driven Mechanism Design (Invited Talk). In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{balcan:LIPIcs.STACS.2022.2, author = {Balcan, Maria-Florina}, title = {{Generalization Guarantees for Data-Driven Mechanism Design}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.2}, URN = {urn:nbn:de:0030-drops-158127}, doi = {10.4230/LIPIcs.STACS.2022.2}, annote = {Keywords: mechanism configuration, algorithm configuration, machine learning, generalization guarantees} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, and David P. Woodruff. Robust Communication-Optimal Distributed Clustering Algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{awasthi_et_al:LIPIcs.ICALP.2019.18, author = {Awasthi, Pranjal and Bakshi, Ainesh and Balcan, Maria-Florina and White, Colin and Woodruff, David P.}, title = {{Robust Communication-Optimal Distributed Clustering Algorithms}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {18:1--18:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.18}, URN = {urn:nbn:de:0030-drops-105942}, doi = {10.4230/LIPIcs.ICALP.2019.18}, annote = {Keywords: robust distributed clustering, communication complexity} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Chandra Chekuri and Shalmoli Gupta. Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chekuri_et_al:LIPIcs.APPROX-RANDOM.2018.9, author = {Chekuri, Chandra and Gupta, Shalmoli}, title = {{Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.9}, URN = {urn:nbn:de:0030-drops-94136}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.9}, annote = {Keywords: Clustering, Perturbation Resilience, LP Integrality, Outliers, Beyond Worst Case Analysis} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, and Hongyang Zhang. Matrix Completion and Related Problems via Strong Duality. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{balcan_et_al:LIPIcs.ITCS.2018.5, author = {Balcan, Maria-Florina and Liang, Yingyu and Woodruff, David P. and Zhang, Hongyang}, title = {{Matrix Completion and Related Problems via Strong Duality}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {5:1--5:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.5}, URN = {urn:nbn:de:0030-drops-83583}, doi = {10.4230/LIPIcs.ITCS.2018.5}, annote = {Keywords: Non-Convex Optimization, Strong Duality, Matrix Completion, Robust PCA, Sample Complexity} }
Published in: Dagstuhl Reports, Volume 6, Issue 9 (2017)
Maria-Florina Balcan, Shai Ben-David, Ruth Urner, and Ulrike von Luxburg. Foundations of Unsupervised Learning (Dagstuhl Seminar 16382). In Dagstuhl Reports, Volume 6, Issue 9, pp. 94-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{balcan_et_al:DagRep.6.9.94, author = {Balcan, Maria-Florina and Ben-David, Shai and Urner, Ruth and von Luxburg, Ulrike}, title = {{Foundations of Unsupervised Learning (Dagstuhl Seminar 16382)}}, pages = {94--109}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {6}, number = {9}, editor = {Balcan, Maria-Florina and Ben-David, Shai and Urner, Ruth and von Luxburg, Ulrike}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.9.94}, URN = {urn:nbn:de:0030-drops-69542}, doi = {10.4230/DagRep.6.9.94}, annote = {Keywords: Machine learning, theory of computing, unsupervised learning, representation learning} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Maria-Florina Balcan, Nika Haghtalab, and Colin White. k-Center Clustering Under Perturbation Resilience. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{balcan_et_al:LIPIcs.ICALP.2016.68, author = {Balcan, Maria-Florina and Haghtalab, Nika and White, Colin}, title = {{k-Center Clustering Under Perturbation Resilience}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {68:1--68: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.68}, URN = {urn:nbn:de:0030-drops-62160}, doi = {10.4230/LIPIcs.ICALP.2016.68}, annote = {Keywords: k-center, clustering, perturbation resilience} }
Published in: Dagstuhl Reports, Volume 4, Issue 9 (2015)
Marina-Florina Balcan, Bodo Manthey, Heiko Röglin, and Tim Roughgarden. Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372). In Dagstuhl Reports, Volume 4, Issue 9, pp. 30-49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@Article{balcan_et_al:DagRep.4.9.30, author = {Balcan, Marina-Florina and Manthey, Bodo and R\"{o}glin, Heiko and Roughgarden, Tim}, title = {{Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372)}}, pages = {30--49}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {4}, number = {9}, editor = {Balcan, Marina-Florina and Manthey, Bodo and R\"{o}glin, Heiko and Roughgarden, Tim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.9.30}, URN = {urn:nbn:de:0030-drops-48829}, doi = {10.4230/DagRep.4.9.30}, annote = {Keywords: analysis of algorithms, probabilistic analysis, smoothed analysis, approximation stability, machine learning} }
Feedback for Dagstuhl Publishing