LIPIcs, Volume 4
FSTTCS 2009, December 15-17, 2009, Kanpur, India
Editors: Ravi Kannan and K. Narayan Kumar
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 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Nikhil Bansal and Christian Coester. Online Metric Allocation and Time-Varying Regularization. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bansal_et_al:LIPIcs.ESA.2022.13, author = {Bansal, Nikhil and Coester, Christian}, title = {{Online Metric Allocation and Time-Varying Regularization}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.13}, URN = {urn:nbn:de:0030-drops-169515}, doi = {10.4230/LIPIcs.ESA.2022.13}, annote = {Keywords: Online algorithms, competitive analysis, k-server, metrical task systems, mirror descent, regularization} }
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 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 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Manuel Fernández V, David P. Woodruff, and Taisuke Yasuda. The Query Complexity of Mastermind with l_p Distances. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 1:1-1:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fernandezv_et_al:LIPIcs.APPROX-RANDOM.2019.1, author = {Fern\'{a}ndez V, Manuel and Woodruff, David P. and Yasuda, Taisuke}, title = {{The Query Complexity of Mastermind with l\underlinep Distances}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {1:1--1:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.1}, URN = {urn:nbn:de:0030-drops-112165}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.1}, annote = {Keywords: Mastermind, Query Complexity, l\underlinep Distance} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee. Semi-Online Bipartite Matching. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kumar_et_al:LIPIcs.ITCS.2019.50, author = {Kumar, Ravi and Purohit, Manish and Schild, Aaron and Svitkina, Zoya and Vee, Erik}, title = {{Semi-Online Bipartite Matching}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {50:1--50:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.50}, URN = {urn:nbn:de:0030-drops-101436}, doi = {10.4230/LIPIcs.ITCS.2019.50}, annote = {Keywords: Semi-Online Algorithms, Bipartite Matching} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt, and José Verschae. A Local-Search Algorithm for Steiner Forest. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gro_et_al:LIPIcs.ITCS.2018.31, author = {Gro{\ss}, Martin and Gupta, Anupam and Kumar, Amit and Matuschke, Jannik and Schmidt, Daniel R. and Schmidt, Melanie and Verschae, Jos\'{e}}, title = {{A Local-Search Algorithm for Steiner Forest}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {31:1--31:17}, 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.31}, URN = {urn:nbn:de:0030-drops-83134}, doi = {10.4230/LIPIcs.ITCS.2018.31}, annote = {Keywords: Local Search, Steiner Forest, Approximation Algorithms, Network Design} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Erisa Terolli. The Distortion of Locality Sensitive Hashing. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chierichetti_et_al:LIPIcs.ITCS.2017.54, author = {Chierichetti, Flavio and Kumar, Ravi and Panconesi, Alessandro and Terolli, Erisa}, title = {{The Distortion of Locality Sensitive Hashing}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {54:1--54:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.54}, URN = {urn:nbn:de:0030-drops-81688}, doi = {10.4230/LIPIcs.ITCS.2017.54}, annote = {Keywords: locality sensitive hashing, distortion, similarity} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, and Silvio Lattanzi. On Reconstructing a Hidden Permutation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 604-617, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{chierichetti_et_al:LIPIcs.APPROX-RANDOM.2014.604, author = {Chierichetti, Flavio and Dasgupta, Anirban and Kumar, Ravi and Lattanzi, Silvio}, title = {{On Reconstructing a Hidden Permutation}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {604--617}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.604}, URN = {urn:nbn:de:0030-drops-47251}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.604}, annote = {Keywords: Mallows model; Rank aggregation; Reconstruction} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@Proceedings{kannan_et_al:LIPIcs.FSTTCS.2009, title = {{LIPIcs, Volume 4, FSTTCS'09, Complete Volume}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2013}, 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}, URN = {urn:nbn:de:0030-drops-40987}, doi = {10.4230/LIPIcs.FSTTCS.2009}, annote = {Keywords: LIPIcs, Volume 4, FSTTCS'09, Complete Volume} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. i-vii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{kannan_et_al:LIPIcs.FSTTCS.2009.2341, author = {Kannan, Ravi and Narayan Kumar, K.}, title = {{Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {i--vii}, 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.2341}, URN = {urn:nbn:de:0030-drops-23415}, doi = {10.4230/LIPIcs.FSTTCS.2009.2341}, annote = {Keywords: Preface, proceedings, FSTTCS, referees, programme committee, organising committee} }
Feedback for Dagstuhl Publishing