Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-167 | 23rd May 2020 03:37

Unique Properties, Lower Bounds & Derandomization

Revision #1
Authors: Anant Dhayal, Russell Impagliazzo
Accepted on: 23rd May 2020 03:37
Keywords:

Abstract:

The most difficult tasks in computational complexity are: proving uniform/non-uniform lower bounds, designing fast satisfiability/learning algorithms, and derandomizing probabilistic algorithms. Connections have been drawn between them to study the relative hardness of these tasks: (a) Uniform to non-uniform lower bounds,
famously known as Karp-Lipton style theorems (KLT) [43]; (b) Fast algorithms to lower bounds; (c) Lower
bounds to derandomization. Such connections were initially known for the class EXP, and then later were
extended to NEXP. The key in the extension was the “easy-witness lemma (EWL) for NEXP” [31]. We extend
these connections to the intermediate class UEXP, and some related classes, by deriving similar EWLs for them.
In the ‘fast algorithms to lower bounds’ connection we also provide translation results that generalize the
lower bound frameworks for unrestricted Boolean circuits, to all typical circuit classes, in a black box fashion
(i.e. generalization only depends on the assumption set of the framework and not its working).
Circuit lower bound techniques that entail natural properties of Razborov and Rudich [61] are called
natural, and are known to contradict widely believed cryptographic assumptions in the course of proving
strong lower bounds. Thus attempts have been made to understand un-natural techniques. Natural properties
satisfy three conditions: usefulness, constructiveness, and largeness. Usefulness is implicit in any lower-bound
technique. In [57, 75] it was shown that P-constructivity is implicit in any NEXP or NEXP ? Co-NEXP lower
bound technique. In this paper we introduce a new notion called unique properties: properties that contain
exactly one element and thus avoid largeness. We show that P-constructivity and uniqueness are implicit in
any UEXP or UEXP ? Co-UEXP lower bound technique. For the case of NP-constructivity, for different lower
bound settings, we establish equivalences between: properties with arbitrary largeness and unique properties.
In the process we obtain a variety of EWLs and KLTs for NEXP ? Co-NEXP and related classes.
Equivalences between deterministic lower bounds and derandomization has been studied extensively in
the past. This was extended to non-deterministic circuits in [7] using an improved high-end KLT for NP/????????????????.
Using the higher Arthur-Merlin classes from [38] we generalize this KLT to general circuit classes and obtain: (i)
a wide spectrum of lower bounds vs derandomization equivalences; (ii) lower bounds for higher Arthur-Merlin
classes against general circuit classes. Our KLT extends to EXP and UEXP, but not to NEXP due to the lack of EWLs.
For the special case of NEXP ? (NP?Co-NP)/???????????????? we prove equivalence with: witness lower bound, an uniform
lower bound, and various useful properties. We extend results from [75] to show that: super-polynomial
savings in exhaustive search for certain problems imply NEXP ? (NP ? Co-NP)/????????????????. This new connection
yields an unconditional lower bound against a special restriction of non-deterministic ACC circuits.

Paper:

TR19-167 | 21st November 2019 01:52

UTIME Easy-witness Lemma & Some Consequences

TR19-167
Authors: Anant Dhayal, Russell Impagliazzo
Publication: 21st November 2019 03:41
Keywords:

Abstract:

We prove an easy-witness lemma ($\ewl$) for unambiguous non-deterministic verfiers. We show that if $\utime(t)\subset\mathcal{C}$, then for every $L\in\utime(t)$, for every $\utime(t)$ verifier $V$ for $L$, and for every $x\in L$, there is a certificate $y$ satisfing $V(x,y)=1$, that can be encoded as a truth-table of a $\mathcal{C}$ circuit. Our technique is simple compared to the $\ntime$ $\ewl$s \cite{IKW02,Wil-ES13,MW18}, and yields fine-grained results in terms of the time and size parameters. It also works for all {\it typical} non-uniform circuit classes without any additional machinery. Using this $\ewl$ we prove a Karp-Lipton \cite{KL80} style theorem ($\klt$) for $\uexp$. We show that $\uexp\subset\size(poly)\implies\uexp=\ma$. We also prove similar $\ewl$ and $\klt$ for $\uexp\cap\couexp$ and $\fewexp$.

Circuit lower bound techniques that entail natural properties of Razborov and Rudich \cite{RR97} are called natural, and are known to contradict widely believed cryptographic assumptions in the course of proving strong lower bounds. Thus attempts have been made to understand un-natural techniques. Natural properties satisfy three conditions: usefulness, constructiveness, and largeness. Usefulness is unavoidable in any lower-bound technique. In \cite{Wil-NP16,Ig13} it was shown that obtaining $\nexp$ lower bounds is equivalent to obtaining $\pt$-constructive (with $\log n$ advice) properties.

In this paper we consider properties that avoid largeness. We introduce a new notion called unique properties, which is opposite to natural properties in the sense of largeness. A unique property contains exactly one element of each input length (that is a power of 2). We show that $\pt$-constructivity and uniqueness (opposite of largeness) both are unavoidable for certain lower bounds. We prove, $\uexp\cap\couexp\not\subset\mathcal{C}$ if and only if there is a $\pt$-constructive unique property against $\mathcal{C}$. We also establish equivalences between lower bounds against $\uexp$ (with and without advice), and the existence of different restrictions of $\pt$-constructive unique properties that use advice.

The derandomization (of $\bpp$) from uniform/non-uniform lower bounds for $\Gamma$'' type of results are known for $\Gamma=\expo,\nexp,\nexp\cap\conexp,\rexp$ \cite{NW94,BFNW93,IW01,IKW02,Wil-NP16}. Using the above equivalences we obtain a super-set of these results that also includes the classes $\uexp,\uexp\cap\couexp,\zpexp$.

One important application of the $\nexp$ $\ewl$ and $\klt$ is the connection between fast ($\sat$ and learning) algorithms and $\nexp$ lower bounds \cite{Wil-ES13,FK09,Ig13}. Using our $\utime$ $\ewl$ and $\klt$ we derive connections between fast unambiguous algorithms and $\utime$ lower bounds. Finally we show results that generalize the lower bound frameworks -- that work only for unrestricted Boolean circuits -- such that they work for any restricted typical circuit class. This will help us to get lower bounds against any typical circuit class from fast algorithms that work for that particular class (and not for the super-class of unrestricted Boolean circuits).

ISSN 1433-8092 | Imprint