Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. On Differentially Private Counting on Trees. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 66:1-66:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ghazi_et_al:LIPIcs.ICALP.2023.66, author = {Ghazi, Badih and Kamath, Pritish and Kumar, Ravi and Manurangsi, Pasin and Wu, Kewen}, title = {{On Differentially Private Counting on Trees}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {66:1--66:18}, 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.66}, URN = {urn:nbn:de:0030-drops-181186}, doi = {10.4230/LIPIcs.ICALP.2023.66}, annote = {Keywords: Differential Privacy, Algorithms, Trees, Hierarchies} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Uma Girish, Avishay Tal, and Kewen Wu. Fourier Growth of Parity Decision Trees. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 39:1-39:36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{girish_et_al:LIPIcs.CCC.2021.39, author = {Girish, Uma and Tal, Avishay and Wu, Kewen}, title = {{Fourier Growth of Parity Decision Trees}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {39:1--39:36}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.39}, URN = {urn:nbn:de:0030-drops-143137}, doi = {10.4230/LIPIcs.CCC.2021.39}, annote = {Keywords: Fourier analysis of Boolean functions, noisy decision tree, parity decision tree, query complexity} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Ce Jin, Jelani Nelson, and Kewen Wu. An Improved Sketching Algorithm for Edit Distance. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 45:1-45:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{jin_et_al:LIPIcs.STACS.2021.45, author = {Jin, Ce and Nelson, Jelani and Wu, Kewen}, title = {{An Improved Sketching Algorithm for Edit Distance}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {45:1--45:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.45}, URN = {urn:nbn:de:0030-drops-136905}, doi = {10.4230/LIPIcs.STACS.2021.45}, annote = {Keywords: edit distance, sketching} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Benjamin Rossman. Shrinkage of Decision Lists and DNF Formulas. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 70:1-70:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{rossman:LIPIcs.ITCS.2021.70, author = {Rossman, Benjamin}, title = {{Shrinkage of Decision Lists and DNF Formulas}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {70:1--70:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.70}, URN = {urn:nbn:de:0030-drops-136098}, doi = {10.4230/LIPIcs.ITCS.2021.70}, annote = {Keywords: shrinkage, decision lists, DNF formulas} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, and Yufan Zheng. On the Degree of Boolean Functions as Polynomials over ℤ_m. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 100:1-100:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{sun_et_al:LIPIcs.ICALP.2020.100, author = {Sun, Xiaoming and Sun, Yuan and Wang, Jiaheng and Wu, Kewen and Xia, Zhiyu and Zheng, Yufan}, title = {{On the Degree of Boolean Functions as Polynomials over \mathbb{Z}\underlinem}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {100:1--100: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.100}, URN = {urn:nbn:de:0030-drops-125070}, doi = {10.4230/LIPIcs.ICALP.2020.100}, annote = {Keywords: Boolean function, polynomial, modular degree, Ramsey theory} }
Feedback for Dagstuhl Publishing