Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR13-099 | 4th April 2014 21:13

#### Local reductions

Revision #3
Authors: Hamidreza Jahanjou, Eric Miles, Emanuele Viola
Accepted on: 4th April 2014 21:13
Keywords:

Abstract:

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT
instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$
such that there is an explicit circuit $C$ that on input
an index $i$ of $\log |\phi|$ bits outputs the $i$th
clause, and each output bit of $C$ depends on $O(1)$
inputs bits. The previous best result was $C$ in NC$^1$.
Even in the simpler setting of $|\phi| = \poly(T)$ the
previous best result was $C$ in AC$^0$.

More generally, for any time $T \ge n$ and parameter $r \leq n$ we obtain $\log_2 |\phi| = \max(\log T, n/r) + O(\log n) + O(\log\log T)$ and each output bit of $C$ is
a decision tree of depth $O(\log r)$.

As an application, we simplify the proof of Williams'
ACC$^0$ lower bound, and tighten his connection between
satisfiability algorithms and lower bounds.

Revision #2 to TR13-099 | 27th November 2013 18:29

#### Local reductions

Revision #2
Authors: Hamidreza Jahanjou, Eric Miles, Emanuele Viola
Accepted on: 27th November 2013 18:29
Keywords:

Abstract:

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT
instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$
such that there is an explicit circuit $C$ that on input
an index $i$ of $\log |\phi|$ bits outputs the $i$th
clause, and each output bit of $C$ depends on $O(1)$
inputs bits. The previous best result was $C$ in NC$^1$.
Even in the simpler setting of $|\phi| = \poly(T)$ the
previous best result was $C$ in AC$^0$.

More generally, for any time $T \ge n$ and parameter $r \leq n$ we obtain $\log_2 |\phi| = \max(\log T, n/r) + O(\log n) + O(\log\log T)$ and each output bit of $C$ is
a decision tree of depth $O(\log r)$.

As an application, we simplify the proof of Williams'
ACC$^0$ lower bound, and tighten his connection between
satisfiability algorithms and lower bounds.

Revision #1 to TR13-099 | 2nd September 2013 00:05

#### Local reductions

Revision #1
Authors: Hamidreza Jahanjou, Eric Miles, Emanuele Viola
Accepted on: 2nd September 2013 00:05
Keywords:

Abstract:

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT
instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$
such that there is an explicit circuit $C$ that on input
an index $i$ of $\log |\phi|$ bits outputs the $i$th
clause, and each output bit of $C$ depends on $O(1)$
inputs bits. The previous best result was $C$ in NC$^1$.
Even in the simpler setting of $|\phi| = \poly(T)$ the
previous best result was $C$ in AC$^0$.

More generally, for any time $T \ge n$ and parameter $r \leq n$ we obtain $\log_2 |\phi| = \max(\log T, n/r) + O(\log n) + O(\log\log T)$ and each output bit of $C$ is
a decision tree of depth $O(\log r)$.

As an application, we simplify the proof of Williams'
ACC$^0$ lower bound, and tighten his connection between
satisfiability algorithms and lower bounds.

Changes to previous version:

Minor changes

### Paper:

TR13-099 | 6th July 2013 17:08

#### Local reductions

TR13-099
Authors: Hamidreza Jahanjou, Eric Miles, Emanuele Viola
Publication: 6th July 2013 17:08
Keywords:

Abstract:

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT
instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$
such that there is an explicit circuit $C$ that on input
an index $i$ of $\log |\phi|$ bits outputs the $i$th
clause, and each output bit of $C$ depends on $O(1)$
inputs bits. The previous best result was $C$ in NC$^1$.
Even in the simpler setting of $|\phi| = \poly(T)$ the
previous best result was $C$ in AC$^0$.

More generally, for any time $T \ge n$ and parameter $r \leq n$ we obtain $\log_2 |\phi| = \max(\log T, n/r) + O(\log n) + O(\log\log T)$ and each output bit of $C$ is
a decision tree of depth $O(\log r)$.

As an application, we simplify the proof of Williams'
ACC$^0$ lower bound, and tighten his connection between
satisfiability algorithms and lower bounds.

ISSN 1433-8092 | Imprint