All reports by Author Ruiwen Chen:

__
TR17-173
| 6th November 2017
__

Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam#### An Average-Case Lower Bound against ACC^0

__
TR15-192
| 26th November 2015
__

Ruiwen Chen, Rahul Santhanam#### Satisfiability on Mixed Instances

__
TR15-112
| 16th July 2015
__

Ruiwen Chen, Rahul Santhanam#### Improved Algorithms for Sparse MAX-SAT and MAX-$k$-CSP

__
TR15-099
| 12th June 2015
__

Ruiwen Chen#### Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

__
TR14-184
| 29th December 2014
__

Ruiwen Chen, Valentine Kabanets#### Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits

__
TR13-150
| 4th November 2013
__

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh#### An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas

__
TR13-057
| 5th April 2013
__

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman#### Mining Circuit Lower Bound Proofs for Meta-Algorithms

__
TR12-007
| 28th January 2012
__

Ruiwen Chen, Valentine Kabanets#### Lower Bounds against Weakly Uniform Circuits

Revisions: 1

Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam

In a seminal work, Williams [Wil14] showed that NEXP (non-deterministic exponential time) does not have polynomial-size ACC^0 circuits. Williams' technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known.

We show that there is a language L in NEXP (resp. EXP^NP) ... more >>>

Ruiwen Chen, Rahul Santhanam

The study of the worst-case complexity of the Boolean Satisfiability (SAT) problem has seen considerable progress in recent years, for various types of instances including CNFs \cite{PPZ99, PPSZ05, Sch99, Sch05}, Boolean formulas \cite{San10} and constant-depth circuits \cite{IMP12}. We systematically investigate the complexity of solving {\it mixed} instances, where different parts ... more >>>

Ruiwen Chen, Rahul Santhanam

We 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 ...
more >>>

Ruiwen Chen

We give a \#SAT algorithm for boolean formulas over arbitrary finite bases. Let $B_k$ be the basis composed of all boolean functions on at most $k$ inputs. For $B_k$-formulas on $n$ inputs of size $cn$, our algorithm runs in time $2^{n(1-\delta_{c,k})}$ for $\delta_{c,k} = c^{-O(c^2k2^k)}$. We also show the average-case ... more >>>

Ruiwen Chen, Valentine Kabanets

We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic #SAT algorithms for small linear-size circuits. In particular, we prove that, for boolean circuits of size $3n - n^{0.51}$, the correlation with Parity is at most $2^{-n^{\Omega(1)}}$, and there ... more >>>

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

We give a deterministic #SAT algorithm for de Morgan formulas of size up to $n^{2.63}$, which runs in time $2^{n-n^{\Omega(1)}}$. This improves upon the deterministic #SAT algorithm of \cite{CKKSZ13}, which has similar running time but works only for formulas of size less than $n^{2.5}$.

Our new algorithm is based on ... more >>>

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for ``easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an $n$-variate Boolean function $f$ computable by some unknown small circuit ... more >>>

Ruiwen Chen, Valentine Kabanets

A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if

there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,

given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one

to interpolate between complete uniformity (when $\gamma(n)=0$) ...
more >>>