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 169, 35th Computational Complexity Conference (CCC 2020)
Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis. On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 19:1-19:42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{goos_et_al:LIPIcs.CCC.2020.19, author = {G\"{o}\"{o}s, Mika and Kamath, Pritish and Sotiraki, Katerina and Zampetakis, Manolis}, title = {{On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {19:1--19:42}, 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.19}, URN = {urn:nbn:de:0030-drops-125712}, doi = {10.4230/LIPIcs.CCC.2020.19}, annote = {Keywords: Total NP Search Problems, Modulo-q arguments, Chevalley - Warning Theorem} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson. Approximate Degree, Secret Sharing, and Concentration Phenomena. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 71:1-71:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bogdanov_et_al:LIPIcs.APPROX-RANDOM.2019.71, author = {Bogdanov, Andrej and Mande, Nikhil S. and Thaler, Justin and Williamson, Christopher}, title = {{Approximate Degree, Secret Sharing, and Concentration Phenomena}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {71:1--71:21}, 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.71}, URN = {urn:nbn:de:0030-drops-112869}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.71}, annote = {Keywords: approximate degree, dual polynomial, pseudorandomness, polynomial approximation, secret sharing} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in Monotone Complexity and TFNP. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{goos_et_al:LIPIcs.ITCS.2019.38, author = {G\"{o}\"{o}s, Mika and Kamath, Pritish and Robere, Robert and Sokolov, Dmitry}, title = {{Adventures in Monotone Complexity and TFNP}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {38:1--38:19}, 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.38}, URN = {urn:nbn:de:0030-drops-101316}, doi = {10.4230/LIPIcs.ITCS.2019.38}, annote = {Keywords: TFNP, Monotone Complexity, Communication Complexity, Proof Complexity} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Badih Ghazi, Pritish Kamath, and Prasad Raghavendra. Dimension Reduction for Polynomials over Gaussian Space and Applications. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 28:1-28:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ghazi_et_al:LIPIcs.CCC.2018.28, author = {Ghazi, Badih and Kamath, Pritish and Raghavendra, Prasad}, title = {{Dimension Reduction for Polynomials over Gaussian Space and Applications}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {28:1--28:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.28}, URN = {urn:nbn:de:0030-drops-88616}, doi = {10.4230/LIPIcs.CCC.2018.28}, annote = {Keywords: Dimension reduction, Low-degree Polynomials, Noise Stability, Non-Interactive Simulation} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Badih Ghazi, Elad Haramaty, Pritish Kamath, and Madhu Sudan. Compression in a Distributed Setting. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{ghazi_et_al:LIPIcs.ITCS.2017.19, author = {Ghazi, Badih and Haramaty, Elad and Kamath, Pritish and Sudan, Madhu}, title = {{Compression in a Distributed Setting}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {19:1--19:22}, 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.19}, URN = {urn:nbn:de:0030-drops-81763}, doi = {10.4230/LIPIcs.ITCS.2017.19}, annote = {Keywords: Distributed Compression, Communication, Language Evolution, Isolating Hash Families} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Mika Göös, Pritish Kamath, Toniann Pitassi, and Thomas Watson. Query-to-Communication Lifting for P^NP. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{goos_et_al:LIPIcs.CCC.2017.12, author = {G\"{o}\"{o}s, Mika and Kamath, Pritish and Pitassi, Toniann and Watson, Thomas}, title = {{Query-to-Communication Lifting for P^NP}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {12:1--12:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.12}, URN = {urn:nbn:de:0030-drops-75388}, doi = {10.4230/LIPIcs.CCC.2017.12}, annote = {Keywords: Communication Complexity, Query Complexity, Lifting Theorem, P^NP} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Bernhard Haeupler, Pritish Kamath, and Ameya Velingker. Communication with Partial Noiseless Feedback. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 881-897, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{haeupler_et_al:LIPIcs.APPROX-RANDOM.2015.881, author = {Haeupler, Bernhard and Kamath, Pritish and Velingker, Ameya}, title = {{Communication with Partial Noiseless Feedback}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {881--897}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.881}, URN = {urn:nbn:de:0030-drops-53426}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.881}, annote = {Keywords: Communication with feedback, Interactive communication, Coding theory Digital} }
Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)
Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath. Faster Algorithms for Alternating Refinement Relations. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 167-182, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{chatterjee_et_al:LIPIcs.CSL.2012.167, author = {Chatterjee, Krishnendu and Chaubal, Siddhesh and Kamath, Pritish}, title = {{Faster Algorithms for Alternating Refinement Relations}}, booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL}, pages = {167--182}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-42-2}, ISSN = {1868-8969}, year = {2012}, volume = {16}, editor = {C\'{e}gielski, Patrick and Durand, Arnaud}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.167}, URN = {urn:nbn:de:0030-drops-36713}, doi = {10.4230/LIPIcs.CSL.2012.167}, annote = {Keywords: Simulation and fair simulation, Alternating simulation, Graph games} }
Feedback for Dagstuhl Publishing