Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The Discrepancy of Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.27, author = {Bodwin, Greg and Deng, Chengyuan and Gao, Jie and Hoppenworth, Gary and Upadhyay, Jalaj and Wang, Chen}, title = {{The Discrepancy of Shortest Paths}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {27:1--27:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.27}, URN = {urn:nbn:de:0030-drops-201705}, doi = {10.4230/LIPIcs.ICALP.2024.27}, annote = {Keywords: Discrepancy, hereditary discrepancy, shortest paths, differential privacy} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Gal Beniamini. The Approximate Degree of Bipartite Perfect Matching. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 1:1-1:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{beniamini:LIPIcs.CCC.2022.1, author = {Beniamini, Gal}, title = {{The Approximate Degree of Bipartite Perfect Matching}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {1:1--1:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.1}, URN = {urn:nbn:de:0030-drops-165634}, doi = {10.4230/LIPIcs.CCC.2022.1}, annote = {Keywords: Bipartite Perfect Matching, Boolean Functions, Approximate Degree} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Nati Linial and Adi Shraibman. An Improved Protocol for the Exactly-N Problem. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 2:1-2:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{linial_et_al:LIPIcs.CCC.2021.2, author = {Linial, Nati and Shraibman, Adi}, title = {{An Improved Protocol for the Exactly-N Problem}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {2:1--2:8}, 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.2}, URN = {urn:nbn:de:0030-drops-142760}, doi = {10.4230/LIPIcs.CCC.2021.2}, annote = {Keywords: Communication complexity, Number-On-the-Forehead, Corner-free sets} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Nati Linial, Toniann Pitassi, and Adi Shraibman. On the Communication Complexity of High-Dimensional Permutations. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 54:1-54:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{linial_et_al:LIPIcs.ITCS.2019.54, author = {Linial, Nati and Pitassi, Toniann and Shraibman, Adi}, title = {{On the Communication Complexity of High-Dimensional Permutations}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {54:1--54: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.54}, URN = {urn:nbn:de:0030-drops-101470}, doi = {10.4230/LIPIcs.ITCS.2019.54}, annote = {Keywords: High dimensional permutations, Number On the Forehead model, Additive combinatorics} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Yonatan Bilu, Amit Daniely, Nati Linial, and Michael Saks. On the practically interesting instances of MAXCUT. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 526-537, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{bilu_et_al:LIPIcs.STACS.2013.526, author = {Bilu, Yonatan and Daniely, Amit and Linial, Nati and Saks, Michael}, title = {{On the practically interesting instances of MAXCUT}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {526--537}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.526}, URN = {urn:nbn:de:0030-drops-39625}, doi = {10.4230/LIPIcs.STACS.2013.526}, annote = {Keywords: MAXCUT, Clustering, Hardness in practice, Stability, Non worst-case analysis} }
Feedback for Dagstuhl Publishing