@InProceedings{	  dlu12higmanstacs,
  author	= "Volker Diekert and J{\"u}rn Laun and Alexander Ushakov",
  title		= "Efficient algorithms for highly compressed data: {T}he
		  Word Problem in {H}igman's group is in {P}",
  booktitle	= "Proc.\ 29th International Symposium on Theoretical Aspects
		  of Computer Science, STACS 2012, Paris, France",
  year		= "2012",
  pages		= "218--229",
  publisher	= "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
  series	= "Leibniz International Proceedings in Informatics (LIPIcs)",
  volume	= "14",
  isbn		= "978-3-939897-35-4",
  note		= "Journal version: IJAC \textbf{22} (2012) 19 pages",
  abstract	= "Power circuits are data structures which support efficient
		  algorithms for highly compressed integers. Using this new
		  data structure it has been shown recently by Myasnikov,
		  Ushakov and Won that the Word Problem of the one-relator
		  Baumslag group is in P. Before that the best known upper
		  bound was non-elementary. In the present paper we provide
		  new results for power circuits and we give new applications
		  in algorithmic group theory: 1. We define a modified
		  reduction procedure on power circuits which runs in
		  quadratic time thereby improving the known cubic time
		  complexity. 2. We improve the complexity of the Word
		  Problem for the Baumslag group to cubic time thereby
		  providing the first practical algorithm for that problem.
		  (The algorithm has been implemented and is available in the
		  CRAG library.) 3. The main result is that the Word Problem
		  of Higman's group is decidable in polynomial time. The
		  situation for Higman's group is more complicated than for
		  the Baumslag group and forced us to advance the theory of
		  Power Circuits.",
  keywords	= "Algorithmic group theory, Data structures, Compression,
		  Word Problem",
  doi		= "10.4230/LIPIcs.STACS.2012.218"
}