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

41. Tight list replicability bounds via a novel sphere covering theorem. with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
    COLT 2026. [arXiv]
42. Simplicial covering dimension of extremal concept classes. with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
    ITCS 2026. [arXiv]
43. Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces. with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
    STOC 2026. [arXiv]
44. Stability and List-Replicability for Agnostic Learners. with Ari Blondal, Shan Gao, and Hamed Hatami.
    COLT 2025. [arXiv]
45. Constant-Cost Communication is not Reducible to k-Hamming Distance. with Yuting Fang, Nathan Harms, and Mika Göös.
    STOC 2025. [arXiv]
46. Hilbert Functions and Low-Degree Randomness Extractors. with Alexander Golovnev, Zeyu Guo, Satyajeet Nagargoje, and Chao Yan.
    RANDOM 2024. [arXiv] [ECCC]
47. No Complete Problem for Constant-Cost Randomized Communication. with Yuting Fang, Lianna Hambardzumyan, and Nathan Harms.
    STOC 2024. [conference version] [arXiv]
48. Online Learning and Disambiguations of Partial Concept Classes. with Tsun-Ming Cheung, Hamed Hatami, and Kaave Hosseini.
    ICALP 2023. Best Paper. [arXiv]
49. Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees. with William M. Hoza, Avishay Tal, and Roei Tell.
    STOC 2023. [ECCC]
50. Dimension-free Bounds and Structural Results in Communication Complexity. with Lianna Hambardzumyan and Hamed Hatami.
    Israel Journal of Mathematics, 2023. [IJM] [ECCC]
51. The Implicit Graph Conjecture is False. with Hamed Hatami.
    FOCS 2022. [arXiv]
52. Lower Bound Methods for Sign-rank and their Limitations. with Hamed Hatami, William Pires, Ran Tao, and Rosie Zhao.
    RANDOM 2022. [ECCC]
53. 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]
54. Fooling Constant-Depth Threshold Circuits. with William M. Hoza, Avishay Tal, and Roei Tell.
    FOCS 2021. [ECCC]
55. On Multilinear Forms: Bias, Correlation, and Tensor Rank. with Abhishek Bhrushundi, Prahladh Harsha, Swastik Kopparty, and Mrinal Kumar.
    RANDOM 2020. [arXiv]
56. XOR Lemmas for Resilient Functions against Polynomials. with Eshan Chattopadhyay, Kaave Hosseini, Shachar Lovett, and David Zuckerman.
    STOC 2020. [ECCC]
57. Log-Seed Pseudorandom Generators via Iterated Restrictions. with Dean Doron and William M. Hoza.
    CCC 2020. [ECCC]
58. Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function. with John Chiarelli and Michael Saks.
    Combinatorica, 2020. [journal] [arXiv]
59. 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]
60. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. with Dean Doron and William Hoza.
    CCC 2019. [ECCC]
61. 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]
62. 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]
63. Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity. with Eshan Chattopadhyay, Omer Reingold, and Avishay Tal.
    STOC 2018. [ECCC]
64. Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius. with Madhur Tulsiani.
    SODA 2018. [pdf] [proceedings]
65. Pseudorandom Generators for Low-Sensitivity Functions. with Avishay Tal.
    ITCS 2018. [ECCC] [proceedings]
66. Low-Sensitivity Functions from Unambiguous Certificates. with Shalev Ben-David and Avishay Tal.
    ITCS 2017. [arXiv]
67. 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]
68. 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]
69. On the structure of quintic polynomials. RANDOM 2016. [arXiv]
70. An Arithmetic Analogue of Fox's Triangle Removal Argument. with Sushant Sachdeva and Madhur Tulsiani.
    Online Journal of Analytic Combinatorics 11 (2016). [OJAC] [arXiv]
71. Algorithmic Regularity for Polynomials and Applications. with Arnab Bhattacharyya and Madhur Tulsiani.
    SODA 2015. [proceedings] [arXiv]
72. Every locally characterized affine-invariant property is testable. with Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, and Shachar Lovett.
    STOC 2013. [ECCC] [arXiv]
73. Variations on the Sensitivity Conjecture. with Raghav Kulkarni and Denis Pankratov.
    Theory of Computing Library, Graduate Surveys 4 (2011), 1--27. [ToC]
74. 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]
75. Distance-Sensitive Property Testing Lower Bounds. with Joshua Brody.
    Manuscript. [arXiv]
76. Perfect dominating sets in the Cartesian products of prime cycles. with Hamed Hatami.
    Electronic Journal of Combinatorics, Vol. 14 (2007), N8. [EJC]
77. Measure preserving homomorphisms and independent sets in tensor graph powers. with Babak Behsaz.
    Discrete Mathematics, 309, 4 (2009), 955--958. [arXiv]
78. On the signed edge domination number of graphs. with Saeed Akbari, Sadegh Bolouki, and Milad Siami.
    Discrete Mathematics, 309, 3 (2009), 587--594. [arXiv]
79. On minimum vertex cover of generalized Petersen graphs. with Mehdi Behzad and E. S. Mahmoodian.
    Bulletin of the ICA, 56 (2009), 98--102. [ICA]
80. An Approximation Algorithm for the Total Covering Problem. Discussiones Mathematicae Graph Theory, 27, 3 (2007), 553--560. [arXiv]
81. 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.