Pooya Hatami

STOC Conference 2025 Conference Paper

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

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

Every known communication problem whose randomized communication cost is constant (independent of the input size) can be reduced to k -Hamming Distance, that is, solved with a constant number of deterministic queries to some k -Hamming Distance oracle. We exhibit the first examples of constant-cost problems which cannot be reduced to k -Hamming Distance. To prove this separation, we relate it to a natural coding-theoretic question. For f ∶ {2,4,6}→ℕ, we say that an encoding function E ∶{0,1} n →{0,1} m is an f -code if it transforms Hamming distances according to dist ( E ( x ), E ( y ))= f ( dist ( x , y )) whenever f is defined. We prove that, if there exist f -codes for infinitely many n , then f must be affine: f (4)=( f (2)+ f (6))/2.

STOC Conference 2024 Conference Paper

No Complete Problem for Constant-Cost Randomized Communication

• Yuting Fang
• Lianna Hambardzumyan
• Nathaniel Harms
• Pooya Hatami

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called BPP 0 , does not contain a complete problem. In other words, there is no randomized constant-cost problem Q ∈ BPP 0 , such that all other problems P ∈ BPP 0 can be computed by a constant-cost deterministic protocol with access to an oracle for Q . We also show that the k -Hamming Distance problems form an infinite hierarchy within BPP 0 . Previously, it was known only that Equality is not complete for BPP 0 . We introduce a new technique, using Ramsey theory, that can prove lower bounds against arbitrary oracles in BPP 0 , and more generally, we show that k -Hamming Distance matrices cannot be expressed as a Boolean combination of any constant number of matrices which forbid large Greater-Than subproblems.

STOC Conference 2023 Conference Paper

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

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

For any n ∈ ℕ and d = o (loglog( n )), we prove that there is a Boolean function F on n bits and a value γ = 2 −Θ( d ) such that F can be computed by a uniform depth-( d + 1) AC 0 circuit with O ( n ) wires, but F cannot be computed by any depth- d TC 0 circuit with n 1 + γ wires. This bound matches the current state-of-the-art lower bounds for computing explicit functions by threshold circuits of depth d > 2, which were previously known only for functions outside AC 0 such as the parity function. Furthermore, in our result, the AC 0 circuit computing F is a monotone *read-once formula* (i.e., an AND-OR tree), and the lower bound holds even in the average-case setting with respect to advantage n −γ . At a high level, our proof strategy combines two prominent approaches in circuit complexity from the last decade: The celebrated *random projections* method of Håstad, Rossman, Servedio, and Tan (J. ACM 2017), which was previously used to show a tight average-case depth hierarchy for AC 0 ; and the line of works analyzing the effect of *random restrictions* on threshold circuits. We show that under a modified version of Håstad, Rossman, Servedio, and Tan’s projection procedure, any depth- d threshold circuit with n 1 + γ wires simplifies to a near-trivial function, whereas an appropriately parameterized AND-OR tree of depth d + 1 maintains structure.

FOCS Conference 2022 Conference Paper

The Implicit Graph Conjecture is False

• Hamed Hatami
• Pooya Hatami

An efficient implicit representation of an n-vertex graph G in a family $\mathcal{F}$ of graphs assigns to each vertex of G a binary code of length O(log n) so that the adjacency between every pair of vertices can be determined only as a function of their codes. This function can depend on the family but not on the individual graph. Every family of graphs admitting such a representation contains at most $2^{O(n\log(n))}$ graphs on n vertices, and thus has at most factorial speed of growth. The Implicit Graph Conjecture states that, conversely, every hereditary graph family with at most factorial speed of growth admits an efficient implicit representation. We refute this conjecture by establishing the existence of hereditary graph families with factorial speed of growth that require codes of length $n^{\Omega(1)}$.

FOCS Conference 2021 Conference Paper

Fooling Constant-Depth Threshold Circuits (Extended Abstract)

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

We present new constructions of pseudorandom generators (PRGs) for two of the most widely studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth $d\in\mathbb{N}$ and $n^{1+\delta}$ wires, where $\delta=2^{-O(d)}$, using seed length $O(n^{1-\delta})$ and with error $2^{-n^{\delta}}$. This tightly matches the best known lower bounds for this circuit class. As a consequence of our result, all the known hardness for LTF circuits has now effectively been translated into pseudorandomness. This brings the extensive effort in the last decade to construct PRGs and deterministic circuit-analysis algorithms for this class to the point where any subsequent improvement would yield breakthrough lower bounds. Our second contribution is a PRG for De Morgan formulas of size $s$ whose seed length is $s^{1/3+o(1)}\cdot\text{polylog}(1/\epsilon)$ for error $\epsilon$. In particular, our PRG can fool formulas of sub-cubic size $s=n^{3-\Omega(1)}$ with an exponentially small error $\epsilon=\exp(-n^{\Omega(1)})$. This significantly improves the inverse-polynomial error of the previous state-of-the-art for such formulas by Impagliazzo, Meka, and Zuckerman (FOCS 2012, JACM 2019), and again tightly matches the best currently-known lower bounds for this class. In both settings, a key ingredient in our constructions is a pseudorandom restriction procedure that has tiny failure probability, but simplifies the function to a non-natural “hybrid computational model” that combines several computational models. As part of our proofs we also construct “extremely low-error” PRGs for related circuit classes; for example, we construct a PRG for arbitrary functions of $s$ LTFs that can handle even the extreme setting of parameters $s=n/\text{polylog}(n)$ and $\epsilon=2^{-n/\text{polylog}(n)}$.

