All reports by Author Hubie Chen:

__
TR05-036
| 28th March 2005
__

Hubie Chen#### Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms

__
TR01-095
| 12th November 2001
__

Hubie Chen#### Arithmetic Versions of Constant Depth Circuit Complexity Classes

__
TR01-067
| 18th September 2001
__

Hubie Chen#### Polynomial Programs and the Razborov-Smolensky Method

Hubie Chen

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the quantified constraint satisfaction problem (QCSP), ... more >>>

Hubie Chen

The boolean circuit complexity classes

AC^0 \subseteq AC^0[m] \subseteq TC^0 \subseteq NC^1 have been studied

intensely. Other than NC^1, they are defined by constant-depth

circuits of polynomial size and unbounded fan-in over some set of

allowed gates. One reason for interest in these classes is that they

contain the ...
more >>>

Hubie Chen

Representations of boolean functions as polynomials (over rings) have

been used to establish lower bounds in complexity theory. Such

representations were used to great effect by Smolensky, who

established that MOD q \notin AC^0[MOD p] (for distinct primes p, q)

by representing AC^0[MOD p] functions as low-degree multilinear

polynomials over ...
more >>>