Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, and Morgan Shirley. Separation of the Factorization Norm and Randomized Communication Complexity. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cheung_et_al:LIPIcs.CCC.2023.1, author = {Cheung, Tsun-Ming and Hatami, Hamed and Hosseini, Kaave and Shirley, Morgan}, title = {{Separation of the Factorization Norm and Randomized Communication Complexity}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {1:1--1:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.1}, URN = {urn:nbn:de:0030-drops-182714}, doi = {10.4230/LIPIcs.CCC.2023.1}, annote = {Keywords: Factorization norms, randomized communication complexity} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami, and Kaave Hosseini. Online Learning and Disambiguations of Partial Concept Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cheung_et_al:LIPIcs.ICALP.2023.42, author = {Cheung, Tsun-Ming and Hatami, Hamed and Hatami, Pooya and Hosseini, Kaave}, title = {{Online Learning and Disambiguations of Partial Concept Classes}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {42:1--42:13}, 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.42}, URN = {urn:nbn:de:0030-drops-180946}, doi = {10.4230/LIPIcs.ICALP.2023.42}, annote = {Keywords: Online learning, Littlestone dimension, VC dimension, partial concept class, clique vs independent set, Alon-Saks-Seymour conjecture, Standard Optimal Algorithm, PAC learning} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao. Lower Bound Methods for Sign-Rank and Their Limitations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 22:1-22:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hatami_et_al:LIPIcs.APPROX/RANDOM.2022.22, author = {Hatami, Hamed and Hatami, Pooya and Pires, William and Tao, Ran and Zhao, Rosie}, title = {{Lower Bound Methods for Sign-Rank and Their Limitations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {22:1--22:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.22}, URN = {urn:nbn:de:0030-drops-171445}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.22}, annote = {Keywords: Average Margin, Communication complexity, margin complexity, monochromatic rectangle, Sign-rank, Unbounded-error communication complexity, VC-dimension} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Sign Rank vs Discrepancy. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hatami_et_al:LIPIcs.CCC.2020.18, author = {Hatami, Hamed and Hosseini, Kaave and Lovett, Shachar}, title = {{Sign Rank vs Discrepancy}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {18:1--18:14}, 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.18}, URN = {urn:nbn:de:0030-drops-125700}, doi = {10.4230/LIPIcs.CCC.2020.18}, annote = {Keywords: Discrepancy, sign rank, Unbounded-error communication complexity, weakly unbounded error communication complexity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, and David Zuckerman. Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{filmus_et_al:LIPIcs.ICALP.2019.58, author = {Filmus, Yuval and Hambardzumyan, Lianna and Hatami, Hamed and Hatami, Pooya and Zuckerman, David}, title = {{Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {58:1--58:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.58}, URN = {urn:nbn:de:0030-drops-106340}, doi = {10.4230/LIPIcs.ICALP.2019.58}, annote = {Keywords: Boolean function analysis, coin flipping} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li. Trading Information Complexity for Error. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 16:1-16:59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{dagan_et_al:LIPIcs.CCC.2017.16, author = {Dagan, Yuval and Filmus, Yuval and Hatami, Hamed and Li, Yaqiao}, title = {{Trading Information Complexity for Error}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {16:1--16:59}, 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.16}, URN = {urn:nbn:de:0030-drops-75179}, doi = {10.4230/LIPIcs.CCC.2017.16}, annote = {Keywords: communication complexity, information complexity} }
Feedback for Dagstuhl Publishing