Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, and Samson Zhou. Differentially Private Aggregation via Imperfect Shuffling. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 17:1-17:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ghazi_et_al:LIPIcs.ITC.2023.17, author = {Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin and Nelson, Jelani and Zhou, Samson}, title = {{Differentially Private Aggregation via Imperfect Shuffling}}, booktitle = {4th Conference on Information-Theoretic Cryptography (ITC 2023)}, pages = {17:1--17:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-271-6}, ISSN = {1868-8969}, year = {2023}, volume = {267}, editor = {Chung, Kai-Min}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.17}, URN = {urn:nbn:de:0030-drops-183453}, doi = {10.4230/LIPIcs.ITC.2023.17}, annote = {Keywords: Differential privacy, private summation, shuffle model} }
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 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Thomas Steinke. Algorithms with More Granular Differential Privacy Guarantees. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 54:1-54:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ghazi_et_al:LIPIcs.ITCS.2023.54, author = {Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin and Steinke, Thomas}, title = {{Algorithms with More Granular Differential Privacy Guarantees}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {54:1--54:24}, 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.54}, URN = {urn:nbn:de:0030-drops-175574}, doi = {10.4230/LIPIcs.ITCS.2023.54}, annote = {Keywords: Differential Privacy, Algorithms, Per-Attribute Privacy} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Badih Ghazi, Ravi Kumar, Jelani Nelson, and Pasin Manurangsi. Private Counting of Distinct and k-Occurring Items in Time Windows. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 55:1-55:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ghazi_et_al:LIPIcs.ITCS.2023.55, author = {Ghazi, Badih and Kumar, Ravi and Nelson, Jelani and Manurangsi, Pasin}, title = {{Private Counting of Distinct and k-Occurring Items in Time Windows}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {55:1--55:24}, 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.55}, URN = {urn:nbn:de:0030-drops-175580}, doi = {10.4230/LIPIcs.ITCS.2023.55}, annote = {Keywords: Differential Privacy, Algorithms, Distinct Elements, Time Windows} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Pasin Manurangsi. Improved Inapproximability of VC Dimension and Littlestone’s Dimension via (Unbalanced) Biclique. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 85:1-85:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{manurangsi:LIPIcs.ITCS.2023.85, author = {Manurangsi, Pasin}, title = {{Improved Inapproximability of VC Dimension and Littlestone’s Dimension via (Unbalanced) Biclique}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {85:1--85:18}, 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.85}, URN = {urn:nbn:de:0030-drops-175884}, doi = {10.4230/LIPIcs.ITCS.2023.85}, annote = {Keywords: VC Dimension, Littlestone’s Dimension, Maximum Biclique, Hardness of Approximation, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi. Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 7:1-7:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{abboud_et_al:LIPIcs.ICALP.2022.7, author = {Abboud, Amir and Cohen-Addad, Vincent and Lee, Euiwoong and Manurangsi, Pasin}, title = {{Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.7}, URN = {urn:nbn:de:0030-drops-163481}, doi = {10.4230/LIPIcs.ICALP.2022.7}, annote = {Keywords: Approximation Algorithms, Complexity, Data Mining, Diversification} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Chien-Chung Huang and François Sellier. Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 27:1-27:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{huang_et_al:LIPIcs.SWAT.2022.27, author = {Huang, Chien-Chung and Sellier, Fran\c{c}ois}, title = {{Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.27}, URN = {urn:nbn:de:0030-drops-161874}, doi = {10.4230/LIPIcs.SWAT.2022.27}, annote = {Keywords: Maximum vertex cover, matroid, approximate kernel, streaming} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Martin Hoefer, Pasin Manurangsi, and Alexandros Psomas. Algorithmic Persuasion with Evidence. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 3:1-3:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{hoefer_et_al:LIPIcs.ITCS.2021.3, author = {Hoefer, Martin and Manurangsi, Pasin and Psomas, Alexandros}, title = {{Algorithmic Persuasion with Evidence}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {3:1--3:20}, 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.3}, URN = {urn:nbn:de:0030-drops-135420}, doi = {10.4230/LIPIcs.ITCS.2021.3}, annote = {Keywords: Bayesian Persuasion, Semidefinite Programming, Approximation Algorithms} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm. The Strongish Planted Clique Hypothesis and Its Consequences. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 10:1-10:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{manurangsi_et_al:LIPIcs.ITCS.2021.10, author = {Manurangsi, Pasin and Rubinstein, Aviad and Schramm, Tselil}, title = {{The Strongish Planted Clique Hypothesis and Its Consequences}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {10:1--10:21}, 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.10}, URN = {urn:nbn:de:0030-drops-135491}, doi = {10.4230/LIPIcs.ITCS.2021.10}, annote = {Keywords: Planted Clique, Densest k-Subgraph, Hardness of Approximation} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman. Tight Hardness Results for Training Depth-2 ReLU Networks. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 22:1-22:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{goel_et_al:LIPIcs.ITCS.2021.22, author = {Goel, Surbhi and Klivans, Adam and Manurangsi, Pasin and Reichman, Daniel}, title = {{Tight Hardness Results for Training Depth-2 ReLU Networks}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {22:1--22: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.22}, URN = {urn:nbn:de:0030-drops-135611}, doi = {10.4230/LIPIcs.ITCS.2021.22}, annote = {Keywords: ReLU, Learning Algorithm, Running Time Lower Bound} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Lijie Chen, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. On Distributed Differential Privacy and Counting Distinct Elements. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 56:1-56:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.ITCS.2021.56, author = {Chen, Lijie and Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin}, title = {{On Distributed Differential Privacy and Counting Distinct Elements}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {56:1--56:18}, 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.56}, URN = {urn:nbn:de:0030-drops-135953}, doi = {10.4230/LIPIcs.ITCS.2021.56}, annote = {Keywords: Differential Privacy, Shuffle Model} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Amey Bhangale, Diptarka Chakraborty, and Rajendra Kumar. Hardness of Approximation of (Multi-)LCS over Small Alphabet. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 38:1-38:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhangale_et_al:LIPIcs.APPROX/RANDOM.2020.38, author = {Bhangale, Amey and Chakraborty, Diptarka and Kumar, Rajendra}, title = {{Hardness of Approximation of (Multi-)LCS over Small Alphabet}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {38:1--38:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.38}, URN = {urn:nbn:de:0030-drops-126418}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.38}, annote = {Keywords: Longest common subsequence, Hardness of approximation, ETH-hardness, Densest k-subgraph problem} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang. On the Quantum Complexity of Closest Pair and Related Problems. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 16:1-16:43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2020.16, author = {Aaronson, Scott and Chia, Nai-Hui and Lin, Han-Hsuan and Wang, Chunhao and Zhang, Ruizhe}, title = {{On the Quantum Complexity of Closest Pair and Related Problems}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {16:1--16:43}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.16}, URN = {urn:nbn:de:0030-drops-125681}, doi = {10.4230/LIPIcs.CCC.2020.16}, annote = {Keywords: Closest pair, Quantum computing, Quantum fine grained reduction, Quantum strong exponential time hypothesis, Fine grained complexity} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Pure Differentially Private Summation from Anonymous Messages. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 15:1-15:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{ghazi_et_al:LIPIcs.ITC.2020.15, author = {Ghazi, Badih and Golowich, Noah and Kumar, Ravi and Manurangsi, Pasin and Pagh, Rasmus and Velingker, Ameya}, title = {{Pure Differentially Private Summation from Anonymous Messages}}, booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)}, pages = {15:1--15:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-151-1}, ISSN = {1868-8969}, year = {2020}, volume = {163}, editor = {Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.15}, URN = {urn:nbn:de:0030-drops-121208}, doi = {10.4230/LIPIcs.ITC.2020.15}, annote = {Keywords: Pure differential privacy, Shuffled model, Anonymous messages, Summation, Communication bounds} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Rajesh Chitnis and Andreas Emil Feldmann. FPT Inapproximability of Directed Cut and Connectivity Problems. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 8:1-8:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{chitnis_et_al:LIPIcs.IPEC.2019.8, author = {Chitnis, Rajesh and Feldmann, Andreas Emil}, title = {{FPT Inapproximability of Directed Cut and Connectivity Problems}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.8}, URN = {urn:nbn:de:0030-drops-114692}, doi = {10.4230/LIPIcs.IPEC.2019.8}, annote = {Keywords: Directed graphs, cuts, connectivity, Steiner problems, FPT inapproximability} }
Feedback for Dagstuhl Publishing