Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Pooya Hatami:

TR18-183 | 5th November 2018
Dean Doron, Pooya Hatami, William Hoza

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

Revisions: 1

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... more >>>

TR18-155 | 8th September 2018
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal

Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates

A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design ... more >>>

TR18-081 | 20th April 2018
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1

In this paper, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random $d$-linear ... more >>>

TR18-015 | 25th January 2018
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

Pseudorandom Generators from Polarizing Random Walks

Revisions: 1 , Comments: 1

We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that ... more >>>

TR17-171 | 6th November 2017
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Revisions: 1

We present an explicit pseudorandom generator with seed length $\tilde{O}((\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 Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work ... more >>>

TR17-025 | 16th February 2017
Pooya Hatami, Avishay Tal

Pseudorandom Generators for Low-Sensitivity Functions

A Boolean function is said to have maximal sensitivity $s$ if $s$ is the largest number of Hamming neighbors of a point which differ from it in function value. We construct a pseudorandom generator with seed-length $2^{O(\sqrt{s})} \cdot \log(n)$ that fools Boolean functions on $n$ variables with maximal sensitivity at ... more >>>

TR14-040 | 30th March 2014
Hamed Hatami, Pooya Hatami, Shachar Lovett

General systems of linear forms: equidistribution and true complexity

Revisions: 1

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 ... more >>>

TR12-184 | 26th December 2012
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett

Every locally characterized affine-invariant property is testable.

Revisions: 1

Let $\mathbb{F} = \mathbb{F}_p$ for any fixed prime $p \geq 2$. An affine-invariant property is a property of functions on $\mathbb{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 ... more >>>

ISSN 1433-8092 | Imprint