Pooya Hatami

According to our database, Pooya Hatami authored at least 48 papers between 2007 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2025

Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces.

Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak

CoRR, March, 2025

Stability and List-Replicability for Agnostic Learners.

Ari Blonda, Shan Gao, Hamed Hatami, Pooya Hatami

CoRR, January, 2025

Constant-Cost Communication Is Not Reducible to k-Hamming Distance.

Yuting Fang, Mika Göös, Nathaniel Harms, Pooya Hatami

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Stability and List-Replicability for Agnostic Learners.

Ari Blondal, Shan Gao, Hamed Hatami, Pooya Hatami

Proceedings of the Thirty Eighth Annual Conference on Learning Theory, 2025

2024

Guest Column: Structure in Communication Complexity and Constant-Cost Complexity Classes.

Hamed Hatami, Pooya Hatami

SIGACT News, March, 2024

Paradigms for Unconditional Pseudorandom Generators.

Pooya Hatami, William Hoza

Found. Trends Theor. Comput. Sci., 2024

Structure in Communication Complexity and Constant-Cost Complexity Classes.

Hamed Hatami, Pooya Hatami

Electron. Colloquium Comput. Complex., 2024

No Complete Problem for Constant-Cost Randomized Communication.

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Hilbert Functions and Low-Degree Randomness Extractors.

Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan

Proceedings of the Approximation, 2024

2023

Theory of Unconditional Pseudorandom Generators.

Pooya Hatami, William Hoza

Electron. Colloquium Comput. Complex., 2023

Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees.

Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Online Learning and Disambiguations of Partial Concept Classes.

TsunMing Cheung, Hamed Hatami, Pooya Hatami, Kaave Hosseini

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

A counter-example to the probabilistic universal graph conjecture via randomized communication complexity.

Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami

Discret. Appl. Math., 2022

The Implicit Graph Conjecture is False.

Hamed Hatami, Pooya Hatami

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Lower Bound Methods for Sign-Rank and Their Limitations.

Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao

Proceedings of the Approximation, 2022

2021

Fooling Constant-Depth Threshold Circuits.

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

Electron. Colloquium Comput. Complex., 2021

Dimension-free Bounds and Structural Results in Communication Complexity.

Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami

Electron. Colloquium Comput. Complex., 2021

Fooling Constant-Depth Threshold Circuits (Extended Abstract).

Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function.

John Chiarelli, Pooya Hatami, Michael E. Saks

Comb., 2020

XOR lemmas for resilient functions against polynomials.

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Log-Seed Pseudorandom Generators via Iterated Restrictions.

Dean Doron, Pooya Hatami, William M. Hoza

Proceedings of the 35th Computational Complexity Conference, 2020

On Multilinear Forms: Bias, Correlation, and Tensor Rank.

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

Proceedings of the Approximation, 2020

2019

Higher-order Fourier Analysis and Applications.

Hamed Hatami, Pooya Hatami, Shachar Lovett

Found. Trends Theor. Comput. Sci., 2019

Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates.

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions.

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas.

Dean Doron, Pooya Hatami, William M. Hoza

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Tight Bound on the Number of Relevant Variables in a Bounded degree Boolean function.

John Chiarelli, Pooya Hatami, Michael E. Saks

CoRR, 2018

Improved pseudorandomness for unordered branching programs through local monotonicity.

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius.

Pooya Hatami, Madhur Tulsiani

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Pseudorandom Generators for Low Sensitivity Functions.

Pooya Hatami, Avishay Tal

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Pseudorandom Generators from Polarizing Random Walks.

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Low-Sensitivity Functions from Unambiguous Certificates.

Shalev Ben-David, Pooya Hatami, Avishay Tal

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

A characterization of functions with vanishing averages over products of disjoint sets.

Hamed Hatami, Pooya Hatami, Yaqiao Li

Eur. J. Comb., 2016

On the Structure of Quintic Polynomials.

Pooya Hatami

Proceedings of the Approximation, 2016

2015

Algorithmic regularity for polynomials and applications.

Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

General systems of linear forms: equidistribution and true complexity.

Hamed Hatami, Pooya Hatami, Shachar Lovett

Electron. Colloquium Comput. Complex., 2014

Limits of Boolean Functions on 𝔽_pⁿ.

Hamed Hatami, Pooya Hatami, James Hirst

Electron. J. Comb., 2014

2013

An Arithmetic Analogue of Fox's Triangle Removal Argument

Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani

CoRR, 2013

Every locally characterized affine-invariant property is testable.

Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett

Proceedings of the Symposium on Theory of Computing Conference, 2013

2011

Variations on the Sensitivity Conjecture.

Pooya Hatami, Raghav Kulkarni, Denis Pankratov

Theory Comput., 2011

2010

An approximation algorithm for the total cover problem

Pooya Hatami

CoRR, 2010

On minimum vertex cover of generalized Petersen graphs

Babak Behsaz, Pooya Hatami, Ebadollah S. Mahmoodian

CoRR, 2010

2009

Measure preserving homomorphisms and independent sets in tensor graph powers.

Babak Behsaz, Pooya Hatami

Discret. Math., 2009

On the signed edge domination number of graphs.

Saeed Akbari, Sadegh Bolouki, Pooya Hatami, Milad Siami

Discret. Math., 2009

2008

A lower bound for the length of a partial transversal in a Latin square.

Pooya Hatami, Peter W. Shor

J. Comb. Theory A, 2008

On minimum vertex covers of generalized Petersen graphs.

Babak Behsaz, Pooya Hatami, Ebadollah S. Mahmoodian

Australas. J Comb., 2008

2007

An approximation algorithm for the total covering problem.

Pooya Hatami

Discuss. Math. Graph Theory, 2007

Perfect Dominating Sets in the Cartesian Products of Prime Cycles.

Hamed Hatami, Pooya Hatami

Electron. J. Comb., 2007