Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Local reductions

RSS-Feed




Revision #3
Authors: Hamidreza Jahanjou, Eric Miles, Emanuele Viola
Accepted on: 4th April 2014 21:13
Downloads: 781
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
Downloads: 849
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
Downloads: 802
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
Downloads: 1069
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