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 the interplay between algebraic, analytic, and combinatorial structure.

I am part of the Computation, Combinatorics & Choice (CCC) group and an affiliate of the Goergen Institute for Data Science and Artificial Intelligence (GIDS-AI) at the University of Rochester.

Publications:

A $\mathbb{Z}_2$-Topological Framework for Sign-rank Lower Bounds	arXiv
with Florian Frick, Aliaksei Vasileuski Preprint, 2026.
A Lower Bound on the Trace Norm of Boolean Matrices and its Applications	ECCC
with Tsun-Ming Cheung, Hamed Hatami, Aleksandar Nikolov , Toniann Pitassi , Morgan Shirley Innovations in Theoretical Computer Science (ITCS) 2025.
Sparse graph counting and Kelley-Meka bounds for binary systems	Arxiv
with Yuval Filmus, Hamed Hatami, Esty Kellman 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 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 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 Computational Complexity Conference (CCC) 2023.
A Borsuk-Ulam lower bound for sign-rank and its applications	ECCC
with Hamed Hatami, Xiang Meng. ACM Symposium on Theory of Computing (STOC) 2023.
Sign rank vs. Discrepancy	ECCC
with Hamed Hatami, Shachar Lovett. Theory of Computing; CCC2020 Special Issue 18 (1), 1-22. July 2022 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. Annual ACM Symposium on Theory of Computing (STOC) 2020.
Optimality of Linear Sketching under Modular Updates	Arxiv
with Shachar Lovett, Grigory Yaroslavtsev. Computational Complexity Conference (CCC) 2019.
A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds	Arxiv
with Shachar Lovett. 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. Innovations in Theoretical Computer Science Conference (ITCS) 2019.
Pseudorandom generators from polarizing random walks	ECCC
with Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett. Theory of Computing; CCC2018 Special Issue 15 (1), 1-26. October 2019 Computational Complexity Conference (CCC) 2018. Invited to ToC Special Issue for CCC2018.
Structure of protocols for XOR functions	ECCC
with Hamed Hatami, Shachar Lovett. SIAM Journal on Computing (SICOMP) 47 (1), 208-217. 2018. 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. IEEE International Symposium on Information Theory (ISIT) 2016.
On the structure of the spectrum of small sets	arXiv
with Shachar Lovett. 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. Mathematical Proceedings of the Cambridge Philosophical Society 161 (2), 193-197. March 2016

Service:

Program Committee: STACS 2026, FOCS 2026

Editor: Theoretical Computer Science

Workshops:

Eastern Great Lakes (EaGL) Theory of Computation Workshop: 2023, 2024, 2025

Past Teaching:

At U of R:

CSC 280/480: Computer Models and Limitations: Fall 2022, Fall 2023, Spring 2026

CSC/MATH 488/288: Analytic Methods in Computer Science: Fall 2021, Fall 2022, Spring 2026

CSC 484/284: Advanced Algorithms Fall 2023, Fall 2024

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

---