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 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-dev.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 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar. On Multilinear Forms: Bias, Correlation, and Tensor Rank. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 29:1-29:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhrushundi_et_al:LIPIcs.APPROX/RANDOM.2020.29, author = {Bhrushundi, Abhishek and Harsha, Prahladh and Hatami, Pooya and Kopparty, Swastik and Kumar, Mrinal}, title = {{On Multilinear Forms: Bias, Correlation, and Tensor Rank}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {29:1--29:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.29}, URN = {urn:nbn:de:0030-drops-126325}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.29}, annote = {Keywords: polynomials, Boolean functions, tensor rank, bias, correlation} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Dean Doron, Pooya Hatami, and William M. Hoza. Log-Seed Pseudorandom Generators via Iterated Restrictions. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 6:1-6:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{doron_et_al:LIPIcs.CCC.2020.6, author = {Doron, Dean and Hatami, Pooya and Hoza, William M.}, title = {{Log-Seed Pseudorandom Generators via Iterated Restrictions}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {6:1--6:36}, 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.6}, URN = {urn:nbn:de:0030-drops-125586}, doi = {10.4230/LIPIcs.CCC.2020.6}, annote = {Keywords: Pseudorandom generators, Pseudorandom restrictions, Read-once depth-2 formulas, Parity gates} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Kuan Cheng and William M. Hoza. Hitting Sets Give Two-Sided Derandomization of Small Space. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cheng_et_al:LIPIcs.CCC.2020.10, author = {Cheng, Kuan and Hoza, William M.}, title = {{Hitting Sets Give Two-Sided Derandomization of Small Space}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {10:1--10:25}, 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.10}, URN = {urn:nbn:de:0030-drops-125625}, doi = {10.4230/LIPIcs.CCC.2020.10}, annote = {Keywords: hitting sets, derandomization, read-once branching programs} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Chin Ho Lee. Fourier Bounds and Pseudorandom Generators for Product Tests. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lee:LIPIcs.CCC.2019.7, author = {Lee, Chin Ho}, title = {{Fourier Bounds and Pseudorandom Generators for Product Tests}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {7:1--7:25}, 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.7}, URN = {urn:nbn:de:0030-drops-108296}, doi = {10.4230/LIPIcs.CCC.2019.7}, annote = {Keywords: bounded independence plus noise, Fourier spectrum, product test, pseudorandom generators} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Dean Doron, Pooya Hatami, and William M. Hoza. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 16:1-16:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{doron_et_al:LIPIcs.CCC.2019.16, author = {Doron, Dean and Hatami, Pooya and Hoza, William M.}, title = {{Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {16:1--16:34}, 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.16}, URN = {urn:nbn:de:0030-drops-108382}, doi = {10.4230/LIPIcs.CCC.2019.16}, annote = {Keywords: Pseudorandom generators, Constant-depth formulas, Explicit constructions} }
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-dev.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 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal. Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2019.22, author = {Chattopadhyay, Eshan and Hatami, Pooya and Lovett, Shachar and Tal, Avishay}, title = {{Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {22:1--22:15}, 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.22}, URN = {urn:nbn:de:0030-drops-101150}, doi = {10.4230/LIPIcs.ITCS.2019.22}, annote = {Keywords: Derandomization, Pseudorandom generator, Explicit construction, Random walk, Small-depth circuits with parity gates} }
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} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Pooya Hatami and Avishay Tal. Pseudorandom Generators for Low Sensitivity Functions. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{hatami_et_al:LIPIcs.ITCS.2018.29, author = {Hatami, Pooya and Tal, Avishay}, title = {{Pseudorandom Generators for Low Sensitivity Functions}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {29:1--29:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.29}, URN = {urn:nbn:de:0030-drops-83300}, doi = {10.4230/LIPIcs.ITCS.2018.29}, annote = {Keywords: Pseudorandom Generators, Sensitivity, Sensitivity Conjecture} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Shalev Ben-David, Pooya Hatami, and Avishay Tal. Low-Sensitivity Functions from Unambiguous Certificates. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 28:1-28:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bendavid_et_al:LIPIcs.ITCS.2017.28, author = {Ben-David, Shalev and Hatami, Pooya and Tal, Avishay}, title = {{Low-Sensitivity Functions from Unambiguous Certificates}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {28:1--28:23}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.28}, URN = {urn:nbn:de:0030-drops-81869}, doi = {10.4230/LIPIcs.ITCS.2017.28}, annote = {Keywords: Boolean functions, decision tree complexity, query complexity, sensitivity conjecture} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Pooya Hatami. On the Structure of Quintic Polynomials. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{hatami:LIPIcs.APPROX-RANDOM.2016.33, author = {Hatami, Pooya}, title = {{On the Structure of Quintic Polynomials}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {33:1--33:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.33}, URN = {urn:nbn:de:0030-drops-66569}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.33}, annote = {Keywords: Higher-order Fourier analysis, Structure Theorem, Polynomials, Regularity lemmas} }
Feedback for Dagstuhl Publishing