%% a008.bib  10-05-2005

@Article{Abrahamson91,
  author =       "K. Abrahamson",
  title ={{Time-Space Tradeoffs for Algebraic Problems on General
 Sequential Machines}},
  journal =      "Journal of Computer and System Sciences",
  volume =       "43",
  year = 1991,
  pages = "269--289",
  eprint={jcss:10.1016/0022-0000(91)90014-V}
}

@InProceedings{Abrahamson86,
  author =       "K. Abrahamson",
  title ={{Time-Space Tradeoffs for Branching Programs Contrasted
 With Those for Straight-Line Programs}},
  booktitle =    {27th IEEE FOCS},
  publisher =    {IEEE Computer Society},
  year = "1986" 
}

@ARTICLE{A1,
  AUTHOR =       {M. Ajtai},
  TITLE =        {{Determinism versus Non-Determinism for Linear Time
{RAMs} with Memory Restrictions}},
  JOURNAL =      {Journal of Computer and System Sciences}, 
  YEAR =         {2002},
  volume =       {65},
  number =       {},
  pages =        {2--37},
  eprint =       {jcss:10.1006/jcss.2002.1821}
}

@INPROCEEDINGS{A2,
  AUTHOR =       {M. Ajtai},
  TITLE =        {A non-linear time lower bound for boolean branching
programs},
  BOOKTITLE =    {40th IEEE FOCS},
  YEAR =         {1999},
  editor =       {},
  volume =       {},
  number =       {},
  series =       {},
  pages =        {60--70},
  publisher =    {IEEE Computer Society},
  eprint =       {focs:10.1109/SFFCS.1999.814578}
}

@ARTICLE{BC,
  AUTHOR =       {A. Borodin and {S. A.} Cook},
  TITLE =        {A time-space tradeoff for sorting on a general
sequential model of computation},
  JOURNAL =      {{SIAM} J. Computing},
  YEAR =         {1982},
  volume =       {11},
  pages =        {287--297},
  eprint =       {sicomp:11/0211022}
}

@ARTICLE{Bea,
  AUTHOR =       {P. Beame},
  TITLE =        {{General Sequential Time-Space Tradeoff for Finding
Unique Elements}},
  JOURNAL =      {{SIAM} J. Computing},
  YEAR =         {1991},
  volume =       {20},
  number =       {2},
  pages =        {270--277},
  eprint =       {sicomp:20/0220017}
}

@ARTICLE{BSSV,
  AUTHOR =       {P. Beame and M. Saks and X. Sun and E. Vee},
  TITLE =        {Time-space tradeoff lower bounds for randomized
computation of decision problems},
  JOURNAL =      {Journal of the {ACM}},
  YEAR =         {2003},
  volume =       {50},
  number =       {2},
  pages =        {154--195},
  eprint =       {jacm:10.1145/636865.636867}
}

@ARTICLE{BRS,
  AUTHOR =       {A. Borodin and {A. A.} Razborov and R. Smolensky},
  TITLE =        {On lower bounds for read-$k$-times branching
programs},
  JOURNAL =      {Computational Complexity},
  YEAR =         {1993},
  volume =       {3},
  number =       {},
  pages =        {1--18}
}

@ARTICLE{BST,
  AUTHOR =       {P. Beame and M. Saks and {T. S.} Jayram},
  TITLE =        {Time-space tradeoffs for branching programs},
  JOURNAL =      {Journal of Computer and System Sciences},
  YEAR =         {2001},
  volume =       {63},
  number =       {4},
  pages =        {542--572},
  eprint =       {jcss:10.1006/jcss.2001.1778}
}

@INPROCEEDINGS{CG85,
  AUTHOR =       {B. Chor and O. Goldreich},
  TITLE =        {{Unbiased Bits from Sources of Weak Randomness and
Probabilistic Communication Complexity}},
  BOOKTITLE =    {26th IEEE FOCS},
  YEAR =         {1985},
  editor =       {},
  volume =       {},
  number =       {},
  series =       {},
  pages =        {429--442},
  publisher =    {IEEE Computer Society}
}

@Article{Karchmer86,
  author =       "M. Karchmer",
  title = {{Two Time-Space Tradeoffs for Element Distinctness}},
  journal =      "Theoretical Computer Science",
  volume =       "47",
  year = "1986",
  pages = "237--246",
  eprint={tcs:10.1016/0304-3975(86)90150-7}
}

@InProceedings{Reisch-Schnitger/82,
  author =       "S. Reisch and G. Schnitger",
  title ={{Three applications of Kolmogorov-complexity}},
  booktitle =    {23rd {IEEE} FOCS},
  pages ="45--52",
  year = "1982",
  publisher =    {IEEE Computer Society},
  cdate ="1970-01-01",
  mdate ="2005-08-18",
}

@INPROCEEDINGS{Tha,
  AUTHOR =       {{J. S.} Thathachar},
  TITLE =        {On separating the read-$k$-times branching program
hierarchy},
  BOOKTITLE =    {30th ACM STOC},
  YEAR =         1998,
  editor =       {},
  volume =       {},
  number =       {},
  series =       {},
  pages =        {653--662},
  publisher =    {ACM},
  eprint =       {stoc:10.1145/276698.276881}
}

@Article{Yesha84,
  author =       "Y. Yesha",
  title ={{Time-Space Tradeoffs for Matrix Multiplication and the
 Discrete Fourier Transform of Any General Sequential
 Random-Access Computer}},
  journal =      "Journal of Computer and System Sciences",
  volume =       "29",
  year = "1984",
  pages = "183--197",
  eprint = {jcss:10.1016/0022-0000(84)90029-1}
}