  Under the auspices of the Computational Complexity Foundation (CCF)     REPORTS > AUTHORS > BIN FU:
All reports by Author Bin Fu:

TR13-157 | 11th November 2013
Bin Fu

#### Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP

We show that
derandomizing polynomial identity testing over an arbitrary finite
field implies that NEXP does not have polynomial size boolean
circuits. In other words, for any finite field F(q) of size q,
$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where
$PIT_q$ is the polynomial identity testing problem over F(q), and
NSUBEXP is ... more >>>

TR11-028 | 24th February 2011
Richard Beigel, Bin Fu

#### A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing

The bin packing problem is to find the minimum
number of bins of size one to pack a list of items with sizes
$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects
a random element from the input list each time, we develop a
randomized $O({n(\log n)(\log\log n)\over ... more >>> TR10-202 | 9th December 2010 Bin Fu #### Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP We investigate the complexity of integration and derivative for multivariate polynomials in the standard computation model. The integration is in the unit cube$[0,1]^d$for a multivariate polynomial, which has format$f(x_1,\cdots,
x_d)=p_1(x_1,\cdots, x_d)p_2(x_1,\cdots, x_d)\cdots p_k(x_1,\cdots,
G_2\times\cdots G_t$, where each$G_i$is a cyclic group of size$p^j$for some prime$p$and integer$j\ge 1$. If$a_i$is the generator of the cyclic group of ... more >>> TR05-013 | 22nd December 2004 Bin Fu #### Theory and Application of Width Bounded Geometric Separator We introduce the notion of width bounded geometric separator, develop the techniques for its existence as well as algorithm, and apply it to obtain a$2^{O(\sqrt{n})}$time exact algorithm for the disk covering problem, which seeks to determine the minimal number of fixed size disks to cover$n\$ points on ... more >>>

ISSN 1433-8092 | Imprint