Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Dongrun Cai, Xue Chen, and Pan Peng. Effective Resistances in Non-Expander Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cai_et_al:LIPIcs.ESA.2023.29, author = {Cai, Dongrun and Chen, Xue and Peng, Pan}, title = {{Effective Resistances in Non-Expander Graphs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {29:1--29:18}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.29}, URN = {urn:nbn:de:0030-drops-186823}, doi = {10.4230/LIPIcs.ESA.2023.29}, annote = {Keywords: Sublinear Time Algorithm, Effective Resistance, Leverage Scores, Matrix Perturbation} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{burke_et_al:LIPIcs.FUN.2022.10, author = {Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua}, title = {{Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {10:1--10:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.10}, URN = {urn:nbn:de:0030-drops-159808}, doi = {10.4230/LIPIcs.FUN.2022.10}, annote = {Keywords: Combinatorial Games, Nim, Generalized Geography, Sprague-Grundy Theory, Grundy value, Computational Complexity, Functional-Preserving Reductions} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Quantum-Inspired Combinatorial Games: Algorithms and Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{burke_et_al:LIPIcs.FUN.2022.11, author = {Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua}, title = {{Quantum-Inspired Combinatorial Games: Algorithms and Complexity}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {11:1--11:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.11}, URN = {urn:nbn:de:0030-drops-159812}, doi = {10.4230/LIPIcs.FUN.2022.11}, annote = {Keywords: Quantum-Inspired Games, Combinatorial Games, Computational Complexity, Polynomial Hierarchy, \c{c}lass\{PSPACE\}, Nim, Generalized Geography, Snort} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Wei Chen, Shang-Hua Teng, and Hanrui Zhang. Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.ITCS.2019.24, author = {Chen, Wei and Teng, Shang-Hua and Zhang, Hanrui}, title = {{Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {24:1--24:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.24}, URN = {urn:nbn:de:0030-drops-101174}, doi = {10.4230/LIPIcs.ITCS.2019.24}, annote = {Keywords: set functions, measure of complementarity, submodularity, subadditivity, cardinality constrained maximization, welfare maximization, simple auctions, price of anarchy} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Shang-Hua Teng. Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences (Invited Talk). In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{teng:LIPIcs.ISAAC.2018.1, author = {Teng, Shang-Hua}, title = {{Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {1:1--1:1}, 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.1}, URN = {urn:nbn:de:0030-drops-99495}, doi = {10.4230/LIPIcs.ISAAC.2018.1}, annote = {Keywords: scalable algorithms, axiomatization, graph sparsification, local algorithms, advanced sampling, big data, network sciences, machine learning, social influence, beyond graph theory} }
Published in: Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Martin Dietzfelbinger, Shang-Hua Teng, Eli Upfal, and Berthold Vöcking. 07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms. In Probabilistic Methods in the Design and Analysis of Algorithms. Dagstuhl Seminar Proceedings, Volume 7391, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{dietzfelbinger_et_al:DagSemProc.07391.1, author = {Dietzfelbinger, Martin and Teng, Shang-Hua and Upfal, Eli and V\"{o}cking, Berthold}, title = {{07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms}}, booktitle = {Probabilistic Methods in the Design and Analysis of Algorithms}, pages = {1--18}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7391}, editor = {Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.1}, URN = {urn:nbn:de:0030-drops-12915}, doi = {10.4230/DagSemProc.07391.1}, annote = {Keywords: Algorithms, Randomization, Probabilistic analysis, Complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Chaitanya Swamy and David Shmoys. Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization. In Probabilistic Methods in the Design and Analysis of Algorithms. Dagstuhl Seminar Proceedings, Volume 7391, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{swamy_et_al:DagSemProc.07391.2, author = {Swamy, Chaitanya and Shmoys, David}, title = {{Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization}}, booktitle = {Probabilistic Methods in the Design and Analysis of Algorithms}, pages = {1--24}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7391}, editor = {Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.2}, URN = {urn:nbn:de:0030-drops-12906}, doi = {10.4230/DagSemProc.07391.2}, annote = {Keywords: Stochastic optimization, approximation algorithms, randomized algorithms, linear programming} }
Published in: Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Bodo Manthey and Till Tantau. Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. In Probabilistic Methods in the Design and Analysis of Algorithms. Dagstuhl Seminar Proceedings, Volume 7391, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{manthey_et_al:DagSemProc.07391.3, author = {Manthey, Bodo and Tantau, Till}, title = {{Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise}}, booktitle = {Probabilistic Methods in the Design and Analysis of Algorithms}, pages = {1--19}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7391}, editor = {Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.3}, URN = {urn:nbn:de:0030-drops-12893}, doi = {10.4230/DagSemProc.07391.3}, annote = {Keywords: Smoothed Analysis, Binary Search Trees, Quicksort, Left-to-right Maxima} }
Feedback for Dagstuhl Publishing