Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Quanquan C. Liu, Yiduo Ke, and Samir Khuller. Scalable Auction Algorithms for Bipartite Maximum Matching Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 28:1-28:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{liu_et_al:LIPIcs.APPROX/RANDOM.2023.28, author = {Liu, Quanquan C. and Ke, Yiduo and Khuller, Samir}, title = {{Scalable Auction Algorithms for Bipartite Maximum Matching Problems}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {28:1--28:24}, 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.28}, URN = {urn:nbn:de:0030-drops-188537}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.28}, annote = {Keywords: auction algorithms, maximum weight bipartite matching, maximum b-matching, distributed blackboard model, parallel work-depth model, streaming model, massively parallel computation model} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, and Adam Smith. Triangle Counting with Local Edge Differential Privacy. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 52:1-52:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{eden_et_al:LIPIcs.ICALP.2023.52, author = {Eden, Talya and Liu, Quanquan C. and Raskhodnikova, Sofya and Smith, Adam}, title = {{Triangle Counting with Local Edge Differential Privacy}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {52:1--52:21}, 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.52}, URN = {urn:nbn:de:0030-drops-181048}, doi = {10.4230/LIPIcs.ICALP.2023.52}, annote = {Keywords: local differential privacy, reconstruction attacks, lower bounds, triangle counting} }
Published in: LIPIcs, Volume 256, 4th Symposium on Foundations of Responsible Computing (FORC 2023)
Arpita Biswas, Yiduo Ke, Samir Khuller, and Quanquan C. Liu. An Algorithmic Approach to Address Course Enrollment Challenges. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 256, pp. 8:1-8:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{biswas_et_al:LIPIcs.FORC.2023.8, author = {Biswas, Arpita and Ke, Yiduo and Khuller, Samir and Liu, Quanquan C.}, title = {{An Algorithmic Approach to Address Course Enrollment Challenges}}, booktitle = {4th Symposium on Foundations of Responsible Computing (FORC 2023)}, pages = {8:1--8:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-272-3}, ISSN = {1868-8969}, year = {2023}, volume = {256}, editor = {Talwar, Kunal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2023.8}, URN = {urn:nbn:de:0030-drops-179297}, doi = {10.4230/LIPIcs.FORC.2023.8}, annote = {Keywords: fairness, allocation, matching, algorithms} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, and Slobodan Mitrović. Massively Parallel Algorithms for Small Subgraph Counting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 39:1-39:28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{biswas_et_al:LIPIcs.APPROX/RANDOM.2022.39, author = {Biswas, Amartya Shankha and Eden, Talya and Liu, Quanquan C. and Rubinfeld, Ronitt and Mitrovi\'{c}, Slobodan}, title = {{Massively Parallel Algorithms for Small Subgraph Counting}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {39:1--39:28}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.39}, URN = {urn:nbn:de:0030-drops-171619}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.39}, annote = {Keywords: triangle counting, massively parallel computation, clique counting, approximation algorithms, subgraph counting} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Quanquan C. Liu, Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua R. Wang. Scheduling with Communication Delay in Near-Linear Time. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 47:1-47:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{liu_et_al:LIPIcs.STACS.2022.47, author = {Liu, Quanquan C. and Purohit, Manish and Svitkina, Zoya and Vee, Erik and Wang, Joshua R.}, title = {{Scheduling with Communication Delay in Near-Linear Time}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {47:1--47:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.47}, URN = {urn:nbn:de:0030-drops-158570}, doi = {10.4230/LIPIcs.STACS.2022.47}, annote = {Keywords: near-linear time scheduling, scheduling with duplication, precedence-constrained jobs, graph algorithms} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Shiri Antaki, Quanquan C. Liu, and Shay Solomon. Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 7:1-7:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{antaki_et_al:LIPIcs.ITCS.2022.7, author = {Antaki, Shiri and Liu, Quanquan C. and Solomon, Shay}, title = {{Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {7:1--7:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.7}, URN = {urn:nbn:de:0030-drops-156039}, doi = {10.4230/LIPIcs.ITCS.2022.7}, annote = {Keywords: dynamic graph algorithms, distributed algorithms, symmetry breaking problems, maximal independent set, matching, coloring} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Lili Su, Quanquan C. Liu, and Neha Narula. The Power of Random Symmetry-Breaking in Nakamoto Consensus. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 39:1-39:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{su_et_al:LIPIcs.DISC.2021.39, author = {Su, Lili and Liu, Quanquan C. and Narula, Neha}, title = {{The Power of Random Symmetry-Breaking in Nakamoto Consensus}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {39:1--39: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.39}, URN = {urn:nbn:de:0030-drops-148413}, doi = {10.4230/LIPIcs.DISC.2021.39}, annote = {Keywords: Nakamoto consensus, Byzantine consensus, blockchain, symmetry-breaking, coalescing random walks} }
Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)
Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch. Tatamibari Is NP-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 1:1-1:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{adler_et_al:LIPIcs.FUN.2021.1, author = {Adler, Aviv and Bosboom, Jeffrey and Demaine, Erik D. and Demaine, Martin L. and Liu, Quanquan C. and Lynch, Jayson}, title = {{Tatamibari Is NP-Complete}}, booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)}, pages = {1:1--1:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-145-0}, ISSN = {1868-8969}, year = {2020}, volume = {157}, editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.1}, URN = {urn:nbn:de:0030-drops-127624}, doi = {10.4230/LIPIcs.FUN.2021.1}, annote = {Keywords: Nikoli puzzles, NP-hardness, rectangle covering} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, and Andrew van der Poel. Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 37:1-37:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{demaine_et_al:LIPIcs.ESA.2019.37, author = {Demaine, Erik D. and Goodrich, Timothy D. and Kloster, Kyle and Lavallee, Brian and Liu, Quanquan C. and Sullivan, Blair D. and Vakilian, Ali and van der Poel, Andrew}, title = {{Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {37:1--37:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.37}, URN = {urn:nbn:de:0030-drops-111583}, doi = {10.4230/LIPIcs.ESA.2019.37}, annote = {Keywords: structural rounding, graph editing, approximation algorithms} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Virginia Vassilevska Williams. Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 34:1-34:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.ITCS.2018.34, author = {Demaine, Erik D. and Lincoln, Andrea and Liu, Quanquan C. and Lynch, Jayson and Vassilevska Williams, Virginia}, title = {{Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {34:1--34:23}, 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.34}, URN = {urn:nbn:de:0030-drops-83335}, doi = {10.4230/LIPIcs.ITCS.2018.34}, annote = {Keywords: IO model, Fine-grained Complexity, Algorithms} }
Feedback for Dagstuhl Publishing