STOC Conference 2020 Conference Paper

XOR lemmas for resilient functions against polynomials

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

A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over F 2 . We introduce a new technique to prove such correlation bounds with F 2 polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In fact, we prove a more general XOR lemma that extends to arbitrary resilient functions. We conjecture that the technique generalizes to higher degree polynomials as well. A key ingredient in our new approach is a structural result about the Fourier spectrum of low degree polynomials over F 2 . We show that for any n -variate polynomial p over F 2 of degree at most d , there is a small set S ⊂ [ n ] of variables, such that almost all of the Fourier mass of p lies on Fourier coefficients that intersect with S . In fact our result is more general, and finds such a set S for any low-dimensional subspace of polynomials. This generality is crucial in deriving the new XOR lemmas.

SODA Conference 2018 Conference Paper

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

• Pooya Hatami
• Madhur Tulsiani

STOC Conference 2018 Conference Paper

Improved pseudorandomness for unordered branching programs through local monotonicity

• Eshan Chattopadhyay
• Pooya Hatami
• Omer Reingold
• Avishay Tal

We present an explicit pseudorandom generator with seed length Õ((log n ) w +1 ) for read-once, oblivious, width w branching programs that can read their input bits in any order. This improves upon the work of Impagliazzo, Meka and Zuckerman (FOCS’12) where they required seed length n 1/2+ o (1) . A central ingredient in our work is the following bound that we prove on the Fourier spectrum of branching programs. For any width w read-once, oblivious branching program B :{0,1} n → {0,1}, any k ∈ {1,…, n }, [complex formula not displayed] This settles a conjecture posed by Reingold, Steinke and Vadhan (RANDOM’13). Our analysis crucially uses a notion of local monotonicity on the edge labeling of the branching program. We carry critical parts of our proof under the assumption of local monotonicity and show how to deduce our results for unrestricted branching programs.

SODA Conference 2015 Conference Paper

Algorithmic regularity for polynomials and applications

• Arnab Bhattacharyya 0001
• Pooya Hatami
• Madhur Tulsiani

In analogy with the regularity lemma of Szemerédi [Sze75], regularity lemmas for polynomials proved by Green and Tao [GT09] and by Kaufman and Lovett [KL08] show that one can modify a given collection of polynomials ℱ = { P 1, …, P m } into a new collection ℱ′ so that the polynomials in ℱ′ are “pseudorandom”. These lemmas have various applications, such as (special cases of) Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from ℱ to ℱ′ in these works is not algorithmic. We define new notions of regularity for polynomials which, while being qualitatively equivalent to the above, also allow for efficient algorithms. Using the algorithmic regularity lemmas, we obtain an algorithmic version of the inverse theorem for Gowers norm (for bounded degree polynomials) over fields of high characteristic, by Green and Tao [GT09]. As an application, we show that if a polynomial P of degree d is within (normalized) Hamming distance of some unknown polynomial of degree k over a prime field (for k < d < | |), then there is an efficient algorithm for finding a degree- k polynomial Q, which is within distance of P, for some η depending on ε, This can be thought of as decoding the Reed-Muller code of order k beyond the list decoding radius, in the sense of finding one close codeword, when the received word P itself is a polynomial (of degree larger than k but smaller than | |). We also show an algorithmic inverse theorem for polynomials over fields of small characteristic and somewhat simplify the original proof by Tao and Ziegler [TZ12]. We also obtain an algorithmic version of the worstcase to average-case reductions by Kaufman and Lovett [KL08]. They show that if a polynomial of degree d can be weakly approximated by a polynomial of lower degree, then it can be computed exactly using a collection of polynomials of degree at most d − 1. We give an effcient algorithm to find this collection. Finally, our algorithmic regularity lemma over low characteristics can be used to effciently decompose low-degree polynomials over n (for any prime order field ) into polynomials P 1, …, P m: n → that satisfy prescribed degree bounds and for which P ( x ) = Λ( P 1 ( x ), …. P m ( x )) for a given m and Λ.

STOC Conference 2013 Conference Paper

Every locally characterized affine-invariant property is testable

• Arnab Bhattacharyya 0001
• Eldar Fischer
• Hamed Hatami
• Pooya Hatami
• Shachar Lovett