Publications

Home | Teaching | Google Scholar

Monographs and surveys

• Structure in Communication Complexity and Constant-Cost Complexity Classes. with Hamed Hatami.
  Invited survey article for ACM SIGACT News Complexity Theory Column. [SIGACT] [ECCC] [arXiv]
• Paradigms for Unconditional Pseudorandom Generators. with William M. Hoza.
  Foundations and Trends in Theoretical Computer Science. [FnTTCS] [old version]
• Higher Order Fourier Analysis and Applications. with Hamed Hatami and Shachar Lovett.
  Foundations and Trends in Theoretical Computer Science, Vol. 13, No. 4, pp. 247--448. [FnTTCS] [free plain version]
• Variations on the Sensitivity Conjecture. with Raghav Kulkarni and Denis Pankratov.
  Theory of Computing Library, Graduate Surveys 4 (2011), 1--27. [ToC]

Papers

• Sign-Rank, Index, and List Replicability: Connections and Separations . with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
  preprint. [arXiv]
• Tight list replicability bounds via a novel sphere covering theorem. with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
  COLT 2026. [arXiv]
• Simplicial covering dimension of extremal concept classes. with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
  ITCS 2026. [arXiv]
• Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces. with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
  STOC 2026. [arXiv]
• Stability and List-Replicability for Agnostic Learners. with Ari Blondal, Shan Gao, and Hamed Hatami.
  COLT 2025. [arXiv]
• Constant-Cost Communication is not Reducible to k-Hamming Distance. with Yuting Fang, Nathan Harms, and Mika Göös.
  STOC 2025. [arXiv]
• Hilbert Functions and Low-Degree Randomness Extractors. with Alexander Golovnev, Zeyu Guo, Satyajeet Nagargoje, and Chao Yan.
  RANDOM 2024. [arXiv] [ECCC]
• No Complete Problem for Constant-Cost Randomized Communication. with Yuting Fang, Lianna Hambardzumyan, and Nathan Harms.
  STOC 2024. [conference version] [arXiv]
• Online Learning and Disambiguations of Partial Concept Classes. with Tsun-Ming Cheung, Hamed Hatami, and Kaave Hosseini.
  ICALP 2023. Best Paper. [arXiv]
• Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees. with William M. Hoza, Avishay Tal, and Roei Tell.
  STOC 2023. [ECCC]
• Dimension-free Bounds and Structural Results in Communication Complexity. with Lianna Hambardzumyan and Hamed Hatami.
  Israel Journal of Mathematics, 2023. [IJM] [ECCC]
• The Implicit Graph Conjecture is False. with Hamed Hatami.
  FOCS 2022. [arXiv]
• Lower Bound Methods for Sign-rank and their Limitations. with Hamed Hatami, William Pires, Ran Tao, and Rosie Zhao.
  RANDOM 2022. [ECCC]
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity. with Lianna Hambardzumyan and Hamed Hatami.
  Discrete Applied Mathematics, 2022. [DAM] [arXiv]
• Fooling Constant-Depth Threshold Circuits. with William M. Hoza, Avishay Tal, and Roei Tell.
  FOCS 2021. [ECCC]
• On Multilinear Forms: Bias, Correlation, and Tensor Rank. with Abhishek Bhrushundi, Prahladh Harsha, Swastik Kopparty, and Mrinal Kumar.
  RANDOM 2020. [arXiv]
• XOR Lemmas for Resilient Functions against Polynomials. with Eshan Chattopadhyay, Kaave Hosseini, Shachar Lovett, and David Zuckerman.
  STOC 2020. [ECCC]
• Log-Seed Pseudorandom Generators via Iterated Restrictions. with Dean Doron and William M. Hoza.
  CCC 2020. [ECCC]
• Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function. with John Chiarelli and Michael Saks.
  Combinatorica, 2020. [journal] [arXiv]
• Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. with Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, and David Zuckerman.
  ICALP 2019. [arXiv]
• Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. with Dean Doron and William Hoza.
  CCC 2019. [ECCC]
• Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. with Eshan Chattopadhyay, Shachar Lovett, and Avishay Tal.
  ITCS 2018. [ECCC]
• Pseudorandom Generators from Polarizing Random Walks. with Eshan Chattopadhyay, Kaave Hosseini, and Shachar Lovett.
  CCC 2018; Theory of Computing 2019, CCC'18 Special Issue. [ECCC] [ToC]
• Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity. with Eshan Chattopadhyay, Omer Reingold, and Avishay Tal.
  STOC 2018. [ECCC]
• Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius. with Madhur Tulsiani.
  SODA 2018. [pdf] [proceedings]
• Pseudorandom Generators for Low-Sensitivity Functions. with Avishay Tal.
  ITCS 2018. [ECCC] [proceedings]
• Low-Sensitivity Functions from Unambiguous Certificates. with Shalev Ben-David and Avishay Tal.
  ITCS 2017. [arXiv]
• General systems of linear forms: equidistribution and true complexity. with Hamed Hatami and Shachar Lovett.
  Advances in Mathematics, 292:446--477, 2016. [journal] [ECCC] [talk video]
• A characterization of functions with vanishing averages over products of disjoint sets. with Hamed Hatami and Yaqiao Li.
  European Journal of Combinatorics, 56 (2016), 81--93. [arXiv] [talk video]
• On the structure of quintic polynomials. RANDOM 2016. [arXiv]
• An Arithmetic Analogue of Fox's Triangle Removal Argument. with Sushant Sachdeva and Madhur Tulsiani.
  Online Journal of Analytic Combinatorics 11 (2016). [OJAC] [arXiv]
• Algorithmic Regularity for Polynomials and Applications. with Arnab Bhattacharyya and Madhur Tulsiani.
  SODA 2015. [proceedings] [arXiv]
• Every locally characterized affine-invariant property is testable. with Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, and Shachar Lovett.
  STOC 2013. [ECCC] [arXiv]
• Variations on the Sensitivity Conjecture. with Raghav Kulkarni and Denis Pankratov.
  Theory of Computing Library, Graduate Surveys 4 (2011), 1--27. [ToC]
• A lower Bound for the length of a Partial Transversal in a Latin Square. with Peter W. Shor.
  Journal of Combinatorial Theory, Series A, 115, 7 (2008), 1103--1113. [doi]
• Distance-Sensitive Property Testing Lower Bounds. with Joshua Brody.
  Manuscript. [arXiv]
• Perfect dominating sets in the Cartesian products of prime cycles. with Hamed Hatami.
  Electronic Journal of Combinatorics, Vol. 14 (2007), N8. [EJC]
• Measure preserving homomorphisms and independent sets in tensor graph powers. with Babak Behsaz.
  Discrete Mathematics, 309, 4 (2009), 955--958. [arXiv]
• On the signed edge domination number of graphs. with Saeed Akbari, Sadegh Bolouki, and Milad Siami.
  Discrete Mathematics, 309, 3 (2009), 587--594. [arXiv]
• On minimum vertex cover of generalized Petersen graphs. with Mehdi Behzad and E. S. Mahmoodian.
  Bulletin of the ICA, 56 (2009), 98--102. [ICA]
• An Approximation Algorithm for the Total Covering Problem. Discussiones Mathematicae Graph Theory, 27, 3 (2007), 553--560. [arXiv]
• On minimum vertex covers in generalized Petersen graphs.
  with Babak Behsaz and E. S. Mahmoodian. Australasian Journal of Combinatorics, 40 (2007), 253--264. [arXiv]

Last updated: June 2026.