All reports by Author Soren Riis:

__
TR09-014
| 7th February 2009
__

Soren Riis#### On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity

__
TR97-048
| 13th October 1997
__

Soren Riis, Meera Sitharam#### Non-constant Degree Lower Bounds imply linear Degree Lower Bounds

Soren Riis

We show that the asymptotic complexity of uniformly generated (expressible in First-Order (FO) logic) propositional tautologies for the Nullstellensatz proof system (NS) as well as for Polynomial Calculus, (PC) has four distinct types of asymptotic behavior over fields of finite characteristic. More precisely, based on some highly non-trivial work by ... more >>>

Soren Riis, Meera Sitharam

The semantics of decision problems are always essentially independent of the

underlying representation. Thus the space of input data (under appropriate

indexing) is closed

under action of the symmetrical group $S_n$ (for a specific data-size)

and the input-output relation is closed under the action of $S_n$.

more >>>