18 citations · 18 across the 2 of their papers we have counts for
7 papers
Circuits, coNP-completeness, and the groups of Richard Thompson
Jean-Camille Birget
We construct a finitely presented group with coNP-complete word problem, and a finitely generated simple group with coNP-complete word problem. These groups are represented as Thom…
Probabilistic behavior of hash tables
Dawei Hong, Jean-Camille Birget, Shushuang Man
We extend a result of Goldreich and Ron about estimating the collision probability of a hash function. Their estimate has a polynomial tail. We prove that when the load factor is g…
The groups of Richard Thompson and complexity
Jean-Camille Birget
We prove new results about the remarkable infinite simple groups introduced by Richard Thompson in the 1960s. We define the groups as partial transformation groups and we give a fa…
Functions on groups and computational complexity
Jean-Camille Birget
We give some connections between various functions defined on finitely presented groups (isoperimetric, isodiametric, Todd-Coxeter radius, filling length functions, etc.), and we s…
A complete rewrite system and normal forms for (S)_reg
Jean-Camille Birget, Stuart W. Margolis
The (.)_reg construction was introduced in order to make an arbitrary semigroup S divide a regular semigroup (S)_reg which shares some important properties with S (e.g., finiteness…
Isoperimetric Functions of Groups and Computational Complexity of the Word Problem
J. -C. Birget, A. Yu. Olshanskii, E. Rips +1
We prove that the word problem of a finitely generated group is in NP (solvable in polynomial time by a non-deterministic Turing machine) if and only if this group is a subgrou…