Finding a problem that is both hard to solve and hard to solve on many instances is a long standing issue
in theoretical computer science.
In this work, we prove that the Succinct Permanent $\bmod \; p$ is $NEXP$
time hard in the worst case (via randomized polynomial time ... more >>>

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):
Given a low-degree polynomial mapping
$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy
$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if $\mathrm{prAM}\subseteq \mathrm{P}^{\mathrm{NP}}$ then there is a Boolean function in $\mathrm{E}^{\mathrm{NP}}$ that requires ... more >>>

We study the complexity of locally list-decoding binary error correcting codes with good parameters (that are polynomially related to information theoretic bounds). We show that computing majority over $\Theta(1/\eps)$ bits is essentially equivalent to locally list-decoding binary codes from relative distance $1/2-\eps$ with list size $\poly(1/\eps)$. That is, a local-decoder ... more >>>

We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson (FOCS `98, JCSS `01) and Trevisan and Vadhan (CCC `02, CC `07) exhibited such reductions for every function f in PSPACE. Moreover, their reductions ... more >>>

Program checking, program self-correcting and program self-testing
were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in
the mid eighties as a new way to gain confidence in software, by
considering program correctness on an input by input basis rather than
full program verification. Work in ... more >>>

We show that a mild derandomization assumption together with the
worst-case hardness of NP implies the average-case hardness of a
language in non-deterministic quasi-polynomial time. Previously such
connections were only known for high classes such as EXP and
PSPACE.

There has been a long line of research trying to explain ... more >>>

We study the complexity of computing $k$-wise independent and
$\epsilon$-biased generators $G : \{0,1\}^n \to \{0,1\}^m$.
Specifically, we refer to the complexity of computing $G$ \emph{explicitly}, i.e.
given $x \in \{0,1\}^n$ and $i \in \{0,1\}^{\log m}$, computing the $i$-th output bit of $G(x)$.
Mansour, Nisan and Tiwari (1990) show that ... more >>>