“Partial
automorphism semigroups,” co-authored
with J. Chubb, V.S. Harizanov, A. Morozov, and E. Ufferman, submitted to the Annals of Pure and Applied Logic.
“Π^0_1
classes and strong
degree spectra of relations,” co-authored with
J. Chisholm, J. Chubb, V.S. Harizanov, D.R. Hirschfeldt, C.G. Jockusch,
and T. McNicholl, Journal of Symbolic
Logic 72 (2007), pp. 1003-1018.
Presentations
Orderings on computable torsion free abelian groups - Invited to speak at the 25th Conference on Knot Theory and its Ramifications, at The George Washington University in Washington, D.C. on 12/9/07.
A countable group is computable if its domain is a computable set and its group theoretic operation is computable. We examine complexity of orders on a computable torsion-free abelian (hence orderable) group G, using Turing degrees as a complexity measure. There are continuum many Turing degrees and they form an upper semilattice under Turing reducibility. All computable sets have Turing degree zero. It is easy to see that if G is of rank 1, then G has exactly two orders and they are computable. Solomon showed that if G has a finite rank greater than 1, then G has an order in every Turing degree. On the other hand, if G is of infinite rank, then G does not necessarily have a computable order, as shown by Downey and Kurtz.
Computability and the Halting Problem - Presented in the GW Mathematics Graduate Student
Seminar on 11/29/07.
Computability theory was invented in the 1930's by Turing, Gödel, Church, and Kleene, among others, who gave formal definitions of a computable function. All of these definitions turned out to be equivalent. The Church-Turing Thesis, generally accepted by all computability theorists, says that the formal notion of a computable function captures the intuitive idea of a computable function. I will discuss what it means for a function, set, and relation to be computable, and computably enumerable and then define the Turing degrees. The Turing degree of a set says how uncomputable a set is. Then, we will discuss the halting problem, which is a natural example of a set that is computably enumerable but not computable. This talked is aimed at undergraduates.
Complexity of Relations on Computable Structures - Invited to speak at the AMS meeting in Middle Tennessee State University, Murfreesboro in the Special Session on Advances in Algorithmic Methods for Algebraic Structures on 11/4/07.
Let A be a computable structure and R be an additional relation on A. The Turing degree spectrum of R on A is the set of all Turing degrees of the images of R under all isomorphisms from A to computable models. Harizanov found a sufficient and necessary condition for the Turing degree spectrum to contain all Turing degrees, which can be adapted to truth-table reducibility. She also showed that the
Turing degree spectrum of the w-part of a linear ordering of type w+w* is all of the Δ^0_2 Turing degrees. This is not the case for tt-degrees, and it can be shown that there is a computably enumerable set D such that D is not weak truth-table reducible to any initial segment of any computable scattered linear ordering. This is joint work with J. Chisholm, J. Chubb, V. Harizanov, D. Hirschfeldt, C. Jockusch, and T. McNicholl. Abstract # 1033-03-152
Complexity of Relations on Computable Structures, Part III - Presented in the GW Mathematics Logic Seminar on 9/28/07.
We will continue our talk from last week and also extend the main result, by showing that there exists a low computably enumerable set C not weak truth-table reducible to any initial segment of any computable scattered linear ordering. We will also discuss a sufficient and necessary condition for the truth-table degree spectrum of a relation on computable structure to contain all degrees.
Complexity of Relations on Computable Structures: Interval Trees, Part II - Presented in the GW Mathematics Logic Seminar on 9/21/07.
We will continue our talk from last week and show our main theorem, that for every limit computable set C, there is a computable linear ordering L of order type w+w* such that C ≤T w(L) ≤tt C. Then, we will extend our first application of interval trees to show that if we assume that C is computably enumerable, then so is w(L). We will also show that the main theorem does not hold when Turing reducibility is replaced by weak truth-table reducibility. We will also give a strengthened version of this result: that C is also not weak truth-table reducible to any computable scattered linear ordering.
Complexity of Relations on Computable Structures: Interval Trees, Part I - Presented in the GW Mathematics Logic Seminar on 9/14/07.
Let A be a computable structure and R be an additionalelation on A. The Turing degree spectrum of R on
A is the set of all Turing degrees of the images of R under all isomorphisms from A to computable models. Harizanov showed that the Turing degree spectrum of the omega-part of a linear ordering of
type w+w* is all of the Δ^0_2 Turing degrees. This is not the case for tt-degrees, and we will show the best possible positive result, that for every Δ^0_2 set A, there is computable linear ordering L of order type w+w* such that A is Turing below the omega-part of L which is tt-below A. We will show this result by defining a new technique of finding the interval tree of a linear ordering. This is joint work with J. Chisholm, J. Chubb, V.S. Harizanov, D.R. Hirschfeldt, C.G. Jockusch, and T. McNicholl.
Encryption Today - Presented to the Dean's Seminar: Turing machines, Chomsky languages, digital and quantum computing, taught by V. Harizanov on 3/27/07.
Also Presented to the Dean's Seminar: Is reason computable? Taught by V. Harizanov on 4/27/06.
The internet age is defined by information sharing worldwide based on more people having access to technology. Technologies such as encryption have been important in regulating access to this information by protecting privacy, property, and principles by whoever chooses to share data. Using several examples, I will describe how several algorithmic techniques can be used to protect information in transit. Beginning with passwords transmitted with Secure Sockets Layers (SSL), leading to simple Digital Rights Management (DRM) which is used to secure DVDs and music, and concluding with more sophisticated schemes such as watermarking and containers, I will describe how encryption has and will become important in our daily lives. Comparatively, I will discuss how encryption methods reduce the quality and quantity of data in an environment without standards especially given the rate of non-encrypted media becoming obsolete.
Complexity of Relations on Computable Structures - Presented at the Second New York Graduate Student Logic Conference on 3/17/07.
Also Presented at the GW Mathematics Graduate Student Seminar on 3/9/07.
Let A be a computable structure and R be an additional relation on A. The Turing degree spectrum of R on A is the set of all Turing degrees of the image of R under all isomorphisms from A to computable models. Harizanov found a sufficient and necessary condition for the Turing degree spectrum to contain all Turing degrees, which can be relativized to truth-table reducibility. She also showed that the Turing degree spectrum of the w-part of a linear ordering of type w+w* is all of the Δ^0_2 degrees. This is not the case for tt-degrees, and it can be shown that there is a computable enumerable set D such that D is not weak truth-table reducible to any initial segment of any computable scattered linear order. This is joint work with Chisholm, Chubb, Harizanov, Hirschfeldt, Jockusch, and McNicholl and this talk is part of a two-part talk with Jennifer Chubb.
Interval Trees - Presented in the GW Mathematics Logic Seminar on 4/4/06. Let L be a linear ordering with a least element. An interval tree is a partial function from a leftward-closed, finitely branching tree T whose nodes are sequences of natural numbers with no terminal nodes, to the set of nonempty intervals of L with some special properties. The talk with cover an introduction to interval trees and then discuss the relationships between interval trees and scattered linear orderings and linear orderings of type: natural numbers followed by a copy of integers.
A theorem on
strong degree spectra - Presented in the GW Mathematics Graduate Student
Seminar on 12/1/06.
We will take a short tour through computable model theory in order to understand the statement and importance of a theorem in one of my recent papers. Starting with a short introduction to model theory, we will then discuss linear orderings. Next, we will go over some basic computability theory and attempt to combine everything together at the end of the talk. This is joint work with J. Chisholm, J. Chubb, V.S. Harizanov, D.R. Hirschfeldt, C.G. Jockusch, and T. McNicholl.
Orderings
on computable torsion free abelian groups | Syllabus -
Presented for Logic specialty exam on 2/23/06. In 1979, Metakides and Nerode showed that facts about Π^0_1 classes can be transfered directly to the space of orders on computable fields. Solomon looked at the same problem for orderable groups. If G is a computable torsion free abelian group, we will find the complexity of the space of orders on G, depending on the rank of G. Then, we will be able to show Solomon’s result that one of the theorems of Metakides and Nerode does not hold, not even in a weak sense.
Courses - Instructor
MATH3 - College Algebra:
MATH51 - Finite Mathematics for the Social and
Management Sciences:
MATH52 - Business Calculus:
Courses - Teaching Assistant
MATH20 - Calculus with Precalculus I: Fall 2003
Instructor: J. Bonin
MATH31 - Calculus I: Fall 2005
Instructor: Y. Rong
MATH32 - Calculus II: Spring 2004
Instructor: M. Gupta
MATH51 - Finite Mathematics for the Social
and Management Sciences: Fall 2002, Spring 2004, Fall 2006, Spring 2007, Fall 2007
Instructors: R. Dimitrov, M. Moses, M. Moses, I. Yi, M. Moses
Other Academic Activites
Invited by the GW Mathematics Department Chair to give a presentation at a department teaching discussion. Spoke on Classes with Recitations: What does the instructor want? What does the teaching assistant want? What does the student want? on 3/23/07.
Copyeditor - Induction, Algorithmic Learning Theory, and Philosophy, M. Friend, N.B. Goethe, and V.S. Harizanov (eds.), Series Logic, Epistemology, and the Unity of Science, vol. 9, Springer, 2007, XIV, 290 p. ISBN: 978-1-4020-6126-4.
Awarded the Philip Amsterdam Graduate Teaching Assistant Honorable Mention Award on 5/4/04.
The views and opinions expressed on these pages are those of the author. The contents of this page have not been reviewed or approved by The George Washington University. Last updated on
9/12/07 9:40
