Lars Engebretsen, Jonas Holmerin, Alexander Russell

An equation over a finite group G is an expression of form

w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted

variable, or a constant from G; such an equation is satisfiable

if there is a setting of the variables to values in G ...
more >>>

Oded Goldreich, Laliv Tauber

Following Ergun et al. (JCSS 2000), we consider testing group properties and focus on the problem of testing whether a binary operation is a group operation.

That is, given a finite set $S$ and oracle access to a function $f:S\times S \to S$, we wish to distinguish the case that ...
more >>>