Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yu Chen, Michael Kapralov, Mikhail Makarov, and Davide Mazzali. On the Streaming Complexity of Expander Decomposition. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.46, author = {Chen, Yu and Kapralov, Michael and Makarov, Mikhail and Mazzali, Davide}, title = {{On the Streaming Complexity of Expander Decomposition}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {46:1--46: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.46}, URN = {urn:nbn:de:0030-drops-201890}, doi = {10.4230/LIPIcs.ICALP.2024.46}, annote = {Keywords: Graph Sketching, Dynamic Streaming, Expander Decomposition} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yu Chen and Zihan Tan. Lower Bounds on 0-Extension with Steiner Nodes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.47, author = {Chen, Yu and Tan, Zihan}, title = {{Lower Bounds on 0-Extension with Steiner Nodes}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {47:1--47:18}, 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.47}, URN = {urn:nbn:de:0030-drops-201905}, doi = {10.4230/LIPIcs.ICALP.2024.47}, annote = {Keywords: Graph Algorithms, Zero Extension, Integrality Gap} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Yu Chen, Sanjeev Khanna, and Zihan Tan. Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ICALP.2023.37, author = {Chen, Yu and Khanna, Sanjeev and Tan, Zihan}, title = {{Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {37:1--37:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.37}, URN = {urn:nbn:de:0030-drops-180892}, doi = {10.4230/LIPIcs.ICALP.2023.37}, annote = {Keywords: Minimum spanning tree, travelling salesman problem, streaming algorithms} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Yu Chen, Sanjeev Khanna, and Ansh Nagda. Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.ICALP.2021.53, author = {Chen, Yu and Khanna, Sanjeev and Nagda, Ansh}, title = {{Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {53:1--53:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.53}, URN = {urn:nbn:de:0030-drops-141227}, doi = {10.4230/LIPIcs.ICALP.2021.53}, annote = {Keywords: hypergraphs, graph sparsification, cut queries} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Yu Chen, Sampath Kannan, and Sanjeev Khanna. Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chen_et_al:LIPIcs.ICALP.2020.30, author = {Chen, Yu and Kannan, Sampath and Khanna, Sanjeev}, title = {{Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {30:1--30:19}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.30}, URN = {urn:nbn:de:0030-drops-124372}, doi = {10.4230/LIPIcs.ICALP.2020.30}, annote = {Keywords: sublinear algorithms, TSP, streaming algorithms, query complexity} }
Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)
Yu Chen and Ke Yi. Random Sampling and Size Estimation Over Cyclic Joins. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chen_et_al:LIPIcs.ICDT.2020.7, author = {Chen, Yu and Yi, Ke}, title = {{Random Sampling and Size Estimation Over Cyclic Joins}}, booktitle = {23rd International Conference on Database Theory (ICDT 2020)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-139-9}, ISSN = {1868-8969}, year = {2020}, volume = {155}, editor = {Lutz, Carsten and Jung, Jean Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.7}, URN = {urn:nbn:de:0030-drops-119315}, doi = {10.4230/LIPIcs.ICDT.2020.7}, annote = {Keywords: Random sampling, joins, join size estimation} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Parosh A. Abdulla, Yu-Fang Chen, Lukas Holik, and Tomas Vojnar. Mediating for Reduction (on Minimizing Alternating Büchi Automata). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{abdulla_et_al:LIPIcs.FSTTCS.2009.2302, author = {Abdulla, Parosh A. and Chen, Yu-Fang and Holik, Lukas and Vojnar, Tomas}, title = {{Mediating for Reduction (on Minimizing Alternating B\"{u}chi Automata)}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {1--12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2302}, URN = {urn:nbn:de:0030-drops-23027}, doi = {10.4230/LIPIcs.FSTTCS.2009.2302}, annote = {Keywords: Alternating Automata, Buchi Automata, Automata Minimization, Buchi Automata Complementation, Simulation Preorder, forward and backward simulation, mediated equivalence} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Timothy M. Chan, Qizheng He, and Yuancheng Yu. On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chan_et_al:LIPIcs.ICALP.2023.34, author = {Chan, Timothy M. and He, Qizheng and Yu, Yuancheng}, title = {{On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {34:1--34:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.34}, URN = {urn:nbn:de:0030-drops-180868}, doi = {10.4230/LIPIcs.ICALP.2023.34}, annote = {Keywords: Geometric set cover, discrete k-center, conditional lower bounds} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu. Approximation Algorithms for Min-Distance Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dalirrooyfard_et_al:LIPIcs.ICALP.2019.46, author = {Dalirrooyfard, Mina and Williams, Virginia Vassilevska and Vyas, Nikhil and Wein, Nicole and Xu, Yinzhan and Yu, Yuancheng}, title = {{Approximation Algorithms for Min-Distance Problems}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {46:1--46:14}, 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.46}, URN = {urn:nbn:de:0030-drops-106223}, doi = {10.4230/LIPIcs.ICALP.2019.46}, annote = {Keywords: fine-grained complexity, graph algorithms, diameter, radius, eccentricities} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, and Yuancheng Yu. Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chen_et_al:LIPIcs.SWAT.2018.33, author = {Chen, Lijie and Demaine, Erik D. and Gu, Yuzhou and Williams, Virginia Vassilevska and Xu, Yinzhan and Yu, Yuancheng}, title = {{Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {33:1--33:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.33}, URN = {urn:nbn:de:0030-drops-88593}, doi = {10.4230/LIPIcs.SWAT.2018.33}, annote = {Keywords: retroactive data structure, conditional lower bound} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Huacheng Yu and Wei Zhan. Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 99:1-99:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{yu_et_al:LIPIcs.ITCS.2024.99, author = {Yu, Huacheng and Zhan, Wei}, title = {{Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {99:1--99:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.99}, URN = {urn:nbn:de:0030-drops-196270}, doi = {10.4230/LIPIcs.ITCS.2024.99}, annote = {Keywords: Time-space tradeoffs, Randomness, Borodin-Cook method} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Huacheng Yu and Wei Zhan. Sampling, Flowers and Communication. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 100:1-100:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{yu_et_al:LIPIcs.ITCS.2024.100, author = {Yu, Huacheng and Zhan, Wei}, title = {{Sampling, Flowers and Communication}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {100:1--100:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.100}, URN = {urn:nbn:de:0030-drops-196288}, doi = {10.4230/LIPIcs.ITCS.2024.100}, annote = {Keywords: Flower, Sampling, Cell probe, Communcation complexity} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Sepehr Assadi, Michael Kapralov, and Huacheng Yu. On Constructing Spanners from Random Gaussian Projections. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 57:1-57:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{assadi_et_al:LIPIcs.APPROX/RANDOM.2023.57, author = {Assadi, Sepehr and Kapralov, Michael and Yu, Huacheng}, title = {{On Constructing Spanners from Random Gaussian Projections}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {57:1--57:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.57}, URN = {urn:nbn:de:0030-drops-188821}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.57}, annote = {Keywords: sketching algorithm, lower bound, graph spanner} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, and Huacheng Yu. Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 80:1-80:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kol_et_al:LIPIcs.ITCS.2023.80, author = {Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R. and Yu, Huacheng}, title = {{Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {80:1--80:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.80}, URN = {urn:nbn:de:0030-drops-175837}, doi = {10.4230/LIPIcs.ITCS.2023.80}, annote = {Keywords: Streaming algorithms, Constraint Satisfaction Problems} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 52:1-52:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.ICALP.2021.52, author = {Chen, Lijie and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R. and Song, Zhao and Yu, Huacheng}, title = {{Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {52:1--52:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.52}, URN = {urn:nbn:de:0030-drops-141218}, doi = {10.4230/LIPIcs.ICALP.2021.52}, annote = {Keywords: streaming algorithms, random walk sampling} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Mingmou Liu, Yitong Yin, and Huacheng Yu. Succinct Filters for Sets of Unknown Sizes. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 79:1-79:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{liu_et_al:LIPIcs.ICALP.2020.79, author = {Liu, Mingmou and Yin, Yitong and Yu, Huacheng}, title = {{Succinct Filters for Sets of Unknown Sizes}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {79:1--79:19}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.79}, URN = {urn:nbn:de:0030-drops-124867}, doi = {10.4230/LIPIcs.ICALP.2020.79}, annote = {Keywords: Bloom filters, Data structures, Approximate set membership, Dictionaries} }
Published in: LIPIcs, Volume 205, 27th International Conference on DNA Computing and Molecular Programming (DNA 27) (2021)
Johannes Linder, Yuan-Jyue Chen, David Wong, Georg Seelig, Luis Ceze, and Karin Strauss. Robust Digital Molecular Design of Binarized Neural Networks. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{linder_et_al:LIPIcs.DNA.27.1, author = {Linder, Johannes and Chen, Yuan-Jyue and Wong, David and Seelig, Georg and Ceze, Luis and Strauss, Karin}, title = {{Robust Digital Molecular Design of Binarized Neural Networks}}, booktitle = {27th International Conference on DNA Computing and Molecular Programming (DNA 27)}, pages = {1:1--1:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-205-1}, ISSN = {1868-8969}, year = {2021}, volume = {205}, editor = {Lakin, Matthew R. and \v{S}ulc, Petr}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.1}, URN = {urn:nbn:de:0030-drops-146685}, doi = {10.4230/LIPIcs.DNA.27.1}, annote = {Keywords: Molecular Computing, Neural Network, Binarized Neural Network, Digital Logic, DNA, Strand Displacement} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Jinyuan Chen. Optimal Error-Free Multi-Valued Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen:LIPIcs.DISC.2021.17, author = {Chen, Jinyuan}, title = {{Optimal Error-Free Multi-Valued Byzantine Agreement}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {17:1--17:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.17}, URN = {urn:nbn:de:0030-drops-148190}, doi = {10.4230/LIPIcs.DISC.2021.17}, annote = {Keywords: Byzantine agreement, information-theoretic security, error correction codes} }
Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Jie Wang, Dingding Chen, Ziyu Chen, Xiangshuang Liu, and Junsong Gao. Completeness Matters: Towards Efficient Caching in Tree-Based Synchronous Backtracking Search for DCOPs. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{wang_et_al:LIPIcs.CP.2022.39, author = {Wang, Jie and Chen, Dingding and Chen, Ziyu and Liu, Xiangshuang and Gao, Junsong}, title = {{Completeness Matters: Towards Efficient Caching in Tree-Based Synchronous Backtracking Search for DCOPs}}, booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)}, pages = {39:1--39:17}, 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.39}, URN = {urn:nbn:de:0030-drops-166685}, doi = {10.4230/LIPIcs.CP.2022.39}, annote = {Keywords: DCOP, Cache, Any-space Algorithms, Complete Search Algorithms} }
Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Xiangshuang Liu, Ziyu Chen, Dingding Chen, and Junsong Gao. A Bound-Independent Pruning Technique to Speeding up Tree-Based Complete Search Algorithms for Distributed Constraint Optimization Problems. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{liu_et_al:LIPIcs.CP.2021.41, author = {Liu, Xiangshuang and Chen, Ziyu and Chen, Dingding and Gao, Junsong}, title = {{A Bound-Independent Pruning Technique to Speeding up Tree-Based Complete Search Algorithms for Distributed Constraint Optimization Problems}}, booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, pages = {41:1--41:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-211-2}, ISSN = {1868-8969}, year = {2021}, volume = {210}, editor = {Michel, Laurent D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.41}, URN = {urn:nbn:de:0030-drops-153324}, doi = {10.4230/LIPIcs.CP.2021.41}, annote = {Keywords: DCOP, complete algorithms, search} }