Pooya Hatami

activity

19932026

most citedWhat can be computed in algebraic geometry?

201 citations · 235 across the 24 of their papers we have counts for

collaborators

Showing math.COShow all

8 papers · 1 filter

math.CO2021

The Implicit Graph Conjecture is False

Hamed Hatami, Pooya Hatami

An efficient implicit representation of an $n$ -vertex graph $G$ in a family $F$ of graphs assigns to each vertex of $G$ a binary code of length $O (lo g n)$ so that the ad…

math.CO2018

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

John Chiarelli, Pooya Hatami, Michael Saks

We prove that there is a constant $C \leq 6.614$ such that every Boolean function of degree at most $d$ (as a polynomial over $R$ ) is a $C \cdot 2^{d}$ -junta, i.e. it depends…

math.CO2015

On the Structure of Quintic Polynomials

Pooya Hatami

We study the structure of bounded degree polynomials over finite fields. Haramaty and Shpilka [STOC 2010] showed that biased degree three or four polynomials admit a strong structu…

math.CO2014

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

Hamed Hatami, Pooya Hatami, Yaqiao Li

Given $α_{1}, ..., α_{m} \in (0, 1)$ , we characterize all integrable functions $f : [0, 1]^{m} \to C$ satisfying $\int_{A_{1} \times ... \times A_{m}} f = 0$ for any collection of disjoint…

math.CO2013

Limits of Boolean Functions on F_p^n

Hamed Hatami, Pooya Hatami, James Hirst

We study sequences of functions of the form F_p^n -> {0,1} for varying n, and define a notion of convergence based on the induced distributions from restricting the functions to a…

math.CO2013★ 10 cited

An Arithmetic Analogue of Fox's Triangle Removal Argument

Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani

We give an arithmetic version of the recent proof of the triangle removal lemma by Fox [Fox11], for the group $F_{2}^{n}$ . A triangle in $F_{2}^{n}$ is a triple $(x, y, z)$ …