@techreport{Ajtai98,
   author    = {Mikl\'{o}s Ajtai},
   title     = {{D}eterminism versus {N}on-{D}eterminism for {L}inear {T}ime {RAM}s with {M}emory {R}estrictions},
   institution = {Electronic Colloquium on Computational Complexity},
   year      = {1998},
   number    = {077}
}

@inproceedings{Ajtai99,
   crossref  = {STOC31},
   author    = {Mikl\'{o}s Ajtai},
   title     = {{D}eterminism versus {N}on-{D}eterminism for {L}inear {T}ime {RAM}s with {M}emory {R}estrictions}
}

@TechReport{Ajtai99a,
  author = 	 {Mikl\'{o}s Ajtai},
  title = 	 {{A} {N}on-linear {T}ime {L}ower {B}ound for {B}oolean {B}ranching {P}rograms},
  institution =  {Electronic Colloquium on Computational Complexity},
  year = 	 {1999},
  number = 	 {026},
}
@InProceedings{Ajtai99b,
  crossref =     {FOCS40},
  author = 	 {Mikl\'{o}s Ajtai},
  title = 	 {{A} {N}on-linear {T}ime {L}ower {B}ound for {B}oolean {B}ranching {P}rograms},
}
@article{Beame91,
   author    = {Paul Beame},
   title     = {{A} {G}eneral {S}equential {T}ime-{S}pace {T}radeoff for {F}inding {U}nique {E}lements},
   journal   = {SIAM Journal on Computing},
   year      = {1991},
   volume    = {20},
   pages     = {270--277}
}
@article{Beame94,
   author    = {Paul Beame and Martin Tompa and Peiyuan Yan},
   title     = {{C}ommunication-{S}pace {T}radeoffs for {U}restricted {P}rotocols},
   journal   = {siamcomp},
   year      = {1994},
   month     = {June},
   volume    = {23},
   number    = {3},
   pages     = {652--661}
}
@techreport{Beame98,
   author    = {Paul Beame and Michael Saks and Jayram S. Thathachar},
   title     = {{T}ime-{S}pace {T}radeoffs for {B}ranching {P}rograms},
   institution = {Electronic Colloquium on Computational Complexity},
   year      = {1998},
   month     = {September},
   number    = {053}
}
@inproceedings{Beame98a,
   crossref  = {FOCS39},
   author    = {Paul Beame and Michael Saks and Jayram S. Thathachar},
   title     = {{T}ime-{S}pace {T}radeoffs for {B}ranching {P}rograms}
}
@TechReport{Beame98b,
  author =	 {Paul Beame and Faith Fich},
  title =	 {{On Searching Sorted Listes: A Near-Optimal Lower
                  Bound}},
  institution =	 {Electronic Colloquium on Computational Complexity},
  year =	 {1998},
  number =	 {??},
}
@InProceedings{Beame99,
  crossref =     {STOC31},
  author = 	 {Paul Beame and Faith E. Fich},
  title = 	 {{Optimal Bounds for the Predecessor Problem}},
}
@TechReport{Beame00a,
  author =	 {Paul Beame and Michael Saks and Xiaodong Sun and Erik Vee},
  title =	 {{Super-linear time-space tradeoff lower bounds for randomized computation}},
  institution =	 {Electronic Colloquium on Computational Complexity},
  year =	 {2000},
  number =	 {TR00-25},
}
@Misc{Beame00b,
  author = 	 {Paul Beame and Michael Saks and Jayram S. Thathachar},
  title = 	 {{T}ime-{S}pace {T}radeoffs for {B}ranching {P}rograms},
  year = 	 {2000},
  note = 	 {Submitted for journal publication},
}

@Article{Beame03,
  author = 	 {Paul Beame and Michael Saks and Xiaodong Sun and Erik Vee},
  title = 	 {Time-space trade-off lower bounds for randomized computation of decision problems},
  journal = 	 {Journal of the ACM},
  year = 	 {2003},
  volume = 	 {50},
  number = 	 {2},
  pages = 	 {154--195},
}
@article{Borodin81,
   author    = {Allan Borodin and Michael J. Fischer and David G. Kirkpatrick and Nancy A. Lynch and Martin Tompa},
   title     = {{A} {T}ime-{S}pace {T}radeoff for {S}orting on {N}on-{O}blivious {M}achines},
   journal   = {Journal of Computer and System Sciences},
   year      = {1981},
   volume    = {22},
   pages     = {351--364}
}
@article{Borodin82,
   author    = {Allan Borodin and Stephen Cook},
   title     = {{A} {T}ime-{S}pace {T}radeoff for {S}orting on a {G}eneral {S}equential {M}odel of {C}omputation},
   journal   = {SIAM Journal on Computing},
   year      = {1982},
   volume    = {11},
   number    = {2},
   pages     = {287--297},
   booktitle = {Conference Proceedings of the Twelfth Annual ACM Symposium on
       Theory of Computing},
   organization = {ACM}
}
@inproceedings{Borodin86,
   crossref  = {STACS86},
   author    = {Allan Borodin and Faith E. Fich and Meyer auf der
       Heide, Friedhelm and Eli Upfal and Avi Wigderson},
   title     = {A Time-Space Tradeoff for Element Distinctness},
   pages     = {353--358},
   source    = {http://theory.lcs.mit.edu/~dmjones/hbp/bibs/ley/stacs/stacs.bib}
}
@article{Borodin87,
   author    = {Allan Borodin and Faith E. Fich and Meyer auf der Heide, Friedhelm and Eli Upfal and Avi Wigderson},
   title     = {{A} {T}ime-{S}pace {T}radeoff for {E}lement {D}istinctness},
   journal   = {SIAM Journal on Computing},
   year      = {1987},
   volume    = {16},
   pages     = {97--99}
}
@inproceedings{Borodin93,
   author    = {Allan Borodin},
   title     = {{T}ime {S}pace {T}radeoffs ({G}etting {C}loser to the {B}arrier?)},
   booktitle = {{A}lgorithms and {C}omputation; 4th {I}nternational {S}ymposium, {ISAAC}'93},
   year      = {1993},
   month     = {December},
   editor    = {K.W. Ng and P. Raghavan and N.W. Balasubramanian and F.Y.L. Chin},
   publisher = {Springer-Verlag, {LNCS} 762}
}
@article{Borodin93a,
   author    = {A. Borodin and A. Razborov and R. Smolensky},
   title     = {{O} {L}ower {B}ounds for {R}ead-$K$-{T}imes {B}ranching {P}rograms},
   journal   = {Computational Complexity},
   year      = {1993},
   volume    = {3},
   pages     = {1--18}
}
@book{GKP94,
   author    = {Ronald Lewis Graham and Donald Erwin Knuth and Oren Patashnik},
   title     = {Concrete Mathematics},
   year      = {1994},
   publisher = {Addison-Wesley},
   edition   = {2nd}
}

@InProceedings{Hagerup98,
  author = 	 {Torben Hagerup},
  title = 	 {{S}orting and {S}earching on the {W}ord {RAM}},
  booktitle = {Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS '98)},
  pages = 	 {366--398},
  year = 	 {1998},
  volume = 	 {1373},
  series = 	 {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
}

@article{Karchmer86,
   author    = {Mauricio Karchmer},
   title     = {{T}wo {T}ime-{S}pace {T}radeoffs for {E}lement {D}istinctness},
   journal   = {Theoretical Computer Science},
   year      = {1986},
   volume    = {47},
   pages     = {237--246}
}
@Book{Knuth97,
   author    = {Donald  Ervin Knuth},
   title     = {{F}undamental {A}lgorithms},
   year      = {1997},
   publisher = {Addison-Wesley},
   edition   = {3rd},
   volume    = {2},
   series    = {{T}he {A}rt of {C}omputer {P}rogramming},
   crossrefonly = 1 
}
@book{Knuth98,
   author    = {Donald  Ervin Knuth},
   title     = {{S}orting and {S}earching},
   year      = {1998},
   publisher = {Addison-Wesley},
   edition   = {2nd},
   volume    = {3},
   series    = {{T}he {A}rt of {C}omputer {P}rogramming},
   crossrefonly = 1 
}
@article{Mansour93,
   author    = {Yishay Mansour and Noam Nisan and Prasoon Tiwari},
   title     = {{T}he {C}omputational {C}omplexity of {U}niversal {H}ashing},
   journal   = {Theoretical Computer Science},
   year      = {1993},
   number    = {107},
   pages     = {121--133}
}
@TechReport{Pagter00,
  author = 	 {Jakob Pagter},
  title = 	 {{O}n {A}jtai's {L}ower {B}ound {T}echnique for $R$-way {B}ranching {P}rograms and the {H}amming {D}istance {P}roblem},
  institution =  {BRICS, Department of Computer Science, University of Aarhus},
  year = 	 {2000},
  number = 	 {BRICS-RS-01-2},
  month = 	 {May},
}
@PhdThesis{Pagter01,
  author = 	 {Jakob Pagter},
  title = 	 {{T}ime-{S}pace {T}rade-{O}ffs},
  school = 	 {BRICS, Department of Computer Science, University of Aarhus},
  year = 	 {2001},
}
@proceedings{STOC31,
   title     = {Thirty-First ACM Symposium on Theory of Computing},
   organization = {ACM},
   year      = {1999},
   booktitle = {Thirty-First ACM Symposium on Theory of Computing}
}
@book{Savage98,
   author    = {John Edmund Savage},
   title     = {{M}odels of {C}omputation},
   year      = {1998},
   publisher = {Addison-Wesley},
   crossrefonly = 1 
}
@article{Yao94,
   author    = {Andrew Chi-Chih Yao},
   title     = {{N}ear-optimal {T}ime-{S}pace {T}radeoff for {E}lement {D}istinctness},
   journal   = {SIAM Journal on Computing},
   year      = {1994},
   volume    = {23},
   pages     = {966--975},
   annote    = {TS=\Omega (n^{2-\varepsilon(n)}), \varepsilon(n) = 5/(\ln n)^2,
       in the comparison based branching program model. The result
       is based on \cite{Borodin87}, refining their result.}
}
@proceedings{FOCS37,
   title     = {37th Annual Symposium on Foundations of Computer Science},
   organization = {IEEE},
   year      = {1996},
   booktitle = {37th Annual Symposium on Foundations of Computer Science}
}

@proceedings{FOCS39,
   title     = {39th Annual Symposium on Foundations of Computer Science},
   organization = {IEEE},
   year      = {1998},
   booktitle = {39th Annual Symposium on Foundations of Computer Science}
}

@proceedings{FOCS40,
   title     = {40th Annual Symposium on Foundations of Computer Science},
   organization = {IEEE},
   year      = {1999},
   booktitle = {40th Annual Symposium on Foundations of Computer Science}
}