ECCC-Report TR13-099https://eccc.weizmann.ac.il/report/2013/099Comments and Revisions published for TR13-099en-usFri, 04 Apr 2014 21:13:29 +0300
Revision 3
| Local reductions |
Hamidreza Jahanjou,
Eric Miles,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2013/099#revision3We 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.
Fri, 04 Apr 2014 21:13:29 +0300https://eccc.weizmann.ac.il/report/2013/099#revision3
Revision 2
| Local reductions |
Hamidreza Jahanjou,
Eric Miles,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2013/099#revision2We 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.
Wed, 27 Nov 2013 18:29:33 +0200https://eccc.weizmann.ac.il/report/2013/099#revision2
Revision 1
| Local reductions |
Hamidreza Jahanjou,
Eric Miles,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2013/099#revision1We 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.
Mon, 02 Sep 2013 00:05:38 +0300https://eccc.weizmann.ac.il/report/2013/099#revision1
Paper TR13-099
| Local reductions |
Hamidreza Jahanjou,
Eric Miles,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2013/099We 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.
Sat, 06 Jul 2013 17:08:52 +0300https://eccc.weizmann.ac.il/report/2013/099