Abstract: It is well known that multi-player potential game is PLS-complete.We show that constant player potential game is also PLS-complete.We also show that,there exist a constant-player potential game with some initial strategy such that it can

Abstract: Motivated by the problem of feature selection in machine learning, the problem of testing juntas, i.e., checking if a Boolean function on the n-dimensional hypercube only depends on k<<n coordinates, has attracted

Abstract: Polynomials are the most fundamental mathematical objects in algebra and it is compelling to understand the complexity of computing polynomials. That is, given a polynomial we want to understand the number of arithmetic

In the problem of partial function extension, we are given a partial function consisting of a set of $n$ points in a domain and a function value at each point.

Abstract: The communication complexity of a function f(x,y) is the number of bits that Alice and Bob need to communicate in order to compute f, when Alice has x and Bob has y.