Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > CHIN HO LEE:
All reports by Author Chin Ho Lee:

TR17-167 | 3rd November 2017
Chin Ho Lee, Emanuele Viola

More on bounded independence plus noise: Pseudorandom generators for read-once polynomials

Revisions: 1

We construct pseudorandom generators with improved seed length for
several classes of tests. First we consider the class of read-once
polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed
length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order
terms. This is optimal up to the factor ... more >>>


TR17-090 | 15th May 2017
Chin Ho Lee, Emanuele Viola

The coin problem for product tests

Let $X_{m, \eps}$ be the distribution over $m$ bits $(X_1, \ldots, X_m)$
where the $X_i$ are independent and each $X_i$ equals $1$ with
probability $(1+\eps)/2$ and $0$ with probability $(1-\eps)/2$. We
consider the smallest value $\eps^*$ of $\eps$ such that the distributions
$X_{m,\eps}$ and $X_{m,0}$ can be distinguished with constant
more >>>


TR16-169 | 3rd November 2016
Elad Haramaty, Chin Ho Lee, Emanuele Viola

Bounded independence plus noise fools products

Let $D$ be a $b$-wise independent distribution over
$\{0,1\}^m$. Let $E$ be the ``noise'' distribution over
$\{0,1\}^m$ where the bits are independent and each bit is 1
with probability $\eta/2$. We study which tests $f \colon
\{0,1\}^m \to [-1,1]$ are $\e$-fooled by $D+E$, i.e.,
$|\E[f(D+E)] - \E[f(U)]| \le \e$ where ... more >>>


TR16-102 | 4th July 2016
Ravi Boppana, Johan HÃ¥stad, Chin Ho Lee, Emanuele Viola

Bounded independence vs. moduli

Revisions: 1

Let $k=k(n)$ be the largest integer such that there
exists a $k$-wise uniform distribution over $\zo^n$ that
is supported on the set $S_m := \{x \in \zo^n : \sum_i
x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We
show that $\Omega(n/m^2 \log m) \le k \le 2n/m + ... more >>>


TR15-005 | 5th January 2015
Chin Ho Lee, Emanuele Viola

Some limitations of the sum of small-bias distributions

Revisions: 1

We exhibit $\epsilon$-biased distributions $D$
on $n$ bits and functions $f\colon \{0,1\}^n
\to \{0,1\}$ such that the xor of two independent
copies ($D+D$) does not fool $f$, for any of the
following choices:

1. $\epsilon = 2^{-\Omega(n)}$ and $f$ is in P/poly;

2. $\epsilon = 2^{-\Omega(n/\log n)}$ and $f$ is ... more >>>


TR12-157 | 12th November 2012
Andrej Bogdanov, Chin Ho Lee

On the depth complexity of homomorphic encryption schemes

Revisions: 2

We show that secure homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure encryption scheme cannot be implemented by constant depth, polynomial size circuits, i.e. in the class AC0. In contrast, we observe that certain previously studied encryption schemes (with quasipolynomial security) can ... more >>>


TR12-156 | 12th November 2012
Andrej Bogdanov, Chin Ho Lee

Limits of provable security for homomorphic encryption

Revisions: 1

We show that public-key bit encryption schemes which support weak homomorphic evaluation of parity or majority cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity.

Previous works on the limitation of reductions for proving security of ... more >>>




ISSN 1433-8092 | Imprint