18 citations · 18 across the 2 of their papers we have counts for
Showing 2003Show all
2 papers · 1 filter
math.GR2003★ 18 cited
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…
cs.DS2003
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…