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-dev.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 264, 38th Computational Complexity Conference (CCC 2023)
Dmitriy Kunisky and Xifan Yu. A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 30:1-30:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kunisky_et_al:LIPIcs.CCC.2023.30, author = {Kunisky, Dmitriy and Yu, Xifan}, title = {{A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {30:1--30:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.30}, URN = {urn:nbn:de:0030-drops-183008}, doi = {10.4230/LIPIcs.CCC.2023.30}, annote = {Keywords: convex optimization, sum of squares, Paley graph, derandomization} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Daniel A. Spielman and Peng Zhang. Hardness Results for Weaver’s Discrepancy Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{spielman_et_al:LIPIcs.APPROX/RANDOM.2022.40, author = {Spielman, Daniel A. and Zhang, Peng}, title = {{Hardness Results for Weaver’s Discrepancy Problem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {40:1--40:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.40}, URN = {urn:nbn:de:0030-drops-171628}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.40}, annote = {Keywords: Discrepancy Problem, Kadison-Singer Problem, Hardness of Approximation} }
Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)
Samuel I. Daitch and Daniel A. Spielman. A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{daitch_et_al:DagSemProc.09061.3, author = {Daitch, Samuel I. and Spielman, Daniel A.}, title = {{A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix}}, booktitle = {Combinatorial Scientific Computing}, pages = {1--4}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9061}, editor = {Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.3}, URN = {urn:nbn:de:0030-drops-20803}, doi = {10.4230/DagSemProc.09061.3}, annote = {Keywords: M-matrix, diagonally-dominant matrix, linear system solver, iterative algorithm, randomized algorithm, network flow, gain graph} }
Feedback for Dagstuhl Publishing