All reports by Author Shiteng Chen:

__
TR16-085
| 28th May 2016
__

Shiteng Chen, Periklis Papakonstantinou#### Depth-reduction for composites

__
TR15-122
| 29th July 2015
__

Shiteng Chen, Periklis Papakonstantinou#### Correlation lower bounds from correlation upper bounds

__
TR12-027
| 29th March 2012
__

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang#### Time-space tradeoffs for width-parameterized SAT:Algorithms and lower bounds

Revisions: 2

Shiteng Chen, Periklis Papakonstantinou

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating $NEXP$ from non-uniform $ACC$.

In particular, we show that every circuit with $AND,OR,NOT$, and $MOD_m$ gates, $m\in\mathbb{Z}^+$, of polynomial size and depth $d$ can be reduced to a depth-$2$, $SYM\circ AND$, circuit of ... more >>>

Shiteng Chen, Periklis Papakonstantinou

We show that for any coprime $m,r$ there is a circuit of the form $\text{MOD}_m\circ \text{AND}_{d(n)}$ whose correlation with $\text{MOD}_r$ is at least $2^{-O\left( \frac{n}{d(n)} \right) }$. This is the first correlation lower bound for arbitrary $m,r$, whereas previously lower bounds were known for prime $m$. Our motivation is the ... more >>>

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang

A decade has passed since Alekhnovich and Razborov presented an algorithm that solves SAT on instances $\phi$ of size $n$ having tree-width $TW(\phi)$, using time (and space) bounded by $2^{O(TW(\phi))}n^{O(1)}$. Although there have been several papers over the ensuing years building on the work of Alekhnovich and Razborov there has ... more >>>