ECCC-Report TR15-112https://eccc.weizmann.ac.il/report/2015/112Comments and Revisions published for TR15-112en-usThu, 16 Jul 2015 20:10:35 +0300
Paper TR15-112
| Improved Algorithms for Sparse MAX-SAT and MAX-$k$-CSP |
Ruiwen Chen,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2015/112We give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX-$k$-CSP. For instances with $n$ variables and $cn$ clauses (constraints), we give algorithms running in time $\poly(n)\cdot 2^{n(1-\mu)}$ for
\begin{itemize}
\item $\mu = \Omega(\frac{1}{c} )$ and polynomial space solving MAX-SAT and MAX-$k$-SAT,
\item $\mu = \Omega(\frac{1}{\sqrt{c}} )$ and exponential space solving MAX-SAT and MAX-$k$-SAT,
\item $\mu = \Omega(\frac{1}{ck^2} )$ and polynomial space solving MAX-$k$-CSP,
\item $\mu = \Omega(\frac{1}{\sqrt{ck^3}} )$ and exponential space solving MAX-$k$-CSP.
\end{itemize}
The previous MAX-SAT algorithms have savings $\mu=\Omega(\frac{1}{c^2 \log^2 c})$ for running in polynomial space~\cite{SST14} and $\mu=\Omega(\frac{1}{c \log c})$ for exponential space~\cite{DW06}. We also give an algorithm with improved savings for satisfiability of depth-2 threshold circuits with $cn$ wires.Thu, 16 Jul 2015 20:10:35 +0300https://eccc.weizmann.ac.il/report/2015/112