Proving circuit lower bounds is one of the most difficult tasks in computational complexity theory. The NP vs. P/poly problem asks whether there are small non-uniform circuits that can simulate circuit satisfiability. The answer is widely believed to be false, but so far progress has only been made in the case of restricted circuits. In 1980s the progress stalled after it was shown that NP doesn’t have non uniform AC0 circuits that have MOD-m gates for any prime m. After almost three decades, in 2010s Williams made progress in the relaxed case of NEXP lower bounds. He first showed that non-trivial satisfiability algorithms for a circuit class entail NEXP lower bounds against that class. Then he designed a fast satisfiability algorithm for ACC circuits (AC0 circuits with MOD-m gates for any constant m) to show that NEXP doesn’t have non-uniform ACC circuits.

We make progress in bringing down the class NEXP, specifically by limiting non-determinism (in terms of the number of non-deterministic branches that accept). We show that slightly faster satisfiability algorithms entail lower bounds for UEXP and related classes. We believe this is progress towards making similar connections, and thus proving lower bounds, for EXP and lower complexity classes.

To investigate why progress again stalled around ACC lower bounds, and why TC0 (AC0 circuits with majority gates) lower bounds have not been established yet, Williams made rigorous connections between NEXP lower bounds and variations of Natural Proofs. Razborov and Rudich defined Natural Proofs to showcase the limitations of the current lower bound techniques. They showed that any technique that entails Natural Proofs, i.e. Proofs that are (i) constructive, (ii) useful, and (iii) large, fail to prove strong lower bounds. Williams showed that NEXP lower bounds, regardless of the technique, entail Proofs that satisfy the first two of the three conditions of Natural Proofs.

We make Williams connections more rigorous, and show that UEXP lower bounds entail Proofs, that in addition to the first two conditions of Natural Proofs, satisfy a third condition that is exactly the opposite of largeness condition. We call this condition, the uniqueness condition, and these Proofs, the Unique Proofs. These connections showcase that NEXP ? UEXP ? EXP is a viable path to approach EXP lower bounds.

We also discuss an alternate approach to improve NEXP lower bounds. We define a new form of nondeterminism to capture the non-uniform circuits from the class (NP ? Co-NP)/poly, and call it promise-Single-Valued non-determinism. We show that in the current NEXP lower bounds, we can allow the non-uniform circuits some limited non-determinism (in terms of the number of non-deterministic inputs) of the type promise-Single-Valued. We also discuss that, how small improvements in the amount of this special type of non-determinism, even in the restricted circuits much weaker than ACC, would imply very strong lower bounds such as NEXP ? P/poly.

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.

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