Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical Computation of Graph VC-Dimension. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{coudert_et_al:LIPIcs.SEA.2024.8, author = {Coudert, David and Csik\'{o}s, M\'{o}nika and Ducoffe, Guillaume and Viennot, Laurent}, title = {{Practical Computation of Graph VC-Dimension}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.8}, URN = {urn:nbn:de:0030-drops-203731}, doi = {10.4230/LIPIcs.SEA.2024.8}, annote = {Keywords: VC-dimension, graph, algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The Discrepancy of Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.27, author = {Bodwin, Greg and Deng, Chengyuan and Gao, Jie and Hoppenworth, Gary and Upadhyay, Jalaj and Wang, Chen}, title = {{The Discrepancy of Shortest Paths}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {27:1--27: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.27}, URN = {urn:nbn:de:0030-drops-201705}, doi = {10.4230/LIPIcs.ICALP.2024.27}, annote = {Keywords: Discrepancy, hereditary discrepancy, shortest paths, differential privacy} }
Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
Bernard Chazelle and Kritkorn Karntikoon. A Connectivity-Sensitive Approach to Consensus Dynamics. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chazelle_et_al:LIPIcs.SAND.2023.10, author = {Chazelle, Bernard and Karntikoon, Kritkorn}, title = {{A Connectivity-Sensitive Approach to Consensus Dynamics}}, booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)}, pages = {10:1--10:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-275-4}, ISSN = {1868-8969}, year = {2023}, volume = {257}, editor = {Doty, David and Spirakis, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.10}, URN = {urn:nbn:de:0030-drops-179464}, doi = {10.4230/LIPIcs.SAND.2023.10}, annote = {Keywords: s-energy, dynamic networks, relaxation time, multiagent systems} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, and Vladimir Podolskii. Complexity of Linear Operators. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kulikov_et_al:LIPIcs.ISAAC.2019.17, author = {Kulikov, Alexander S. and Mikhailin, Ivan and Mokhov, Andrey and Podolskii, Vladimir}, title = {{Complexity of Linear Operators}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {17:1--17:12}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.17}, URN = {urn:nbn:de:0030-drops-115137}, doi = {10.4230/LIPIcs.ISAAC.2019.17}, annote = {Keywords: algorithms, linear operators, commutativity, range queries, circuit complexity, lower bounds, upper bounds} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Peyman Afshani. A New Lower Bound for Semigroup Orthogonal Range Searching. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{afshani:LIPIcs.SoCG.2019.3, author = {Afshani, Peyman}, title = {{A New Lower Bound for Semigroup Orthogonal Range Searching}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {3:1--3:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.3}, URN = {urn:nbn:de:0030-drops-104075}, doi = {10.4230/LIPIcs.SoCG.2019.3}, annote = {Keywords: Data Structures, Range Searching, Lower bounds} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Bernard Chazelle. Toward a Theory of Markov Influence Systems and their Renormalization. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chazelle:LIPIcs.ITCS.2018.58, author = {Chazelle, Bernard}, title = {{Toward a Theory of Markov Influence Systems and their Renormalization}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {58:1--58:18}, 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.58}, URN = {urn:nbn:de:0030-drops-83317}, doi = {10.4230/LIPIcs.ITCS.2018.58}, annote = {Keywords: Markov influence systems, nonlinear Markov chains, dynamical systems, renormalization, graph sequence parsing} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Bernard Chazelle and Chu Wang. Self-Sustaining Iterated Learning. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chazelle_et_al:LIPIcs.ITCS.2017.17, author = {Chazelle, Bernard and Wang, Chu}, title = {{Self-Sustaining Iterated Learning}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {17:1--17:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.17}, URN = {urn:nbn:de:0030-drops-81711}, doi = {10.4230/LIPIcs.ITCS.2017.17}, annote = {Keywords: Iterated learning, language evolution, iterated Bayesian linear regression, non-equilibrium dynamics} }
Published in: Dagstuhl Seminar Proceedings, Volume 5291, Sublinear Algorithms (2006)
Bernard Chazelle, Ding Liu, and Avner Magen. Sublinear Geometric Algorithms. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 5291, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{chazelle_et_al:DagSemProc.05291.4, author = {Chazelle, Bernard and Liu, Ding and Magen, Avner}, title = {{Sublinear Geometric Algorithms}}, booktitle = {Sublinear Algorithms}, pages = {1--18}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {5291}, editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05291.4}, URN = {urn:nbn:de:0030-drops-5548}, doi = {10.4230/DagSemProc.05291.4}, annote = {Keywords: Sublinear algorithms, computational geometry} }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
Helmut Alt, Bernard Chazelle, and Raimund Seidel. Computational Geometry (Dagstuhl Seminar 9511). Dagstuhl Seminar Report 109, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1995)
@TechReport{alt_et_al:DagSemRep.109, author = {Alt, Helmut and Chazelle, Bernard and Seidel, Raimund}, title = {{Computational Geometry (Dagstuhl Seminar 9511)}}, pages = {1--27}, ISSN = {1619-0203}, year = {1995}, type = {Dagstuhl Seminar Report}, number = {109}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.109}, URN = {urn:nbn:de:0030-drops-149970}, doi = {10.4230/DagSemRep.109}, }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
Helmut Alt, Bernard Chazelle, and Emo Welzl. Computational Geometry (Dagstuhl Seminar 9312). Dagstuhl Seminar Report 59, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1993)
@TechReport{alt_et_al:DagSemRep.59, author = {Alt, Helmut and Chazelle, Bernard and Welzl, Emo}, title = {{Computational Geometry (Dagstuhl Seminar 9312)}}, pages = {1--28}, ISSN = {1619-0203}, year = {1993}, type = {Dagstuhl Seminar Report}, number = {59}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.59}, URN = {urn:nbn:de:0030-drops-149479}, doi = {10.4230/DagSemRep.59}, }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
Helmut Alt, Bernard Chazelle, and Emo Welzl. Computational Geometry (Dagstuhl Seminar 9141). Dagstuhl Seminar Report 22, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1991)
@TechReport{alt_et_al:DagSemRep.22, author = {Alt, Helmut and Chazelle, Bernard and Welzl, Emo}, title = {{Computational Geometry (Dagstuhl Seminar 9141)}}, pages = {1--27}, ISSN = {1619-0203}, year = {1991}, type = {Dagstuhl Seminar Report}, number = {22}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.22}, URN = {urn:nbn:de:0030-drops-149101}, doi = {10.4230/DagSemRep.22}, }