Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Yi Li, Honghao Lin, David P. Woodruff, and Yuheng Zhang. Streaming Algorithms with Large Approximation Factors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{li_et_al:LIPIcs.APPROX/RANDOM.2022.13, author = {Li, Yi and Lin, Honghao and Woodruff, David P. and Zhang, Yuheng}, title = {{Streaming Algorithms with Large Approximation Factors}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {13:1--13:23}, 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.13}, URN = {urn:nbn:de:0030-drops-171354}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.13}, annote = {Keywords: streaming algorithms, 𝓁\underlinep norm, heavy hitters, distinct elements} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Yi Li and David P. Woodruff. The Product of Gaussian Matrices Is Close to Gaussian. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 35:1-35:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{li_et_al:LIPIcs.APPROX/RANDOM.2021.35, author = {Li, Yi and Woodruff, David P.}, title = {{The Product of Gaussian Matrices Is Close to Gaussian}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {35:1--35:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.35}, URN = {urn:nbn:de:0030-drops-147281}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.35}, annote = {Keywords: random matrix theory, total variation distance, matrix product} }
Published in: OASIcs, Volume 89, 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)
Li Yi and Jan C. Aurich. Development and Validation of Energy Simulation for Additive Manufacturing. In 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020). Open Access Series in Informatics (OASIcs), Volume 89, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{yi_et_al:OASIcs.iPMVM.2020.1, author = {Yi, Li and Aurich, Jan C.}, title = {{Development and Validation of Energy Simulation for Additive Manufacturing}}, booktitle = {2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)}, pages = {1:1--1:17}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-183-2}, ISSN = {2190-6807}, year = {2021}, volume = {89}, editor = {Garth, Christoph and Aurich, Jan C. and Linke, Barbara and M\"{u}ller, Ralf and Ravani, Bahram and Weber, Gunther H. and Kirsch, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.iPMVM.2020.1}, URN = {urn:nbn:de:0030-drops-137500}, doi = {10.4230/OASIcs.iPMVM.2020.1}, annote = {Keywords: Additive manufacturing, fused deposition modeling, selective laser melting, energy simulation, eco-design for AM} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Zhengyang Guo and Yi Li. Geometric Cover with Outliers Removal. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{guo_et_al:LIPIcs.STACS.2021.39, author = {Guo, Zhengyang and Li, Yi}, title = {{Geometric Cover with Outliers Removal}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.39}, URN = {urn:nbn:de:0030-drops-136849}, doi = {10.4230/LIPIcs.STACS.2021.39}, annote = {Keywords: Geometric Cover, Unit Square Cover, Unit Disk Cover, Shifting Strategy, Outliers Detection, Computational Geometry} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Ke Yi. Worst-Case Optimal Join Algorithms (Invited Talk). In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{yi:LIPIcs.ISAAC.2020.2, author = {Yi, Ke}, title = {{Worst-Case Optimal Join Algorithms}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.2}, URN = {urn:nbn:de:0030-drops-133462}, doi = {10.4230/LIPIcs.ISAAC.2020.2}, annote = {Keywords: query evaluation} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, and David P. Woodruff. Streaming Complexity of SVMs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 50:1-50:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{andoni_et_al:LIPIcs.APPROX/RANDOM.2020.50, author = {Andoni, Alexandr and Burns, Collin and Li, Yi and Mahabadi, Sepideh and Woodruff, David P.}, title = {{Streaming Complexity of SVMs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {50:1--50:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, 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.2020.50}, URN = {urn:nbn:de:0030-drops-126532}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.50}, annote = {Keywords: support vector machine, streaming algorithm, space lower bound, sketching algorithm, point estimation} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Yi Li and Vasileios Nakos. Deterministic Sparse Fourier Transform with an 𝓁_{∞} Guarantee. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 77:1-77:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{li_et_al:LIPIcs.ICALP.2020.77, author = {Li, Yi and Nakos, Vasileios}, title = {{Deterministic Sparse Fourier Transform with an 𝓁\underline\{∞\} Guarantee}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {77:1--77:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.77}, URN = {urn:nbn:de:0030-drops-124844}, doi = {10.4230/LIPIcs.ICALP.2020.77}, annote = {Keywords: Fourier sparse recovery, derandomization, incoherent matrices} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Yi-Jun Chang, Martín Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai. Streaming Complexity of Spanning Tree Computation. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chang_et_al:LIPIcs.STACS.2020.34, author = {Chang, Yi-Jun and Farach-Colton, Mart{\'\i}n and Hsu, Tsan-Sheng and Tsai, Meng-Tsung}, title = {{Streaming Complexity of Spanning Tree Computation}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {34:1--34:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.34}, URN = {urn:nbn:de:0030-drops-118951}, doi = {10.4230/LIPIcs.STACS.2020.34}, annote = {Keywords: Max-Leaf Spanning Trees, BFS Trees, DFS Trees} }
Published in: Dagstuhl Reports, Volume 9, Issue 4 (2019)
Krishnendu Chakrabarty, Tsung-Yi Ho, Hai Li, and Ulf Schlichtmann. Emerging Hardware Techniques and EDA Methodologies for Neuromorphic Computing (Dagstuhl Seminar 19152). In Dagstuhl Reports, Volume 9, Issue 4, pp. 43-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{chakrabarty_et_al:DagRep.9.4.43, author = {Chakrabarty, Krishnendu and Ho, Tsung-Yi and Li, Hai and Schlichtmann, Ulf}, title = {{Emerging Hardware Techniques and EDA Methodologies for Neuromorphic Computing (Dagstuhl Seminar 19152)}}, pages = {43--58}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {4}, editor = {Chakrabarty, Krishnendu and Ho, Tsung-Yi and Li, Hai and Schlichtmann, Ulf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.4.43}, URN = {urn:nbn:de:0030-drops-113034}, doi = {10.4230/DagRep.9.4.43}, annote = {Keywords: Neuromorphic computing; nanotechnology; hardware design; electronic design automation; reliability and robustness} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of Linear Sketching Under Modular Updates. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hosseini_et_al:LIPIcs.CCC.2019.13, author = {Hosseini, Kaave and Lovett, Shachar and Yaroslavtsev, Grigory}, title = {{Optimality of Linear Sketching Under Modular Updates}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {13:1--13:17}, 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.13}, URN = {urn:nbn:de:0030-drops-108355}, doi = {10.4230/LIPIcs.CCC.2019.13}, annote = {Keywords: communication complexity, linear sketching, streaming algorithm} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Merav Parter and Hsin-Hao Su. Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{parter_et_al:LIPIcs.DISC.2018.39, author = {Parter, Merav and Su, Hsin-Hao}, title = {{Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {39:1--39:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.39}, URN = {urn:nbn:de:0030-drops-98286}, doi = {10.4230/LIPIcs.DISC.2018.39}, annote = {Keywords: Distributed Graph Algorithms, Coloring, congested clique} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Yi Li and Vasileios Nakos. Deterministic Heavy Hitters with Sublinear Query Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2018.18, author = {Li, Yi and Nakos, Vasileios}, title = {{Deterministic Heavy Hitters with Sublinear Query Time}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {18:1--18:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.18}, URN = {urn:nbn:de:0030-drops-94221}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.18}, annote = {Keywords: heavy hitters, turnstile model, sketching algorithm, strongly explicit} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Yi Li, Vasileios Nakos, and David P. Woodruff. On Low-Risk Heavy Hitters and Sparse Recovery Schemes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2018.19, author = {Li, Yi and Nakos, Vasileios and Woodruff, David P.}, title = {{On Low-Risk Heavy Hitters and Sparse Recovery Schemes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {19:1--19:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.19}, URN = {urn:nbn:de:0030-drops-94237}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.19}, annote = {Keywords: heavy hitters, sparse recovery, turnstile model, spike covariance model, lower bounds} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Yi Li and David P. Woodruff. Embeddings of Schatten Norms with Applications to Data Streams. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{li_et_al:LIPIcs.ICALP.2017.60, author = {Li, Yi and Woodruff, David P.}, title = {{Embeddings of Schatten Norms with Applications to Data Streams}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {60:1--60:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.60}, URN = {urn:nbn:de:0030-drops-73726}, doi = {10.4230/LIPIcs.ICALP.2017.60}, annote = {Keywords: data stream algorithms, embeddings, matrix norms, sketching} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Yi Li and David P. Woodruff. Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 39:1-39:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2016.39, author = {Li, Yi and Woodruff, David P.}, title = {{Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {39:1--39:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, 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.2016.39}, URN = {urn:nbn:de:0030-drops-66620}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.39}, annote = {Keywords: data streams, sketching, matrix norms, subspace embeddings} }
Feedback for Dagstuhl Publishing