Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Shiteng Chen:

TR16-085 | 28th May 2016
Shiteng Chen, Periklis Papakonstantinou

Depth-reduction for composites

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 >>>

TR15-122 | 29th July 2015
Shiteng Chen, Periklis Papakonstantinou

Correlation lower bounds from correlation upper bounds

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint