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-dev.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-dev.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 234, 37th Computational Complexity Conference (CCC 2022)
Ivan Mihajlin and Anastasia Sofronova. A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{mihajlin_et_al:LIPIcs.CCC.2022.13, author = {Mihajlin, Ivan and Sofronova, Anastasia}, title = {{A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {13:1--13:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.13}, URN = {urn:nbn:de:0030-drops-165755}, doi = {10.4230/LIPIcs.CCC.2022.13}, annote = {Keywords: formula complexity, communication complexity, Karchmer-Raz-Wigderson conjecture, De Morgan formulas} }
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-dev.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 137, 34th Computational Complexity Conference (CCC 2019)
Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of Linear Sketching Under Modular Updates. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hosseini_et_al:LIPIcs.CCC.2019.13, author = {Hosseini, Kaave and Lovett, Shachar and Yaroslavtsev, Grigory}, title = {{Optimality of Linear Sketching Under Modular Updates}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.13}, URN = {urn:nbn:de:0030-drops-108355}, doi = {10.4230/LIPIcs.CCC.2019.13}, annote = {Keywords: communication complexity, linear sketching, streaming algorithm} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, and Sankeerth Rao. Torus Polynomials: An Algebraic Approach to ACC Lower Bounds. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bhrushundi_et_al:LIPIcs.ITCS.2019.13, author = {Bhrushundi, Abhishek and Hosseini, Kaave and Lovett, Shachar and Rao, Sankeerth}, title = {{Torus Polynomials: An Algebraic Approach to ACC Lower Bounds}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {13:1--13:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.13}, URN = {urn:nbn:de:0030-drops-101066}, doi = {10.4230/LIPIcs.ITCS.2019.13}, annote = {Keywords: Circuit complexity, ACC, lower bounds, polynomials} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. Pseudorandom Generators from Polarizing Random Walks. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2018.1, author = {Chattopadhyay, Eshan and Hatami, Pooya and Hosseini, Kaave and Lovett, Shachar}, title = {{Pseudorandom Generators from Polarizing Random Walks}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {1:1--1:21}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.1}, URN = {urn:nbn:de:0030-drops-88880}, doi = {10.4230/LIPIcs.CCC.2018.1}, annote = {Keywords: AC0, branching program, polarization, pseudorandom generators, random walks, Sensitivity} }
Feedback for Dagstuhl Publishing