Kaave Hosseini

I am an Assistant Professor in the Department of Computer Science at the University of Rochester. Previously I was a Postdoctoral Associate in the Department of Mathematical Sciences at Carnegie Mellon University. I obtained my Ph.D. in Computer Science from UC San Diego under the supervision of Shachar Lovett. Before that, I did my BSc in Mathematics and Computer Science at Sharif University of Technology, Tehran.

I am interested in theoretical computer science and additive combinatorics. Usually, the problems I work on have to do with approximate algebraic structure and/or pseudorandomness.

Upcoming Event:

Teaching:

Current:
CSC 484/284: Advanced Algorithms - Fall 2024

Past:
At U of R:
CSC 484/284: Advanced Algorithms - Fall 2023
CSC 280/480: Computer Models and Limitations - Fall 2023
CSC/MATH 488/288: Analytic Methods in Computer Science - Fall 2022
CSC 480/280: Computer Models and Limitations - Fall 2022
CSC 488/288: Analytic Methods in Computer Science - Fall 2021
At CMU:
21-111 Differential Calculus - Spring 2021
21-301 Combinatorics (co-taught with Alan Frieze) - Fall 2020
21-301 Combinatorics - Spring 2020
21-325 Probability - Spring 2020

Publications:

[C]: Conference [J]: Journal

    Sparse graph counting and Kelley-Meka bounds for binary systems
    		Arxiv
    with Yuval Filmus, Hamed Hatami, Esty Kellman
    65th IEEE Symposium on Foundations of Computer Science (FOCS) 2024.
    Refuting approaches to the log-rank conjecture for XOR functions
    		ECCC
    with Hamed Hatami, Shachar Lovett, Anthony Ostuni
    [C] 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP) 2024.
    Online Learning and Disambiguations of Partial Concept Classes
    		Arxiv
    with Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami
    [C] 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP) 2023. Best paper award.
    Separation of the factorization norm and randomized communication complexity
    		ECCC
    with Tsun-Ming Cheung, Hamed Hatami, Morgan Shirley
    [C] 38th Computational Complexity Conference (CCC) 2023.
    A Borsuk-Ulam lower bound for sign-rank and its applications
    		ECCC
    with Hamed Hatami, Xiang Meng.
    [C] 55th ACM Symposium on Theory of Computing (STOC) 2023.
    Sign rank vs. Discrepancy
    		ECCC
    with Hamed Hatami, Shachar Lovett.
    [J] Theory of Computing; CCC2020 Special Issue 18 (1), 1-22. July 2022
    [C] 35th Computational Complexity Conference (CCC) 2020. Invited to ToC Special Issue for CCC2020.
    XOR Lemmas for Resilient Functions Against Polynomials
    		ECCC
    with Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, David Zuckerman.
    [C] 52nd Annual ACM Symposium on Theory of Computing (STOC) 2020.
    Optimality of Linear Sketching under Modular Updates
    		Arxiv
    with Shachar Lovett, Grigory Yaroslavtsev.
    [C] 34th Computational Complexity Conference (CCC) 2019.
    A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds
    		Arxiv
    with Shachar Lovett.
    [J] Discrete Analysis. 2019:10, 14 pp. June 2019
    Torus polynomials: an algebraic approach to ACC lower bounds
    		 ECCC
    with Abhishek Bhrushundi, Shachar Lovett, Sankeerth Rao.
    [C] 10th Innovations in Theoretical Computer Science Conference (ITCS) 2019.
    Pseudorandom generators from polarizing random walks
    		ECCC
    with Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett.
    [J] Theory of Computing; CCC2018 Special Issue 15 (1), 1-26. October 2019
    [C] 33rd Computational Complexity Conference (CCC) 2018. Invited to ToC Special Issue for CCC2018.
    Structure of protocols for XOR functions
    		ECCC
    with Hamed Hatami, Shachar Lovett.
    [J] SIAM Journal on Computing (SICOMP) 47 (1), 208-217. 2018.
    [C] 57th Annual Symposium on Foundations of Computer Science (FOCS) 2016.
    Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification
    		ECCC
    with Divesh Aggarwal, Shachar Lovett.
    [C] IEEE International Symposium on Information Theory (ISIT) 2016.
    On the structure of the spectrum of small sets
    		arXiv
    with Shachar Lovett.
    [J] Journal of Combinatorial Theory, Series A 148, 1-14. May 2017
    An improved Lower Bound for Arithmetic Regularity
    		arXiv
    with Shachar Lovett, Guy Moshkovitz , Asaf Shapira.
    [J] Mathematical Proceedings of the Cambridge Philosophical Society 161 (2), 193-197. March 2016

imagei

pronounciation: kaa-VEH ho-SAY-nee
email: kaave.hosseini@gmail.com
email: kaave.hosseini@rochester.edu
office: Wegmans Hall 2507