BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Pooya Hatami

Pooya Hatami contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COComputational ComplexityData Structures and AlgorithmsDiscrete Mathematicsmath.FAmath.NTmath.PR

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
12works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2015arXiv

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

Given $α_1,...,α_m \in (0,1)$, we characterize all integrable functions $f:[0,1]^m \to \mathbb{C}$ satisfying $\int_{A_1 \times ...\times A_m} f =0$ for any collection of disjoint sets $A_1,...,A_m \subseteq [0,1]$ of respective measures $α_1,...,α_m$. We use this characterization to settle some of the conjectures in [S. Janson and V. Sós, More on quasi-random graphs, subgraph counts and graph limits, arXiv:1405.6808].

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

General systems of linear forms: equidistribution and true complexity

The densities of small linear structures (such as arithmetic progressions) in subsets of Abelian groups can be expressed as certain analytic averages involving linear forms. Higher-order Fourier analysis examines such averages by approximating the indicator function of a subset by a function of bounded number of polynomials. Then, to approximate the average, it suffices to know the joint distribution of the polynomials applied to the linear forms. We prove a near-equidistribution theorem that describes these distributions for the group $\mathbb{F}_p^n$ when $p$ is a fixed prime. This fundamental fact is equivalent to a strong near-orthogonality statement regarding the higher-order characters, and was previously known only under various extra assumptions about the linear forms. As an application of our near-equidistribution theorem, we settle a conjecture of Gowers and Wolf on the true complexity of systems of linear forms for the group $\mathbb{F}_p^n$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Algorithmic regularity for polynomials and applications

In analogy with the regularity lemma of Szemerédi, regularity lemmas for polynomials shown by Green and Tao (Contrib. Discrete Math. 2009) and by Kaufman and Lovett (FOCS 2008) modify a given collection of polynomials \calF = {P_1,...,P_m} to a new collection \calF&#39; so that the polynomials in \calF&#39; are &#34;pseudorandom&#34;. 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 \calF to \calF&#39; is not algorithmic for either regularity lemma. We define new notions of regularity for polynomials, which are analogous to the above, but which allow for an efficient algorithm to compute the pseudorandom collection \calF&#39;. In particular, when the field is of high characteristic, in polynomial time, we can refine \calF into \calF&#39; where every nonzero linear combination of polynomials in \calF&#39; has desirably small Gowers norm. Using the algorithmic regularity lemmas, we show that if a polynomial P of degree d is within (normalized) Hamming distance 1-1/|F| -\eps of some unknown polynomial of degree k over a prime field F (for k < d < |F|), then there is an efficient algorithm for finding a degree-k polynomial Q, which is within distance 1-1/|F| -ηof P, for some ηdepending on \eps. This can be thought of as decoding the Reed-Muller code of order k beyond the list decoding radius (finding one close codeword), when the received word P itself is a polynomial of degree d (with k < d < |F|). We also obtain an algorithmic version of the worst-case to average-case reductions by Kaufman and Lovett. 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 efficient (randomized) algorithm to find this collection.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distance-Sensitive Property Testing Lower Bounds

In this paper, we consider several property testing problems and ask how the query complexity depends on the distance parameter $\eps$. We achieve new lower bounds in this setting for the problems of testing whether a function is monotone and testing whether the function has low Fourier degree. For monotonicity testing, our lower bound matches the recent upper bound of Chakrabarty and Seshadhri.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Every locally characterized affine-invariant property is testable

Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that there is a test that, given an input function f, makes a constant number of queries to f, always accepts if f satisfies P, and rejects with positive probability if the distance between f and P is nonzero. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable. We also prove that any property that can be described as the property of decomposing into a known structure of low-degree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized. Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of low-degree non-classical polynomials. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degree-structural properties.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Limits of Boolean Functions on F_p^n

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 random affine subspace. Using a decomposition theorem and a recently proven equi-distribution theorem from higher order Fourier analysis, we prove that the limits of such convergent sequences can be represented by certain measurable functions. We are also able to show that every such limit object arises as the limit of some sequence of functions. These results are in the spirit of similar results which have been developed for limits of graph sequences. A more general, albeit substantially more sophisticated, limit object was recently constructed by Szegedy in [Sze10].

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Lower Bounds on Testing Functions of Low Fourier Degree

We consider the problem of testing whether a Boolean function has Fourier degree $\leq k$ or it is $ε$-far from any Boolean function with Fourier degree $\leq k$. We improve the known lower bound of $Ω(k)$ \cite{BBM11,CGM10}, to $Ω(k/\sqrtε)$. The lower bound uses the recently discovered connections between property testing and communication complexity by Blais \textit{et. al.} \cite{BBM11}

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On minimum vertex cover of generalized Petersen graphs

For natural numbers $n$ and $k$ ($n > 2k$), a generalized Petersen graph $P(n,k)$, is defined by vertex set $\lbrace u_i,v_i\rbrace$ and edge set $\lbrace u_iu_{i+1},u_iv_i,v_iv_{i+k}\rbrace$; where $i = 1,2,\dots,n$ and subscripts are reduced modulo $n$. Here first, we characterize minimum vertex covers in generalized Petersen graphs. Second, we present a lower bound and some upper bounds for $β(P(n,k))$, the size of minimum vertex cover of $P(n,k)$. Third, in some cases, we determine the exact values of $β(P(n,k))$. Our conjecture is that $β(P(n,k)) \le n + \lceil\frac{n}{5}\rceil$, for all $n$ and $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On The Signed Edge Domination Number of Graphs

Let $γ&#39;_s(G)$ be the signed edge domination number of G. In 2006, Xu conjectured that: for any $2$-connected graph G of order $ n (n \geq 2),$ $γ&#39;_s(G)\geq 1$. In this article we show that this conjecture is not true. More precisely, we show that for any positive integer $m$, there exists an $m$-connected graph $G$ such that $ γ&#39;_s(G)\leq -\frac{m}{6}|V(G)|.$ Also for every two natural numbers $m$ and $n$, we determine $γ&#39;_s(K_{m,n})$, where $K_{m,n}$ is the complete bipartite graph with part sizes $m$ and $n$.

0 citations0 reviewsNo code linkedOpen access