Pooya Hatami

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