Current filters:

Search Results

  • <<
  • 1
  • >>
Item hits:
  • Thesis

  • Authors: Nudelman, Eugene (2005)

  • Traditionally, computer scientists have considered computational problems and al¬gorithms as artificial formal objects that can be studied theoretically. In this work we propose a different view of algorithms as natural phenomena that can be studied using empirical methods. In the first part, we propose a methodology for using ma-chine learning techniques to create accurate statistical models of running times of a given algorithm on particular problem instances. Rather than focus on the traditional aggregate notions of hardness, such as worst-case or average-case complexity, these models provide a much more comprehensive picture of algorithms' performance. We demonstrate that such models can indeed be constructed for two notoriously hard domains: winner determination problem for com...

  • Thesis

  • Authors: Ulrich, James L (2005)

  • Motivated by a desire to test the security of the pubic key exchange protocol of I. Anshel, M. Anshel, and D. Goldfeld, (“An Algebraic Method for Public-Key Cryptography”, Mathematical Research Letters, vol. 6, pp. 1-5, 1999), we study algorithmic approaches to the simple commutator decision and promise problems (SCDP/SCPP) for the braid groups Bn. We take as our point of departure a seminal paper of O. Ore, (“Some Remarks on Commutators”, Proceedings of the American Mathematical Society, Vol. 2, No. 2, pp.307-314, 1951), which studies the SCPP for the symmetric groups. Our results build on the work of H. Cejtin and I. Rivin, (“A Property of Alternating Groups”, arXiv:math.GR/0303036). We extract, from their proof that any element of the alternating subgroup of Sn can be written as...