Pooya Hatami

Publication Activity (10 Years)

Years Active: 2007-2024
Publications (10 Years): 53

Top Topics

Boolean Functions

Uniformly Distributed

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami
No Complete Problem for Constant-Cost Randomized Communication. CoRR (2024)
Yuting Fang, Mika Göös, Nathaniel Harms, Pooya Hatami
Constant-Cost Communication is not Reducible to k-Hamming Distance. CoRR (2024)
Hamed Hatami, Pooya Hatami
Guest Column: Structure in Communication Complexity and Constant-Cost Complexity Classes. SIGACT News 55 (1) (2024)
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami
No Complete Problem for Constant-Cost Randomized Communication. Electron. Colloquium Comput. Complex. (2024)
Pooya Hatami, William Hoza
Paradigms for Unconditional Pseudorandom Generators. Found. Trends Theor. Comput. Sci. 16 (1-2) (2024)
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan
Hilbert Functions and Low-Degree Randomness Extractors. CoRR (2024)
Hamed Hatami, Pooya Hatami
Structure in Communication Complexity and Constant-Cost Complexity Classes. Electron. Colloquium Comput. Complex. (2024)
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan
Hilbert Functions and Low-Degree Randomness Extractors. Electron. Colloquium Comput. Complex. (2024)
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami
No Complete Problem for Constant-Cost Randomized Communication. STOC (2024)
Hamed Hatami, Pooya Hatami
Structure in Communication Complexity and Constant-Cost Complexity Classes. CoRR (2024)
TsunMing Cheung, Hamed Hatami, Pooya Hatami, Kaave Hosseini
Online Learning and Disambiguations of Partial Concept Classes. ICALP (2023)
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees. STOC (2023)
Pooya Hatami, William Hoza
Theory of Unconditional Pseudorandom Generators. Electron. Colloquium Comput. Complex. (2023)
TsunMing Cheung, Hamed Hatami, Pooya Hatami, Kaave Hosseini
Online Learning and Disambiguations of Partial Concept Classes. CoRR (2023)
Hamed Hatami, Pooya Hatami
The Implicit Graph Conjecture is False. FOCS (2022)
Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao
Lower Bound Methods for Sign-Rank and Their Limitations. APPROX/RANDOM (2022)
Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao
Lower Bound Methods for Sign-rank and their Limitations. Electron. Colloquium Comput. Complex. (2022)
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees. Electron. Colloquium Comput. Complex. (2022)
Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity. Discret. Appl. Math. 322 (2022)
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
Fooling Constant-Depth Threshold Circuits (Extended Abstract). FOCS (2022)
Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity. CoRR (2021)
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
Fooling Constant-Depth Threshold Circuits. Electron. Colloquium Comput. Complex. 28 (2021)
Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami
Dimension-free Bounds and Structural Results in Communication Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Hamed Hatami, Pooya Hatami
The Implicit Graph Conjecture is False. CoRR (2021)
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
Fooling Constant-Depth Threshold Circuits (Extended Abstract). FOCS (2021)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman
XOR lemmas for resilient functions against polynomials. STOC (2020)
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar
On Multilinear Forms: Bias, Correlation, and Tensor Rank. APPROX-RANDOM (2020)
John Chiarelli, Pooya Hatami, Michael E. Saks
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function. Comb. 40 (2) (2020)
Dean Doron, Pooya Hatami, William M. Hoza
Log-Seed Pseudorandom Generators via Iterated Restrictions. Computational Complexity Conference (2020)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett
Pseudorandom Generators from Polarizing Random Walks. Theory Comput. 15 (2019)
Hamed Hatami, Pooya Hatami, Shachar Lovett
Higher-order Fourier Analysis and Applications. Found. Trends Theor. Comput. Sci. 13 (4) (2019)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman
XOR Lemmas for Resilient Functions Against Polynomials. Electron. Colloquium Comput. Complex. 26 (2019)
Dean Doron, Pooya Hatami, William M. Hoza
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. Computational Complexity Conference (2019)
Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. CoRR (2019)
Dean Doron, Pooya Hatami, William Hoza
Log-Seed Pseudorandom Generators via Iterated Restrictions. Electron. Colloquium Comput. Complex. 26 (2019)
Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. Electron. Colloquium Comput. Complex. 26 (2019)
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. ITCS (2019)
Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. ICALP (2019)
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar
On Multilinear Forms: Bias, Correlation, and Tensor Rank. CoRR (2018)
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. Electron. Colloquium Comput. Complex. 25 (2018)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett
Pseudorandom Generators from Polarizing Random Walks. Electron. Colloquium Comput. Complex. 25 (2018)
Dean Doron, Pooya Hatami, William Hoza
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. Electron. Colloquium Comput. Complex. 25 (2018)
Pooya Hatami, Madhur Tulsiani
Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius. SODA (2018)
John Chiarelli, Pooya Hatami, Michael E. Saks
Tight Bound on the Number of Relevant Variables in a Bounded degree Boolean function. CoRR (2018)
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar
On Multilinear Forms: Bias, Correlation, and Tensor Rank. Electron. Colloquium Comput. Complex. 25 (2018)
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal
Improved pseudorandomness for unordered branching programs through local monotonicity. STOC (2018)
Pooya Hatami, Avishay Tal
Pseudorandom Generators for Low Sensitivity Functions. ITCS (2018)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett
Pseudorandom Generators from Polarizing Random Walks. Computational Complexity Conference (2018)
Pooya Hatami, Avishay Tal
Pseudorandom Generators for Low-Sensitivity Functions. Electron. Colloquium Comput. Complex. 24 (2017)
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity. Electron. Colloquium Comput. Complex. 24 (2017)
Shalev Ben-David, Pooya Hatami, Avishay Tal
Low-Sensitivity Functions from Unambiguous Certificates. ITCS (2017)
Pooya Hatami
On the Structure of Quintic Polynomials. APPROX-RANDOM (2016)
Hamed Hatami, Pooya Hatami, Yaqiao Li
A characterization of functions with vanishing averages over products of disjoint sets. Eur. J. Comb. 56 (2016)
Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani
Algorithmic regularity for polynomials and applications. SODA (2015)
Hamed Hatami, Pooya Hatami, James Hirst
Limits of Boolean Functions on $\mathbb{F}_p^n$. Electron. J. Comb. 21 (4) (2014)
Hamed Hatami, Pooya Hatami, Shachar Lovett
General systems of linear forms: equidistribution and true complexity. Electron. Colloquium Comput. Complex. 21 (2014)
Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani
Algorithmic regularity for polynomials and applications. CoRR (2013)
Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani
An Arithmetic Analogue of Fox's Triangle Removal Argument CoRR (2013)
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett
Every locally characterized affine-invariant property is testable. STOC (2013)
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett
Every locally characterized affine-invariant property is testable. Electron. Colloquium Comput. Complex. 19 (2012)
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett
Every locally characterized affine-invariant property is testable CoRR (2012)
Pooya Hatami, Raghav Kulkarni, Denis Pankratov
Variations on the Sensitivity Conjecture. Theory Comput. 4 (2011)
Saeed Akbari, Sadegh Bolouki, Pooya Hatami, Milad Siami
On The Signed Edge Domination Number of Graphs CoRR (2010)
Pooya Hatami
An approximation algorithm for the total cover problem CoRR (2010)
Pooya Hatami, Raghav Kulkarni, Denis Pankratov
Variations on the Sensitivity Conjecture CoRR (2010)
Babak Behsaz, Pooya Hatami, Ebadollah S. Mahmoodian
On minimum vertex cover of generalized Petersen graphs CoRR (2010)
Babak Behsaz, Pooya Hatami
Measure preserving homomorphisms and independent sets in tensor graph powers. Discret. Math. 309 (4) (2009)
Saeed Akbari, Sadegh Bolouki, Pooya Hatami, Milad Siami
On the signed edge domination number of graphs. Discret. Math. 309 (3) (2009)
Babak Behsaz, Pooya Hatami, Ebadollah S. Mahmoodian
On minimum vertex covers of generalized Petersen graphs. Australas. J Comb. 40 (2008)
Pooya Hatami, Peter W. Shor
A lower bound for the length of a partial transversal in a Latin square. J. Comb. Theory, Ser. A 115 (7) (2008)
Pooya Hatami
An approximation algorithm for the total covering problem. Discuss. Math. Graph Theory 27 (3) (2007)
Hamed Hatami, Pooya Hatami
Perfect Dominating Sets in the Cartesian Products of Prime Cycles. Electron. J. Comb. 14 (1) (2007)