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

Revisions: 1
,
Comments: 1

__
TR11-028
| 24th February 2011
__

Richard Beigel, Bin Fu#### A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing

__
TR10-202
| 9th December 2010
__

Bin Fu#### Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP

__
TR10-196
| 8th December 2010
__

Bin Fu#### NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets

__
TR10-124
| 18th July 2010
__

Zhixiang Chen, Bin Fu#### Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials

__
TR10-122
| 18th July 2010
__

Zhixiang Chen, Bin Fu, Yang Liu, Robert Schweller#### Algorithms for Testing Monomials in Multivariate Polynomials

__
TR10-114
| 17th July 2010
__

Zhixiang Chen, Bin Fu#### The Complexity of Testing Monomials in Multivariate Polynomials

__
TR07-052
| 7th May 2007
__

Li Chen, Bin Fu#### Linear and Sublinear Time Algorithms for the Basis of Abelian Groups

Revisions: 2

__
TR05-013
| 22nd December 2004
__

Bin Fu#### Theory and Application of Width Bounded Geometric Separator

Bin Fu

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

Richard Beigel, Bin Fu

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

Bin Fu

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,

x_d)$,

where each $p_i(x_1,\cdots, x_d)=\sum_{j=1}^d q_j(x_j)$ with

all single variable polynomials $q_j(x_j)$ ...
more >>>

Bin Fu

A long standing open problem in the computational complexity theory

is to separate NE from BPP, which is a subclass of $NP_T (NP\cap P/poly)$.

In this paper, we show that $NE\not\subseteq NP_T (NP \cap$ Nonexponentially-Dense-Class),

where Nonexponentially-Dense-Class is the class of languages A without exponential density

(for ...
more >>>

Zhixiang Chen, Bin Fu

This paper is our third step towards developing a theory of testing monomials in multivariate polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a $\Pi\Sigma\Pi$ polynomial.

We first prove ...
more >>>

Zhixiang Chen, Bin Fu, Yang Liu, Robert Schweller

This paper is our second step towards developing a theory of

testing monomials in multivariate polynomials. The central

question is to ask whether a polynomial represented by an

arithmetic circuit has some types of monomials in its sum-product

expansion. The complexity aspects of this problem and its variants

have been ...
more >>>

Zhixiang Chen, Bin Fu

The work in this paper is to initiate a theory of testing

monomials in multivariate polynomials. The central question is to

ask whether a polynomial represented by certain economically

compact structure has a multilinear monomial in its sum-product

expansion. The complexity aspects of this problem and its variants

are investigated ...
more >>>

Li Chen, Bin Fu

It is well known that every finite Abelian group $G$ can be

represented as a product of cyclic groups: $G=G_1\times

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

Bin Fu

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