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
|